2020CCPC威海遊記

感謝教練爭取的外卡，感謝教練帶我們出去吃兩次飯
個人首銅。終於能寫一次遊記，雖然這次我並沒有出去。
從準備環節開始講吧。
某一天看到出題是南京大學，然後意外翻到南大那個強隊的一個人的部落格，就尋摸著這人會不會出題？來一波面向出題人的準備？

看了看他部落格 Palindrome series 好像是個很新的東西（集訓隊論文19年才有提出這個東西？），沒學過，計算幾何的閔可夫斯基和也沒學過，於是補了一下那倆。然後發現他好像字串挺強的，就尋摸著怎麼著也得出一道字串吧？
結果正式賽一個字串都他媽沒有草

然後是熱身賽，熱身還是期待他出一道字尾陣列的題的因為字串就這個東西沒學，出了明天就不怕了。然後，出了個我們會的2-SAT，或許這就預示著明天可能會賊不順吧
事實證明確實不順，雖然鍋都在我身上
第一題簽到，思維沒啥難度，直接寫出來了，走一發，$WA$，有點小慌，策略有問題？於是開始和一個隊友開始了長達幾十分鐘的將正確的結論證偽的過程，最後頂不住了，棄療了，因為實在找不到策略哪裡有問題，這個時候撇了一眼宏

#define sl(a) scanf("%d",&a)

臥槽等等，這不對勁兒？我敲的時候怎麼回事，ll按int輸了？可是這個n的資料範圍並不會爆longlong，是因為這個炸的嗎？是的話直接交一發？然而不應該啊，但想了想很久以前hdu上因為這個WA了一次，反正走投無路了，於是又交了一發。
然後，稽核錄屏的人就可以看到一個人大喊一聲「日媽的我傻逼」

出鍋++

然後開始開第二題，想了好一會兒沒想法不知道咋維護，期間還棄療和另一個隊友討論了一下L然而並沒有結果，後來又想了想十有八九是要每個set單獨考慮然後又想離線一下bit維護，誒？搞。第二題一發過，WA 唯一一個沒wa的題 ，雖然人傻想了太久

然後跟榜開D，想了一小會大概猜到結論就是對給定的數質因子分解看每個質因子冪次是不是都是1，若有大於1的就不行，然後人懶了感覺應該沒問題直接就上了，然後 WA
（此處是因為分解時沒考慮大於1e7的質因數的平方，出鍋++）
這裡就感覺是不是結論假了，於是就開始證，然後證出來結論沒問題
然後意識到大質數沒考慮到，質因數分解寫假了，加上判分解剩餘值是不是平方數，然後又 WA （此處因為是拿剩下的值判是不是平方數，就把本是no的1弄成yes瞭然而沒意識到，出鍋++）
然後，自閉了。開始懷疑隊友質數篩寫假了，自己寫了一遍，WA 出鍋++，於是棄療
不過還好最後隨手又測了下1發現了問題，最後還是過了

來到第四題，隊友先是搜，我瞅了眼搜的結果發現到後面答案開始收斂，莫不是小範圍打表大於一個值之後直接printf？於是思路在這地方卡了n久，後來發現隊友搜尋寫假了真的搜尋跑不到完全確定收斂的點就超時，表根本打不下來，然後隊友說要不dp，想了想確實可以按分組揹包dp（得虧上週藍橋杯發現揹包就沒好好學過直接寫還寫不出來就專門重學了一邊），於是直接按分組揹包敲了個，敲完發現維護乘法的話沒寫過，怕出事，又發現是對答案取對數，那麼直接對每個值取對數換成加法的揹包似乎穩的一批？但和乘法的比較一下發現乘法會收斂但先取對數就不存在收斂，懷疑精度出問題（去年徐州心理陰影），還是聽隊友繼續乘法揹包，於是 WA
GG打個錘子
然後想著想著不對啊這他媽乘法必要溢位啊，而且之前隊友的搜尋也會溢位，乘法的絕對不對勁，和隊友討論後統一意見覺得確實有溢位問題，就又換回加法（並沒有刪除留了一份）交，AC
第五題跟榜的話是個算期望，一看期望就煩於是看了另外一個資料結構，直接就有思路，線段樹維護hash來判序列是否相等不就ok？開始寫。然而hash不知道哪裡寫出問題了，這個題最後都沒過，後來看群裡討論說值域對映不能從0開始（md不就是我嗎），不過不確定自己的是咋回事，下週補一下再看看吧 感謝出題人教我hash

果然是值域對映的問題，雖然改的時候發現我寫的線段樹pushdown忘更新mx了就算對映對了也沒用

長春繼續沖沖衝