SDOI一輪摸魚記

01-25

這學期開學過了沒幾個星期就停課了。雖然說是為了學數競和OI，但是我們學校沒有數競自習室，就只能天天呆在微機室。既然在微機室就要寫題是吧...於是邊摸魚邊寫了一個月的題。主要都是些模版題，稍微複雜一點的就得問學長或查題解...於是就這樣到了山東的一輪省選。

省選之前加了一個SDOI2016的群，發現好多神犇%%%%這次的目標就是堅持到二輪省選，於是打算寫寫暴力騙個200來分就好了。

Day1

一早來到山師附中果然發現好多好多神犇%%%%一進考場大家都在啪啪啪敲鍵盤就我啥都沒寫。突然發現自己連提交時文件怎麼放都不知道，連忙問監考老師，發現不只有我一個人不知道好開心

拿到題一看，和想像中的似乎有點差距...T1這個求和是什麼鬼，T2似乎是網路流？T3無論到底是鏈剖還是能用LCT都夠噁心的，不是很想寫。於是就先開始看T1。把這個求和的東西打出來貼到了Excel里塗色找規律，旁邊坐的人似乎在學我...找了半天覺得有點像分形之類的，但是沒想好怎麼算，就打了個暴力去看T2。T2樸素的想法就是把每個數拆成兩個點直接建圖，跑一個費用流就出來了...然而發現那樣的話一次配對會對應兩條邊。怎麼辦呢？那就同時增廣兩條增廣路就好啦！本著這種想法寫了暴力建邊+如上魔改過的費用流，試了幾組數據覺得應該是對的，就沒再去管。

回來看T1，看著看著發現好像裡面有一些邊長 $2^n$ 的正方形塊，塊里每一行都是一樣的。於是就把 $n$ 和 $m$ 分別二進位拆分之後算每一塊，就能算出來了...雖然還有點時間但是實在不想看T3了，就沒有管它交卷了。

考完看群里的神犇都在說T2有二分圖，我完全沒看出來，好像和質因數個數的奇偶性有關...似乎有不少人寫了T3，T1有人說是數位動歸，一想其實也差不多。

出成績後發現qdez有一位AK的神犇，我200分能排到第三...話說T2如此暴力竟然A了...和學長討論了一下明天的題，覺得可能會出字元串或DP，還可能有些數學或者數據結構之類的。沒想那麼多又看了看藍書和黑書就睡了。

Day2

一早去了碰到出題人jzh，打聽了一下覺得似乎D2會很難...結果拿到題一看：這都些什麼玩意？T1字元串肯定是後綴數組，然而不會寫，於是寫了蛤希。T2一看這不是全錯位排列嗎，直接上式子 $d_n=n!sum_{i=0}^nfrac{left(-1 ight)^i}{i!}$ ，遞推的話就是 $d_n=nd_{n-1}+left(-1 ight)^n$ 。然後覺得可能要用到線性時間求逆元於是推了一會，大概是這樣： $i^{-1}equiv -left[frac{p}{i} ight]cdotleft(pmod i ight)^{-1}pmod p$ 但是後來發現並不用。T3裸的斜率優化動歸，寫了一會就寫完了。結果三個小時左右沒事幹.....太無聊了於是開始拿暴力程序跑大數據玩，玩著玩著就到時間了。

之後聽jzh講題。D1T1和我想的差不多，T2原來就是按質因數個數的奇偶性分類，只有不同類里的才能配對，然後直接建圖跑最大流就好了...怎麼就沒想到呢...T3果然是鏈剖但是好複雜，找時間寫一寫試試吧。D2T1似乎是線段樹動態維護後綴數組，T2T3就是我想的那樣。

總分竟然水到了460...不過總算是能參加二輪了。

接下來的一個月也要努力啊。

（我的數學已經荒廢）