xxsap

摘要： T1靜音問題 這個題做的比較滿意，主要考察單調(diào)隊列，大概花費了10min左右 T2課后答疑 這個題卡了很久的暴力寫法，大概一半多的時間都在調(diào)這道題的暴力寫法，花了很久過掉暴力，然后就有點懵了，導(dǎo)致考試的時候沒太想清楚怎么優(yōu)化 但其實很簡單，f[i]表示處理了前i個學(xué)生的問題的答案， 然后 f[i] 閱讀全文

摘要： T1 乘方 這個題真的是很簡單，就特判一下1的情況，其它情況直接暴力枚舉即可 考試的時候也是非常快的想到 T2 解密 也比較容易 首先我們把ed = (p_i?1)(q_i?1)+1打開 變?yōu)閑d = pq?p?q+1+1 將n = pq帶入原式得： ed = n?p?q+2 那么我們現(xiàn)在有了兩個式 閱讀全文

摘要： T1動態(tài)詢問 這個題主要考察快速排序求第k小O(n)的時間復(fù)雜度完成的方法 主要錯誤原因在于，在一些情況下x與y并不連續(xù)，中間可能會各一個數(shù)，所以它的k需要注意 這道在這個點上卡了很久，大概花費了1h左右，但感覺應(yīng)該可以更快的解決，主要在于那道題沒學(xué)好，一直記了一個錯誤的算法 T2財富計算 這個題做 閱讀全文

摘要： 快速排序 每次找一個基準(zhǔn)值，比基準(zhǔn)值小的放左邊，比基準(zhǔn)值大的放右邊，在分別對左右排序 標(biāo)準(zhǔn)代碼： void work(int l,int r) { if (l >= r) return; int mid = (l+r)/2; mid = a[mid]; int x = l,y = r; while 閱讀全文

摘要： 維護GCD 給出一個長度為n(1<=n<=10^5 )的序列和q(1<=q<=3*10^5)個詢問,每個詢問輸出一行,詢問gcd(a_i,a_i+1,...,a_j)=x的(i,j)的對數(shù)。 思考：首先GCD是可以重疊的符合ST表，其次思考f[l][len]如何轉(zhuǎn)移，通過之前的學(xué)習(xí)可知f[l][le 閱讀全文

摘要： ST表 一、引入 如何解決區(qū)間最值問題？ 最容易想到的就是暴力枚舉，但是很明顯，速度過于慢，所以引入ST表 二、ST表 我們令f[i][len]表示以i開頭長度為1<<len的最大值 由此可以突出初始值為f[i][0] = a[i] 接下來思考轉(zhuǎn)移，我們就是要把f[i][len]拆成兩個更容易就覺得 閱讀全文

摘要： T1， 一看就看出來了這道題用不到任何算法，直接模擬即可，大概花費了5分鐘來讀題以及打代碼，結(jié)果樣例WA了，再次閱讀題目發(fā)現(xiàn)少判斷了P與N的情況，然后改了，總的來講花了10分鐘作業(yè) T2， 通過他給定一個區(qū)間想到了前綴和的做法，這樣的時間復(fù)雜度就大大降低，輕松AC T3，T4 這兩道題都比較容易沒什 閱讀全文