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