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