置頂隨筆
#
2013年1月10日
#
2012年11月13日
#
其實(shí)是對最后一年NOIp的吐槽吧. 初賽后有若干個(gè)理由支持我去或不去, 有個(gè)理由是給Juda送書. 哦, 我應(yīng)該偽裝的高尚一點(diǎn), 其實(shí)是去見證歷史的亂象的, 最后一年保送的最后一門. 回來以后發(fā)現(xiàn), 還有個(gè)理由, 自費(fèi)旅游放松心情(好吧我是來觀賽的…
雖然最想見的人都沒去, 代碼能力各種退化, 目測不寫掛就二等, 不過怎么樣就怎么樣吧……
Day0
轉(zhuǎn)車是種奇怪的事情, 不過深圳北站和廣州南站都實(shí)在是很張狂的現(xiàn)代建筑, 空間非常寬廣, 置身其中會(huì)深深的體味到自身的渺小.
似乎凡是帶了"和諧號(hào)"的車, 似乎都是可以提前上車的. 聽父親講, 像我這么大的時(shí)候, 買站票, 跟人去餐車蹭座位…制度尚未形成, 或者在變革途中的年代, 其實(shí)更容易產(chǎn)生豐富的人生經(jīng)歷, 倒是現(xiàn)在這樣, 四平八穩(wěn), 更多的是平淡的味道. 輕軌這玩意明明就是城際地鐵, 但是少了幾分靈活, 出來之后摩的這個(gè)多……
雅居樂酒店我怎么覺得外墻有種歐式風(fēng)格, 同房間的老師居然是四會(huì)的…然后發(fā)現(xiàn)5F幾乎被深圳眾占領(lǐng)了. 出去逛了一圈, 還有個(gè)大媽把她哭鬧的孩子往我這邊推, 說”我不要他了”, 當(dāng)時(shí)我就____, 我長得這么像大叔么(
酒店外面的桂花很香, 不是有句話叫”金秋十月, 丹桂飄香”么, “回憶像一場艷麗煙火, 伴隨著喜怒哀樂終究要散落”, 倒是隱隱約約記起去年自己一個(gè)人在紀(jì)中逛了一圈. 出門走了一段, 在某個(gè)路口突然覺得有些時(shí)空錯(cuò)位, 隱隱約約的覺得像是太原. 走了很久, 直到人困馬乏, 在一條長長的河旁的堤岸邊上散步. 印象最深的是一所小學(xué), 進(jìn)去有座門樓, 同樣是校友捐贈(zèng), 滿滿的歷史的痕跡, 背后漆噴上去的字實(shí)在是很不應(yīng)景. 小學(xué)的門口是形形色色的文具店小吃店各種才藝培訓(xùn), 接孩子的家長幾乎都騎著摩托.
晚上和深圳眾出去吃飯, 和chj師弟以及深外的yy去扯淡了, 對著某份一堆超綱知識(shí)點(diǎn)的大綱評頭論足一番, 結(jié)果后來各種超綱. = =||| 給Juda神牛送書, 然后被涮了嗚嗚嗚嗚, 雖然Juda那么像初一的小盆友.(> <) 然后晚上就和知遠(yuǎn)兄談理想談人生談愛情去了, 其實(shí)熟識(shí)的人都挺像的, 明明專心致志在別的地方, 結(jié)果文化課就莫名其妙的考好了, 除了文理, 其實(shí)兩個(gè)人太像了. 或者說, 本來就不該區(qū)分文理, 希望他博雅杯能過吧. 最終晚上只復(fù)習(xí)了怎么寫gen和對拍器.
Day1
一上車就看到盧牛以及身邊的妹子, 不科學(xué)……
一進(jìn)去就在寫gen和對拍器, 然后寫讀入, 然后就開場了. 密碼和實(shí)事結(jié)合很緊嘛. 讀題很慢, 但是沒有像去年一樣, 寫了滿滿一頁的題目要點(diǎn). P1是個(gè)很水的字符串, 不過據(jù)說兩位省隊(duì)跪掉了(>_)<). P2是<局部調(diào)整法在信息學(xué)競賽中的應(yīng)用>的例題, 只要想到貪心的話, 60%, 然后要寫單精乘除. 當(dāng)然, 作為低智商選手, 我花了40min最終YY出來二分+集合狀態(tài)轉(zhuǎn)移, 40%, 當(dāng)然沒寫……P3的裸模擬50%, 預(yù)處理一下70%……Day1以100+20+50告終(要是寫跪了呢 T_T)
下午在看某部很奇怪的電影…果然帶了什么都不會(huì)干正事, 一直在刷機(jī)……其間拜讀了clj的題解. 以及聽prof.guo講了半個(gè)小時(shí), 包括復(fù)賽名額如何決定, GDOI/GDKOI可能的變化etc, 其間東莞的教研員由于郵箱查看不及時(shí)被點(diǎn)名批評”不做事”, 我大深圳就呵呵呵呵吧. BTW, 第一天實(shí)在各種熱, 于是就把衣服留在401了, 還去麻煩了moreD大神……跟wx神牛各種短信若干, 其實(shí)他可以和cxq一樣來觀賽嘛 >_<
晚上繼續(xù)頹廢, 看完conan, 聽知遠(yuǎn)兄給的*.wav, 聽了一半被Juda拉下去面基, 然后被他們的小朋友膜拜…于是…于是…Day2果然就跪了(
Day2
進(jìn)去以后繼續(xù)敲gen和對拍器, 一看題就跪了. p1是擴(kuò)展歐幾里得, 當(dāng)時(shí)一看是不定方程, 變形以后果斷裴蜀定理, 易知a,b互質(zhì), 然后就不會(huì)了……可以知道x<=b, 雖然后面想到輾轉(zhuǎn)相除, 但是沒多想一步, 對于2的冪次觀察到x為a%b或b-a%b, 對于a-b=1或2的情況得到了結(jié)論, 不過不能推廣, 數(shù)學(xué)渣啊… = =||| p2 30%是二逼模擬O(NM), 想了10min就發(fā)現(xiàn)可以二分+BIT, O(NlogMlogN)不過只能70%, 但是BIT/zkw線段樹都不會(huì)寫了, YY了半天沒YY出來. 好吧據(jù)說正解又是前綴和+二分, 作為去年A了那題的群眾我哭了. P3一上來就想到LCA, 大概可以O(shè)(N^3)搞出任一點(diǎn)對距離, 但是軍隊(duì)實(shí)在不知道怎么移動(dòng)……最終特判了0和-1, 希望數(shù)據(jù)比較科學(xué)兩個(gè)點(diǎn)都有. Day2大概60 + 30 + 10(20?), 兩天加起來270吧, 目測一等線300-330, 求二等 T_T
目測今年深圳兩個(gè)一等的樣子, 看他們寫跪多少吧……
回來的路上終于看完TBBT, 艾米又在體現(xiàn)”女孩子好麻煩”了…路上看到zxk的感傷段子, 作為見證歷史的觀眾, 我覺得大可不必如此悲觀, 至少我還是相信歷史的車輪會(huì)滾滾向前的.
一個(gè)人去, 一個(gè)人回, 孤獨(dú)落寞的征途果然如此么.
2012年10月28日
#
10.22
P1326, SPFA.
最短路模板題
P2022, 模擬.
維護(hù)長度為N的序列即可, 對于每個(gè)操作注意細(xì)節(jié).
P2017, 搜索
貪心上界, 累加下界, 中間暴搜. 昨天打漏了\sum C_i的初始化, 把C_i和A_i打混了.
*據(jù)說數(shù)據(jù)弱到直接交下界就A
*需要復(fù)習(xí)下gen怎么寫了
P2021, 位運(yùn)算+DP
and, 統(tǒng)計(jì)連續(xù)的1, 直接計(jì)算
or, 統(tǒng)計(jì)連續(xù)的0, 間接計(jì)算
10.27
Vijos Monthly Oct12
P1742, 模擬.
平均數(shù) 加權(quán)累加即可;
中位數(shù) qsort排序, 按照奇偶分類輸出;
眾數(shù) 排序后累計(jì)不同的值和出現(xiàn)次數(shù), 排序輸出;
P1745, 貪心?
數(shù)據(jù)范圍否定了DP, 但是作為貪心范圍確實(shí)有點(diǎn)小. 按照切割的權(quán)w_i排序, 如果w_i相等, 則行/列多的先切. 排序后累加即可.
如果f[i][j]來dp的話, 大概是O(N^3)的時(shí)間, O(N^4)的空間...
-> 很好, 爆longlong了...T_T
P1746, 圖論.
最短路變形, N = 300. 直接利用Floyd得到所有最短路, 對于一對u,v, 分別枚舉N個(gè)節(jié)點(diǎn), min{G[u][i] + G[i][v]}即為所求.
P1747, ?.
30%明顯是搜索, 但是我實(shí)在不會(huì)暴力了, 連方向都不知道. 我想起來今天AIME那幾個(gè)暴力算的圓...
*對于算法, 在實(shí)現(xiàn)前必須充分討論細(xì)節(jié). 在實(shí)現(xiàn)過程中修改細(xì)節(jié)及其浪費(fèi)時(shí)間.
*對拍 & 特別小數(shù)據(jù)的構(gòu)造需要復(fù)習(xí), 正確率.
*各類算法模板的整理.
-> 150/300, 實(shí)現(xiàn)能力啊啊啊啊
http://www.vijos.org/Discuss_Show.asp?DisID=55613
10.28
Vijos T1062, 實(shí)在沒動(dòng)力寫, 就YY了一下(...
P1, 十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制小數(shù)
不會(huì)...乘二取整法套不上
P2, ?
只會(huì)暴力做法, O(N!)生成序列, 然后根據(jù)約束條件剪枝, 譬如:
(1) 賀卡的時(shí)間順序
(2) 每個(gè)人的時(shí)區(qū)互異性
(3) 時(shí)間范圍
其實(shí)手算可容易了...(
P3, 模擬
[70%做法]
(1) O(N^2)把每個(gè)區(qū)域蓋房子的權(quán)值預(yù)處理一遍
(2) 蓋N次房子, 每次掃一遍找最小值, 然后標(biāo)記相關(guān)區(qū)域不可用O(N^3)
*可能的房子數(shù)量上限好像是大于N的 ...
[AC做法]
(1) O(N^2)把每個(gè)區(qū)域蓋房子的權(quán)值預(yù)處理一遍
(2) 把每個(gè)區(qū)域的權(quán)值升序排序, 依次選擇, 對于選中的區(qū)域, 標(biāo)記其周邊區(qū)域不可用, 復(fù)雜度O(N^2)
2012年10月22日
#
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)
只寫了1.5h, 看了題就果斷敲暴力了, 自己沒出數(shù)據(jù), 沒對拍, 沒手感......
40 + 10 + 0...明晚回來看題解, 果然NOIp裸考掛定了...
P1[簡單數(shù)學(xué)]
注意到序列里的U和D只要合法就可以移動(dòng), 所以對字符串st計(jì)算高度的變化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>
用數(shù)組記錄每個(gè)beautiful words的長度和起止字母, 然后用O(N^4*M)來暴力枚舉.
<暴力做法2>
對于每個(gè)beautiful words, 從頭掃一遍記錄前綴長度, 從后面掃一遍記錄前綴長度, 然后記錄長度大于該beautiful words的字符串?dāng)?shù)量, 累加即可. 復(fù)雜度O(N^2*M).
<AC做法>
同暴力做法而, 不同的是由于使用了KMP所以復(fù)雜度變成O(NM)
P3[_____]
根據(jù)樣例, 如果一對元素A_i, A_j需要操作的話, 必然滿足A_i ^ A_j > max{A_i, A_j}. 于是當(dāng)任何一對A_i, A_j都不能被操作時(shí), \sum_{A_i}最大,
然后由于還有15min了, 我就果斷敲回溯暴力了...
AC做法是高斯消元然后亂搞...看不懂
10.20
鑒于是恢復(fù)狀態(tài)的訓(xùn)練, 而且AC做法全都沒學(xué)過, 出于給生活以情趣的目的......看了題解就算了......
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/線段樹在O(NlogN)的時(shí)間里得到所有區(qū)間的操作結(jié)果, O(N^2)枚舉. 特別地, xor滿足區(qū)間減法, 可以直接O(N^2).
[O(NlogN)做法 by Juda]
(1) and
對于元素A_i, f[i][j]表示A_1...A_i的第j個(gè)二進(jìn)制位中連續(xù)為1的個(gè)數(shù), 累加即得.
(2) or
對于元素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ì)] 對于A_1 xor A_2 xor ... xor A_n, 考慮第j位, 若有奇數(shù)個(gè)1則為0, 反之亦然.
對于元素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
一開始讀題以為是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á)到下界或超過上界馬上剪枝.
*只過了一個(gè)點(diǎn)...這不科學(xué)!!!!!!!!
P4, communicate, LCA
只會(huì)SPFA...但是這個(gè)范圍!!!一看就不是NOIp題(
*明天晚上抽2h調(diào)一下吧...還要寫PS...
2012年10月13日
#
第四年參加NOIp, 大概是四年來壓力最小的一次.
和CPhOp預(yù)賽地點(diǎn)一樣, 不同之處在于NOIp初賽人很少, 教室只占了一層樓. 沒有蜂擁而至的人群, 亦沒有死守在樓梯口的保安, 連考務(wù)都是各校教練, 不知道可喜還是可悲. 就考前兩天隨手做了兩套題, 也沒復(fù)習(xí)什么東西. 給的成績大概是71.5, 全市第二. 自己對了下答案, 大概是74, 有個(gè)很二的空填錯(cuò)了. 要是和CMOp預(yù)賽的分?jǐn)?shù)換一下, 高中的競賽生涯也算圓滿了.
題目難度加大, 但是風(fēng)格很好, 延續(xù)了10年以來的靈活. 選擇題對知識(shí)量的要求依舊弱, 除了不記得P/NP/NPC的定義還真沒別的識(shí)記問題. 問題求解很難, 第一題是數(shù)理邏輯背景, 看不懂題意. 第二題大概是類似tree dp的組合計(jì)數(shù), 很久沒碰了, 沒做. 閱讀不難, 第一題是去掉一個(gè)最低分去掉一個(gè)最高分算均值, 第二題是統(tǒng)計(jì)n的正因子個(gè)數(shù), 第三題是n-n的二進(jìn)制表示中1的個(gè)數(shù), 第四題是給個(gè)先序和中序, 然后畫出樹來加權(quán). 完善第一題是暴力搜索例題, 眼殘了一個(gè)填空. 第二題有點(diǎn)意思, 但是由于很久沒敲過題了, 果斷只對了兩個(gè)空. 大概一年前的水平是可以解出來此題的.
該干什么干什么吧.
2012年5月28日
#
上周四研究有多套系數(shù)的氧化還原反應(yīng)方程式配平的時(shí)候, 遇到了多元線性方程組求解的問題, 不過似乎書上寫掛了(應(yīng)該寫通解, 而書上只給出了一個(gè)特解). 另外一個(gè)可能遇到的應(yīng)用,是, 在電路問題中, 結(jié)合歐姆定律和基爾霍夫定律暴力求解. 當(dāng)然, 平時(shí)用的最多的是利用二階行列式求解系數(shù)較為復(fù)雜的二元一次方程, 比如高考解析幾何大題.
大概是對于wikipedia上概念, 結(jié)合個(gè)人認(rèn)識(shí)的一些重述, 實(shí)在不是便于理解, 僅供復(fù)習(xí):
[線性方程組的矩陣表示] A \times a = b. 矩陣乘法的一個(gè)應(yīng)用是求解線性遞推數(shù)列, 可以利用快速冪將復(fù)雜度降至O(logN).
[Rank(秩)] 線性無關(guān)的列的個(gè)數(shù), 對于n元線性方程組, 僅當(dāng)秩r = n時(shí)恰有一組解. r > n時(shí)無解, r < n時(shí)有無數(shù)組解.
[Gaussian Elimination(高斯消元法)] 通過不斷消元, 使得方程組中每個(gè)方程的元的個(gè)數(shù)逐個(gè)遞減, 等號(hào)左邊呈三角形狀, 自下而上代入消元即可. 具體操作時(shí), 對于方程f_1(x_1, x_2, \cdots, x_n) = 0, f_2(x_1, x_2, \cdots, x_n) = 0, 令f_2(...) = f_1(...) + \lambda f_2(...). 手算的話, 消元方向很明確,
對于N元線性方程組, 時(shí)間復(fù)雜度為O(N^3). 更好的做法是共軛梯度法, 時(shí)間復(fù)雜度為O(N^2). NOIp 2004的蟲食算的AC算法可以使用Gaussion Elimination.
[Cramer's Rule(克萊姆法則)] 二階行列式解二元一次方程組的理論依據(jù).
x_i = \frac{D_i}{D} (1 \leq i \leq n), D = det(A). D_i = det(A_i), 即把矩陣A的第i列換成矩陣b. 顯然當(dāng)D為0時(shí)線性方程組無解. 對于N元線性方程組, 時(shí)間復(fù)雜度為O(N!).
[Least Squares(最小二乘法)]參見選修2-3, 推導(dǎo)有一定技巧性, 但是我已經(jīng)忘完了 >_<. 值得一提的是, 發(fā)現(xiàn)者是Gauss和Legendre, 存在發(fā)現(xiàn)先后的爭論, Legendre的肖像居然和同名法國政治家的肖像混用了一個(gè)多世紀(jì)(參見維基), 不過發(fā)現(xiàn)者是如何的淡騰. = =|||
[Cross Product(叉積)] 可以通過向量矩陣和(i, j, k)的乘法計(jì)算, 通過右手定則判定方向. 比較簡單的用途是計(jì)算立體幾何中的法向量(口算), 以及安培力和洛倫磁力的方向確定.(不過高中教材中介紹左手定則判定方向, 分離了矢量的方向和大小).
考慮向量a, b, 存在|a \times b|^2 + |a \cdot b|^2 = |a|^2 \ cdot |b|^2, 這個(gè)結(jié)論被稱作Lagrangian Identities(拉格朗日恒等式).
立體幾何一個(gè)的應(yīng)用在化學(xué)的晶體結(jié)構(gòu)中, 比如正四面體CH_4, 鍵角為arccos{-1/3}. 如果嘗試思考不同學(xué)科之間的聯(lián)系, 會(huì)發(fā)現(xiàn)很多意想不到的結(jié)論, 往往可以通過其他學(xué)科淺顯的結(jié)論, 來解釋另一學(xué)科中難以求解的問題. 令人唏噓的是, 一些原本淺顯的聯(lián)系并沒有在高中教學(xué)中被體現(xiàn). 也許可以嘗試收集這樣的聯(lián)系, 何況生活原本是充滿樂趣, 可我們卻停留在了乏味而抽象的表層.
2012年5月4日
#
不管怎么說還有個(gè)三等, 退役了, 隨意了. 只是深圳又從B類市掉到C類市, 大概是對不起是后人了. 看著wx神牛最后一年掛了, 嘆息而已.
[Day0]
發(fā)現(xiàn)宿舍比較坑爹. 晚上看tree dp無能, 翻了一下前幾天的problist和白書, 找wx神牛要了SCC模板, 結(jié)果瞬間理解了. 只是沒學(xué)習(xí)BCC, 機(jī)緣巧合? 教ylt SPFA的數(shù)組模擬鏈表實(shí)現(xiàn). 和深中眾去逛二中, 發(fā)現(xiàn)二中各種花前月下, 各種幽靜之處. 沒延續(xù)NOIp和GDKOI Day0亂逛的習(xí)慣. 真是些語無倫次的描述.
[Day1]
今天題目描述異常簡潔, 于是讀題的過程同樣非常迅速, 但是幾乎沒有題目進(jìn)行了深入的思考. P1一看就是暴搜, 一開始卻算錯(cuò)狀態(tài), 以為是O(3^N), 于是認(rèn)為GDOI難得出了一次送分題. 后面越看越水, P2暴力30, 似乎可以用tire. P3 無思路, 似乎是雙連通分量, 但是考前復(fù)習(xí)的時(shí)候排除了. P4是數(shù)學(xué)題, 直觀的想法是打表找規(guī)律. P5題目描述很長, 開始沒看.
P1的DFS打錯(cuò)了多次, P2的字符串排序也打錯(cuò)了多次, 而且由于rank數(shù)組寫錯(cuò), 直接爆零. 很明顯應(yīng)該看清題目, 此次的樣例調(diào)試性較好, 若調(diào)試性較差可能引起更大的問題. P4先打了暴力生成, 然后發(fā)現(xiàn)30%的速度非常快, 只是單獨(dú)考慮各個(gè)位, 想通過某個(gè)特征數(shù)字確定答案. 事實(shí)上應(yīng)該求和, 所的序列單調(diào)增, 然后可以通過二分得到答案, 于是可以過50%. P3想了20min, 結(jié)合數(shù)據(jù)范圍用Floyd YY了一個(gè)錯(cuò)誤的貪心, 騙了25分, 大概是改成等權(quán)圖, 對于度為1的點(diǎn), 成對連接距離最大的兩個(gè). P5可以看出要使用狀態(tài)壓縮, 但是實(shí)在想不出方程. 之后在P5的暴力, 死磕P1, P4之間猶豫. 最終選擇死磕P1, 利用直角三角形的性質(zhì)，枚舉不妨或放在任意兩邊. 可以利用背包判斷第三條邊是否存在，復(fù)雜度$O(3^N \cdot N^2)$, 但是之后復(fù)評發(fā)現(xiàn)是錯(cuò)的. 做法完全正確只是DFS多寫了一行. 這大概是我參加了三次GD字頭的比賽，為數(shù)不多的在現(xiàn)場想出AC做法的題目. 由于第二題對于樣例的大意, 丟了30%.
最終結(jié)果: 135 = 70 + 0 + 35 + 30 + 0
中午由于wx打算講題, 于是又萌生了錄像的想法. 下午還上去醬油了一下, 盡管講錯(cuò)了.某天晚上腦子一抽，發(fā)現(xiàn)做法其實(shí)是對的，但是我手賤把$O(3^N)$寫成了$O(4^N)$. 復(fù)評的時(shí)候有幸見到了wqc同學(xué). 晚上除了整理視頻就是各種頹廢, 大概和神牛看了一集新的TBBT.
[Day2]
前一天晚上心情低落, 一直延續(xù)到今天. P1是數(shù)據(jù)結(jié)構(gòu), 目測可做. P2數(shù)據(jù)結(jié)構(gòu). P3 DP. P4 搜索. P5 博弈論. 寫了P1的60%, 很顯然的數(shù)組模擬, 數(shù)據(jù)范圍比較厚道. 但是想AC算法一直想利用vector和維護(hù)坐標(biāo)偏移, 思路完全南轅北轍, 實(shí)際上對于每種顏色應(yīng)該分開考慮, 用0/1表示該點(diǎn)是否存在, 利用BIT維護(hù)區(qū)間和. 或者進(jìn)行離線處理. 也不見得想不出來, 考前幾乎沒有進(jìn)行BIT的模型識(shí)別, 結(jié)果如此也是可以預(yù)料到的. P2在最后1.5h寫了O(N^4 \cdot M)的暴力查詢, 用二維BIT查詢矩陣和, 大概能過若干個(gè)測試點(diǎn), 結(jié)果全崩潰了, 原因不知. 正解大概是轉(zhuǎn)化成線段樹, 前幾年有個(gè)類似的題目. P3對于30%算法寫了SCDP, 但是沒調(diào)出來, 原因未知. 正解大概是對于條件進(jìn)行簡單的分析后, 轉(zhuǎn)化為背包模型, 可以通過50%. 然后利用偏序關(guān)系優(yōu)化. P4 20%可以一遍BFS得出結(jié)果, 但是沒寫; AC做法大概是狀態(tài)壓縮BFS. P5 20%可以記憶化搜索, AC算法思維難度極大, 現(xiàn)場只有盧神A了.
最終結(jié)果: 60 = 60 + 0 + 0 + 0 + 0
中午和tzz聊了聊, 覺得深圳14er的OI還是挺有希望的…只是下午就被攆回家了, 草草開局, 草草收尾, 如此而已.
考前問段神如何準(zhǔn)備, 段神說”我是反面教材”, 令人唏噓的是, 我大概成了反面教材2.0. 考前速成STL和數(shù)據(jù)結(jié)構(gòu), STL用了<pair>, BIT學(xué)的比較多, 但是最終沒搞出模型. GDOI和GDKOI一樣, 幾乎看不出任何非顯然的東西, Day1的狀態(tài)有點(diǎn)莫名其妙, 策略比較正常, Day2異常低落, 使用了很奇怪的策略, 于是裝13裝過頭了, 數(shù)據(jù)結(jié)構(gòu)磕傻了, 集合狀態(tài)DP從未寫過卻在考場上YY. 其實(shí)是新一輪的瓶頸期, 思維能力不適應(yīng)知識(shí)量, 代碼能力差強(qiáng)人意. 反正NOIp之后就放棄了. 結(jié)局如此, 意料之外, 情理之中, 差強(qiáng)人意.
其實(shí)還是太弱了, 思維局限很嚴(yán)重, 訓(xùn)練方式同樣存在盲點(diǎn). 起步太晚同樣是一方面, 結(jié)局如此, 也罷, 也罷.
退役了, 一段生活的結(jié)束, 也許是暫時(shí)的離開, 也許是永遠(yuǎn)的離開.
一局終了, 從開始到結(jié)束經(jīng)歷了三年, 挺長的.
2012年5月1日
#
高中OI生涯結(jié)束. 可能是暫時(shí)的離開, 或是永遠(yuǎn)的離開. 也許會(huì)寫一篇東西紀(jì)念.
大概是初三以來的代碼, 按照日期整理, 可以對照Problem List. 題目的話, 參看Problem List上的來源吧:
/Files/Climber-pI/code.7z就這樣了. 保送生考試, CMOp 2012.
等待著塵埃落定.
3.31
(1) 如何確定對那些題目進(jìn)行深入思考
(2) 即使全打暴力不見得打得完
(3) 數(shù)論?
(4) SC DP?
GDOI 2011 Day1分析[未實(shí)現(xiàn)]
P1, 直接模擬, AC.
P2, 生成子集+高精變形, 8
P3, 暴力模擬, ?
P4, 快排, 4
P5, 暴搜, 12
大概是40 + 8 + ? + 4+ 12 = 64.
4.7
US Open Silver Division, 2h, 未實(shí)現(xiàn)
P1_unlock[DFS-ID + 二分]
[Brief]
在10*10的方格中, 有三個(gè)連通塊, 對于每個(gè)連通塊可以向四個(gè)方向移動(dòng), 求使得三個(gè)連通塊互不相鄰所需的最小移動(dòng)次數(shù).
[Solution]
---------|
-++++++++|
--------+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|||
分析:
(1) 大概最小移動(dòng)次數(shù)的最大值不會(huì)超過20, 如上圖. 移動(dòng)次數(shù)的上限大概略大于 相連的邊數(shù)/2.
(2) 可以發(fā)現(xiàn), 每次的決策必然小于3*4 = 12種, 可以利用一次Floodfill得到不同連通塊之間的相接關(guān)系, 顯然只有相對方向有一方相連, 或者均不相連的部分可以移動(dòng).
可能的優(yōu)化:
(1) 兩個(gè)相連的連通塊, 向相反方向移動(dòng)是互相等價(jià)的.
(2) 若在某個(gè)方向能夠移動(dòng)的話, 一次移動(dòng)到位.
*復(fù)雜度很難分析, 應(yīng)該能通過大部分測試數(shù)據(jù).
P2_bookshelf[DP]
[Brief]
給定N個(gè)長為W_i, 寬為H_i的書, 書的放置必須按照給定順序, 每層的長度限制為L, 試求書柜高度最小值.
[Solution]
很明顯是O(N^2)的動(dòng)態(tài)規(guī)劃, 但是我只想到了O(N^2*L)的, 似乎是有限制的背包問題.
[狀態(tài)] f[i][j][k]表示放了i本書, 在第j層, 該層剩余寬度為k的最小值
[方程] 略, 討論第i-1本書放在哪層即可.
*正解可能通過單調(diào)隊(duì)列或是別的手段降維, 也可能是重新設(shè)計(jì)狀態(tài).
P3_running[數(shù)據(jù)結(jié)構(gòu)]
[Brief]
N頭牛, 跑L圈, 圈長C. 給出每頭牛的速度v_i, 求跑的最快的牛到達(dá)終點(diǎn)是, 牛群中超車了多少次.
[Solution]
正解復(fù)雜度大概是O(NlogN).
可以知道T = C*L / max{v_i}, 然后對于每頭牛i跑了C_i = T*v_i/C圈, Σ[C_i-C_j]即為答案. 復(fù)雜度O(N^2).
大概可以總結(jié)幾點(diǎn):
(1) 對題目的分析能力顯著下降
(2) 實(shí)現(xiàn)能力是個(gè)問題
(3) 如何恰當(dāng)?shù)膶ε? 減少時(shí)間成本, 又不損失正確率
4.9
GDOI 2011 Day2 分析[未實(shí)現(xiàn)]
P1, 讀題無能, 完全不能找到"瞬移水只能作用于到過的點(diǎn)的描述". 做法是prim+heap或kruskal
P2, 時(shí)間常數(shù)比較大, 很難寫, 不一定能AC
(1) 讀入每部小說后, 對小說中每個(gè)單詞進(jìn)行排序(字典序), 注意不區(qū)分大小寫, O(n*NlogN)
(2) 將排序后的單詞按照順序插入動(dòng)態(tài)數(shù)組(指針/數(shù)組模擬鏈表/vector實(shí)現(xiàn)), O(N)
(3) 按照時(shí)髦值對小說進(jìn)行間接排序, O(NlogN)
(4) 對于每個(gè)詢問, 在每部小說中進(jìn)行二分查找, O(QlogN)
總復(fù)雜度是O(n*NlogN), n = 1000, N <= 20000, 預(yù)計(jì)能通過大部分測試數(shù)據(jù)
P3, 數(shù)論題, AC做法需要用到中國剩余定理, 下面是50%的做法
(1) 構(gòu)造素因子表判斷A的合法性
(2) 對每個(gè)1..N除去因子后, 求乘積末位
(3) 記錄構(gòu)成K的因子的次數(shù), 計(jì)算多余部分乘積末尾
(4) 輸出結(jié)果
復(fù)雜度是O(QN)
P4, 計(jì)算幾何, 這種做法大概能通過大部分?jǐn)?shù)據(jù)
對于每個(gè)方案, 計(jì)算每個(gè)點(diǎn)和其中相連兩點(diǎn)構(gòu)成三角形面積之和(利用行列式), 并檢測點(diǎn)是否在五邊形上, 復(fù)雜度是O(5MN)
P5, treeDP, 看不出來...比較容易想到O(N!)的暴搜
(1) 利用兒子兄弟表示法建樹
(2) 生成N!種順序, 判斷其合法性(利用樹的層次關(guān)系?)
(3) 維護(hù)最小值
可能的分?jǐn)?shù)大概是40? + 40- + 20 + 40- + 12?
考慮實(shí)際情況, 可能是0 + 32 + 20 + 24 + 0 = 76.
于是綜合考慮兩天, 大概是64 + 76 = 140, 差不多二等了. 可能的預(yù)計(jì)是, 題目方向變化, 難度提升.
4.15 ~ 4.28
用CTex寫的, 雖然只是徒勞的努力, 不過也有些初窺門徑的味道. 結(jié)局意料之外情理之中, 倒也罷了. 段神說他是反面教材, 我是反面教材2.0
省賽備戰(zhàn)實(shí)錄.pdf
4.28
一個(gè)idea, 算法模板, 并準(zhǔn)備若干測試數(shù)據(jù), 以測試模板.
2012年3月19日
#
//大概在5周前就寫完忘記發(fā)了, (2)和(3)大概胎死腹中了.
Climber.pI按: 時(shí)隔兩年, 故地重游, 大概是高中OI生涯的第二次GDKOI, 也是最后一次GDKOI, 倒數(shù)第三場正式比賽了. 結(jié)果差強(qiáng)人意, 卻也是意料之中. 也就形式化一把, 隨記二三.
(1) 關(guān)于賽場
大概是前一天晚上一個(gè)人逛中大, 結(jié)果還沒找錯(cuò)了講評的地方 = =|||
Day0
大概就是各種聊天, 各種扯淡…沒敲一行代碼, 所以第二天就NC了
Day1
感覺組織工作比NOIp差很多, 比如進(jìn)去都半個(gè)小時(shí)了才有水喝.
P1是個(gè)DP, 一開始根據(jù)數(shù)據(jù)范圍準(zhǔn)備的判斷了復(fù)雜度, 但是后來鑒于題目的背景, 沒有進(jìn)一步的分析題意. 相反, 聯(lián)想到了USACO Training的job, 二分+貪心經(jīng)典題, 于是YY了一個(gè)貪心. 大概是把所有任務(wù)排序, 然后先選大的, 不能再裝的時(shí)候就選小的, 居然還過了樣例.
但當(dāng)時(shí)對貪心的正確性毫無把握, 于是又寫了O(a^N)的暴搜, 然后對拍. 大概是手生的緣故, 一個(gè)半小時(shí)才全部折騰完, 最終的結(jié)果是貪心錯(cuò)誤. 于是有改寫了一個(gè)小范圍暴搜, 大范圍貪心的程序. 當(dāng)天中午重新看題的時(shí)候, 瞬間發(fā)現(xiàn)題目實(shí)際上是個(gè)變形的背包. 一旦在現(xiàn)場思維走偏, 總是難以挽回, 比如去年初賽, 比如去年Day1P2.
這時(shí)候有種奇怪的感覺, 時(shí)時(shí)刻刻想著放棄卻又不敢放棄, 完全不能控制比賽進(jìn)程, 只能順著身體的慣性寫題. 很像初中的時(shí)候跑1500的感覺, 帶著種無法預(yù)知的恐懼.
P2是最短路, 由于邊的權(quán)值為{1, 2, 3}其中一個(gè)數(shù), 所以可以拆成若干邊權(quán)為1的邊, 從而用O(3n)的BFS AC.
當(dāng)時(shí)讀題之后認(rèn)為dij+heap可以A, 但是幾乎不記得怎么寫了. 大致估計(jì)了一下, 認(rèn)為SPFA可以過80%, 又擔(dān)心SPFA敲掛, 又多敲了一個(gè)Floyd. 敲完折騰完對拍基本上過了3h了, 結(jié)果一直不同, 最后手工算了一組數(shù)據(jù)發(fā)現(xiàn)是Floyd掛了, 原因不知. 當(dāng)然, 由于只開了80%的范圍, 也無緣享受4s時(shí)限優(yōu)惠了.
P3是個(gè)數(shù)學(xué)題, 當(dāng)時(shí)只有40+min, 果斷放棄. 但事實(shí)上30%的做法可以直接手算打表, 50%的做法可以利用DP, 甚至可以通過記憶化搜索打表AC.
P4是字符串, 由于不記得C++的I/O, 只能用字符數(shù)組敲. 雖然原理絕對正確, 但是最后還是沒調(diào)出來.
于是Day1就結(jié)束了, 41算是意料之中, 值得慶幸的是SPFA沒有寫掛. 和NOIp一樣, 依舊是全市第二, 盡管wx神牛這次102是我的若干倍.
Day2
大概是被Day1嚇到了, Day2晚上回來還是敲了一會(huì)兒代碼. 第二天的組織工作好了很多.
P1是數(shù)學(xué)題. 仔細(xì)讀題之后很快發(fā)現(xiàn)了O(N)的做法, 聯(lián)想到若干次被周期數(shù)列坑了, 果斷找循環(huán)節(jié), 發(fā)現(xiàn)前面一部分并不循環(huán), 而循環(huán)節(jié)一定是N的倍數(shù), 于是果斷從后面找N. 考慮了50%的范圍, 于是找了400N, 于是只過了60%的數(shù)據(jù). 可以證明的是循環(huán)節(jié)長度不超過O(N^2), 但是我并不知道如何證明, 于是12分沒了. 經(jīng)過一番對拍, 時(shí)間已經(jīng)過了近2h了.
P2的標(biāo)準(zhǔn)做法需要用到線段樹/樹狀數(shù)組/平衡樹等高級數(shù)據(jù)結(jié)構(gòu). 讀題之后發(fā)現(xiàn)模擬十分好寫, 但是由于當(dāng)時(shí)考慮不周, 邊寫邊調(diào)浪費(fèi)了很多時(shí)間. 大概是利用一個(gè)數(shù)組記錄某值是否存在, 然后利用數(shù)組模擬鏈表來實(shí)現(xiàn). 終于調(diào)對了之后, 發(fā)現(xiàn)樣例掛了, 特意問了評委30%的范圍是否符合50%的要求, 得到肯定答復(fù)后. 遂放棄此題的進(jìn)一步調(diào)試, 最終過了4個(gè)點(diǎn).
當(dāng)時(shí)還有70min左右, 在P3和P4猶豫了很久, 發(fā)現(xiàn)P4如果用Floyd的話還需要記錄路徑, 實(shí)在不好寫, 遂放棄.
第三題是搜索, 可以利用DP預(yù)處理狀態(tài), 或者充分利用問題性質(zhì), 只枚舉每個(gè)格子需要填否即可. 當(dāng)時(shí)的做法是記錄未填格子的位置, 逐個(gè)枚舉, 如果某行全部枚舉后進(jìn)行可行性剪枝, 最后判斷沒列是否符合題意. 雖然思路絕對正確, 但是一直調(diào)不出來, 在最后幾分鐘突然發(fā)現(xiàn)是初始狀態(tài)打成1了, 應(yīng)該為0, 改了之后, 屏幕一閃, 樣例過了. 最終過了6個(gè)點(diǎn), 僅超時(shí)了兩個(gè)點(diǎn), 有兩個(gè)WA的點(diǎn)多輸出了一組解, 不知道哪里寫掛了.
于是總分就是18 + 16 + 24 = 58, 又是全市第二, xh64第一, wx牛居然直接3分了…
至此, GDKOI的賽程結(jié)束, 在中大西苑一樓大堂看到一等和二等證書發(fā)完卻不見深圳蹤影, 悵然若失之感涌上心頭, 差不多退役了.
(2) 一些人一些事
(3) 亂七八糟的想法