2007年4月8日。
校賽第二場正式開鑼。
在師傅,大哥等人的祝福中走入賽場.呵呵~
前一天早早準(zhǔn)備到OJ上面切菜題積累RP 以備第二天爆發(fā)爆發(fā) 呵呵~
第二天下午 在第一次使用pc^2的環(huán)境下（很興奮）比賽正式開始
比賽前期發(fā)揮的不錯(cuò) 后期比較急
覺得ZZN組織比賽的時(shí)候嚴(yán)肅的神情特別好玩

比賽過程：(比賽采取個(gè)人賽的形式 4小時(shí)）
開場立刻開始翻開鍵盤下的試題開始看 第一題 hang over比較簡單 4分鐘左右提交了第一個(gè)題 順利得到AC 接著是第二題 Divisibility 非常典型的DP 但是要注意求余的時(shí)候產(chǎn)生負(fù)數(shù)要處理一下 不要runtime error
大概15分鐘左右順利1Y 此時(shí)翻了翻board alpc05排第一 我第二 看了看C題 Onion layer 比較長 跳過 D題 Bubble Map 長 跳過 看了看E題Persistent Numbers 高精度 求余除法的題目 可能稍微有點(diǎn)麻煩 先跳過 于是來到F題 Shuffle'm up 非常好寫的一個(gè)模擬題 于是決定拿這個(gè)題目開刀 劈哩啪啦一頓亂敲之后 做了一下數(shù)據(jù)測試 發(fā)現(xiàn)對(duì)于無解的情況時(shí)間判斷的時(shí)間比較長 立刻加了一個(gè)50000的上界限定 順利1Y 此時(shí)已經(jīng)到了board 第一 第二名與我只有10 minutes的罰時(shí)差距 這個(gè)時(shí)候回去做E題 敲的過程中遇到一個(gè)小問題 在求完約數(shù)的時(shí)候 是必須要對(duì)一些諸如3*3=9這樣的約數(shù)重新組合成9的 要專門做一個(gè)組合么？實(shí)際上不用 如果從9->2的方向求 則可以盡可能先把9約出來 就不存在3*3這樣的組合了 OK 提交 幾分鐘之后 返回WRONG ANSWER 一看 突然發(fā)現(xiàn)自己提交錯(cuò)了文件...提交成了E.plg文件..faint!!!看來對(duì)pc^2還沒完全適應(yīng) 換個(gè)文件提交 順利AC 翻開G題Binary Search Heap Construction 發(fā)現(xiàn)是treap的題目 由于從來沒有敲過treap 決定先放放 來到最后一題 Dictionary 是一道簡單題 于是開始做 題目比較陰險(xiǎn)紙上輸出的標(biāo)準(zhǔn)輸出是".."但是要求程序輸出"  ",整理wrong answer一次 改過之后順利AC 5題 此時(shí)在題數(shù)和罰時(shí)上都領(lǐng)先很多 之后server出了一些問題 后來又修復(fù)好 這個(gè)時(shí)候翻過試題 開始做G題 理解題目意思理解了挺久的 看懂了之后還是決定放放 于是看C題 題目意思就是一層一層求凸包 求得最后要多少層凸包就可以了 由于很久沒有寫凸包的程序了 沒有AC的信心 還是放放 來到D題 剛開始題意理解錯(cuò)了 寫了一個(gè)相當(dāng)復(fù)雜的程序提交 wrong answer 于是正式投奔G題 用string霹靂啪啦敲完提交得到TLE之后 把string換成了C風(fēng)格還是TLE 不斷的做各種各樣的優(yōu)化始終TLE 這個(gè)時(shí)候比較煩了 回頭再去看D題 發(fā)現(xiàn)原來理解錯(cuò)了 改來改去越改越亂 這個(gè)時(shí)候發(fā)現(xiàn)時(shí)間只剩下30分鐘了 靜不下心來寫D題 始終想到G題過掉 于是最錯(cuò)誤的決策就是最后30分鐘在G題上面孤注一擲 直到比賽結(jié)束仍然是5題 1人7題 2人6題 我因?yàn)榱P時(shí)的優(yōu)勢排在第4 由于1等獎(jiǎng)有5名 還是拿到了1等. 記得我問GF 想要我比賽拿什么成績 她說拿一等就好了 那總算沒有讓她失望 呵呵~~
解題小報(bào)告:
A:hang over 直接計(jì)算1/2+1/3+..1/n的值 由輸入順序或二分判斷即可
B:Divisibility 我的DP方式是a[i][j] i代表從0..i的數(shù)的+-組合，j代表組合出來的數(shù)對(duì)K的余數(shù) 注意一些負(fù)數(shù)的錯(cuò)誤 我的方式是讀入的時(shí)候?qū)取余（求出來還要將負(fù)數(shù)轉(zhuǎn)正） DP的時(shí)候限定下標(biāo)為0...k即可
C:Onion layer 一層一層凸包求取即可
D:Bubble Maps 相當(dāng)簡單的一題 比賽時(shí)沒有做出來太可惜 由題意可知 比如p的上面一定是s 所以直接將p改成s就可以了 注意邊界情況要回溯搜索 比如pp的上面就要改成ss再回溯到上一層
E:Persistent Numbers:高精 對(duì)9->2去除 相當(dāng)于到一個(gè)分解式 最后排序 從小到大輸出即可 無解的情況是無法分解成9...2的組合 注意各位數(shù)的特殊情況 要特殊判斷輸出
F:直接模擬+上界判斷(我以為hash會(huì)超時(shí) 實(shí)踐證明 這個(gè)題目的數(shù)據(jù)在hash下面并不會(huì)超時(shí))
G:題目意思是根據(jù)節(jié)點(diǎn)構(gòu)造Treap 最大節(jié)點(diǎn)數(shù)50000 LSM解釋說要笛卡爾樹 不懂...
H:從上到下輸出Min(應(yīng)該輸出的點(diǎn)數(shù),p[i-1]+1)就可以了 注意輸出空格
隨便侃侃：
說說自己吧 其實(shí)覺得自己是那種總喜歡做自己喜歡的題目的那種人 題目要對(duì)胃口就舒服 不然就容易茫然
我最喜歡的是圖論（樹啊等等都是） 其次是DP 最不喜歡的是計(jì)算幾何和比較復(fù)雜的數(shù)論題
看來以后要改改自己的毛病 要多做做自己沒有做過的題目和有挑戰(zhàn)性的題目
其實(shí)一直都想成為做難題的角色 結(jié)果總是發(fā)現(xiàn)自己成為弱題清掃工
看來要換換口味了
呵呵~ 校賽結(jié)束 新的生活開始!