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