Posted on 2012-03-16 20:56
Mato_No1 閱讀(2054)
評論(0) 編輯 收藏 引用 所屬分類:
COCI
【背景（神犇不要鄙視）】
前段時間，本沙茶在捉神馬題都被完虐的情況下，發現了COCI……一看，發現里面有相當數量的水題，于是就去捉了……結果，本想體驗虐題的感覺，可還是被里面的一些神犇題虐了……我太沙茶了，沒臉見人了囧……
COCI官網2011~2012 #1：
jabuke: 超級大水題；
matrix：超級大水題，不過本沙茶一開始看疵題了……
x3: 水題，直接對每一位單獨考慮即可；
ples: 水題，裸DP；
sort: 這個題看上去很不好搞囧……但注意題目里面的這個條件：一開始各極大遞減子序列的長度均為偶數（也就是均>1），這樣，第一次模擬一遍以后，剩下的極大遞減子序列就只有長度為2的了，這時每個數要歸位需要與其后面所有比它小的數都交換一次，所以結果就是第一次模擬的rev執行次數加上第一次模擬之后的逆序對總數；
skakac: 神犇題，因為涉及比較難的知識點，本沙茶暫時不會搞囧……
2011~2012 #2：
najboljih5: 超級大水題；
okret: 超級大水題，注意特殊情況即可；
zadaca: 水題，直接因數分解一遍，再查找相同的因數（用哈希），求較小值即可，對于10^9的判定應該很容易的，注意特殊情況；
kompici: 中等難度，需要用到容斥原理，對于開始的10^6個數，由于本質不同的只有1024個，所以可以壓縮成1024種情況，這樣總的復雜度就是1024*1024了；
funkcija: 神犇題！！巨神無比的遞推！！這里面涉及到的思想需要慢慢總結；
raspored: 中等難度，模型轉化后可以發現T是無用的，只需要按照時間遞增的順序執行任務（貪心的經典模型），然后用線段樹維護這個遞增序的和就行了；
2011~2012 #3：
digitalna: 超級大水題；
dhondt: 超級大水題，關鍵在于題意的理解（是把每個派別的選票總數依次除以1到14，得14個結果，然后匯總起來取前14大的結果對應的派別，不是按比例）；
pogodak: 水題，暴力模擬即可；
robot: 水題，注意二分查找的邊界（比如要找大于等于給定值的最小值，需要特判所有的值都小于給定值的情況）；
place: 超級大水題，裸得不能再裸的模型了；
traka: 本張試卷的唯一一道不水的題（是個神犇題），首先很容易模型轉化為求F[i]S[i-1]-F[i+1]S[i]的最大值，由于F是個定值且為正，可以除以F[i]，變成S[i-1]-(F[i+1]/F[i])*S[i]，可以看成直線y=S[i-1]-S[i]*x，當x=F[i+1]/F[i]時的縱坐標，這樣把所有的直線搞出來，維護下凸殼即可（當然本沙茶至今未做過這樣數形結合的題目囧……以后可以搞一個專題）；
2011~2012 #4：
kino: 超級大水題，貪心就能搞定；
zima: 水題，線段樹操作，注意細節（本沙茶一開始把下放標記dm()中的mr_opr(LCH(No))，mr_opr寫成dm了……成遞歸調用了……為此查了2h+）；
keks：超級大水題，貪心經典模型，不要管前導0的問題；
ograda：這個是神犇題了（因為本沙茶總是搞不定啊囧……），首先由于相鄰元素的大小關系以定，絕對值號可以去掉的（本沙茶竟然木有想到這個），然后根據貪心思想，應當盡量把大的和小的交替放置，而且這樣必然能得到可行解（詳細證明見官方題解）；
broj：中等難度，P>=5000時可以直接篩，P<5000時用容斥原理（表面上需要計算2
N次，N是小于P的質數總數，其實很多交集都是空集，可以忽略掉，最后剩下的非空集合很少的囧……這也是容斥原理之所以廣泛應用的原因啊囧……）
kriptogram: 中等難度，首先各個單詞可以映射到Trie里面，變成編號，然后就是類似KMP的搞法了（類似于WC2012 Day1上午講的那道CEOI題目）……本沙茶用官方數據本機測試AC，但交上去RE了兩個點……說是Trie爆了……（本機測試時跟蹤了一下，發現木有爆）主要是這題空間卡得太死（64M），而Trie的空間由于要乘上一個104，所以不能開太大（或許這里可以優化，但本沙茶還不會啊囧……）