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