10.12
NOIp 2011 初賽, 84; 注意讀題, 思維盲點(diǎn);
10.13
NOIp 2012 初賽, 71.5.
(T_T 2.5分到哪里去了...)
10.19
「Clover IX」杯HE兩校聯(lián)賽(Day1)
只寫(xiě)了1.5h, 看了題就果斷敲暴力了, 自己沒(méi)出數(shù)據(jù), 沒(méi)對(duì)拍, 沒(méi)手感......
40 + 10 + 0...明晚回來(lái)看題解, 果然NOIp裸考掛定了...
P1[簡(jiǎn)單數(shù)學(xué)]
注意到序列里的U和D只要合法就可以移動(dòng), 所以對(duì)字符串st計(jì)算高度的變化dH, 分類(lèi)討論:
1) |h[0]+dH-h[N]| < N-len, 奇偶性相同則有解, 反之無(wú)解
2) |h[0]+dH-h[N]| = N-len, 有解, 且需滿(mǎn)足h[0]+dH >= 0 || h[N]-dH >= 0
3) |h[0]+dH-h[N]| > N-len, 無(wú)解
*要用草稿紙!!!注意考慮各種情況!!!
P2[字符串]
<暴力做法1>
用數(shù)組記錄每個(gè)beautiful words的長(zhǎng)度和起止字母, 然后用O(N^4*M)來(lái)暴力枚舉.
<暴力做法2>
對(duì)于每個(gè)beautiful words, 從頭掃一遍記錄前綴長(zhǎng)度, 從后面掃一遍記錄前綴長(zhǎng)度, 然后記錄長(zhǎng)度大于該beautiful words的字符串?dāng)?shù)量, 累加即可. 復(fù)雜度O(N^2*M).
<AC做法>
同暴力做法而, 不同的是由于使用了KMP所以復(fù)雜度變成O(NM)
P3[_____]
根據(jù)樣例, 如果一對(duì)元素A_i, A_j需要操作的話(huà), 必然滿(mǎn)足A_i ^ A_j > max{A_i, A_j}. 于是當(dāng)任何一對(duì)A_i, A_j都不能被操作時(shí), \sum_{A_i}最大,
然后由于還有15min了, 我就果斷敲回溯暴力了...
AC做法是高斯消元然后亂搞...看不懂
10.20
鑒于是恢復(fù)狀態(tài)的訓(xùn)練, 而且AC做法全都沒(méi)學(xué)過(guò), 出于給生活以情趣的目的......看了題解就算了......
10.21
P1, Preda's queue, 模擬
注意到最多有N次彈出操作, 所以保留N個(gè)元素就好了, 然后模擬即可.
*居然爆零了...這不科學(xué)
P2, signal, 位運(yùn)算+DP統(tǒng)計(jì)
[O(N^3)做法] 直接O(N^2)得到所有區(qū)間
[O(N^2)做法] 可以利用heap/線段樹(shù)在O(NlogN)的時(shí)間里得到所有區(qū)間的操作結(jié)果, O(N^2)枚舉. 特別地, xor滿(mǎn)足區(qū)間減法, 可以直接O(N^2).
[O(NlogN)做法 by Juda]
(1) and
對(duì)于元素A_i, f[i][j]表示A_1...A_i的第j個(gè)二進(jìn)制位中連續(xù)為1的個(gè)數(shù), 累加即得.
(2) or
對(duì)于元素A_i, g[i][j]表示A_1...A_i的第j個(gè)二進(jìn)制位中1第一次出現(xiàn)的位置, 累加即得.
*上述做法可以統(tǒng)一描述為, 自右向左掃描, and/or需要記錄第i個(gè)元素前的元素中第j位第一次為0/1的位置, 2^j * (i - f[i][j] + 1)即為所求
(3) xor
[xor運(yùn)算性質(zhì)] 對(duì)于A_1 xor A_2 xor ... xor A_n, 考慮第j位, 若有奇數(shù)個(gè)1則為0, 反之亦然.
對(duì)于元素A_i, f[i][j]表示A_1...A_i, A_2...A_i, .. , A_i的中有奇數(shù)個(gè)1的序列個(gè)個(gè)數(shù), g[i][j]表示序列中有偶數(shù)個(gè)1的序列個(gè)數(shù), 不斷交換, \sum 2^j * f[i][j]即為所求.
*還是爆零了不科學(xué)...
P3, catclimb, DFS-ID
一開(kāi)始讀題以為是DP, 條件反射想到training里的rocker和GDKOI 2012 Day1P1. 被P2虐了一通之后, 發(fā)現(xiàn)其實(shí)是搜索, 智商這個(gè)拙計(jì)啊....
標(biāo)程給的做法是DFS-ID. 直接\sum{A_i}\N上取整可以得到理論下界, 然后qsort一下{A_i}先取大的再取小的填一下可以得到上界, 直接O(N!)暴力枚舉. 如果達(dá)到下界或超過(guò)上界馬上剪枝.
*只過(guò)了一個(gè)點(diǎn)...這不科學(xué)!!!!!!!!
P4, communicate, LCA
只會(huì)SPFA...但是這個(gè)范圍!!!一看就不是NOIp題(
*明天晚上抽2h調(diào)一下吧...還要寫(xiě)PS...