2020CSP全國資訊學聯賽 游記

Day -4

中午打了樹的直徑，做了復習，下午回來看了一下例題，
晚上估計是復習 l c a lca lca等樹上演算法，

Day -3

中午機子壞了，
晚上沒來，

Day -2

期中考試，發揮失常，數學沒有AK，大概116，
中午沒來，晚上來了，
不知道干啥——做USACO，
感覺要掛科，

Day -1

期中考試，英語賊簡單，
其它感徑訓行，
然后什么時候都沒來，
期中考試感覺總體還可以

Day 0

早上在講試卷，
不難，幼ò訃得不錯？？？
怎么可能？？？
感覺很累，看三體看瘋了，
然后中午沒來，下午打了球，
就感覺心情不佳，
晚上沒上晚修，早寫完作業就來了，被老師叫了一下（還好），來寫會游記，看看資料，
好怕呀！
注意事項（由于本人是蒟蒻，所以不會高深演算法）：

1. 不要著急，
2. 背包問題：01是倒，完全是正，
3. 要多多對拍，
4. 注意時間，入門組要抓緊時間，最好每道題都想到正確方法；提高組也盡力而為，
5. 小心粗心等問題，最后想好再寫代碼，
6. 不要想任何與考試無關事情，
7. 背包問題輸出方案，記錄直接更新，
8. 總方案數用01/完全，一樣方法，
9. 區間 d p dp dp注意好回圈順序，
10. D A G DAG DAG上的 d p dp dp沒打過，但是也不難，按正常 D A G DAG DAG求法再 d p dp dp，
11. 樹形 d p dp dp用 d f s dfs dfs或者是 d f s dfs dfs序，
12. 換根 d p dp dp要思考一下，其實不難，
13. 狀壓 d p dp dp要注意狀態，
14. 單調佇列優化要思考，
15. 哈希表的 m o d mod mod要定為質數，如果很容易重復，就用雙哈希或者三哈希，
16. 并查集要壓縮路徑，
17. 可以用啟發式合并提升速度，
18. 堆打的時候要多在草稿紙上模擬，主要是這些資料結構不常用，
19. 解決區間靜態的可重復貢獻問題是用 S T ST ST表，思想是倍增，
20. 樹狀陣列記得如果 d e f i n e define define時就要將 l o w b i t lowbit lowbit里面的運算打上括號，或者直接寫函式， l o w b i t ( x ) = x & ( ? x ) lowbit(x)=x\&(-x) lowbit(x)=x&(?x)，
21. 線段樹要掌握其精髓，不要盲打，記得要開4倍空間，
22. 鏈式前向星：最好不要用 s t r u c t struct struct，記得無向圖或樹要開而被空間，
23. 記得 2 n 2n 2n是 n < < 1 n<<1 n<<1，
24. 樹的直徑用兩遍 d f s dfs dfs可以做完，
25. 樹的最近公共祖先要用倍增做，如果忘了就思考一下 d f s dfs dfs序的 R M Q RMQ RMQ問題，盡量 不要用 t a r j a n tarjan tarjan，我也不會，
26. 以樹的重心為根，所有子樹的大小小于等于整棵樹大小的一半，
27. 拓撲排序記得將訪問的點標記，
28. 最小生成樹盡量用 k r u s k a l kruskal kruskal不要用 p r i m prim prim，
29. 最短路 s p f a spfa spfa不行就打 d i j k s t r a dijkstra dijkstra的堆優化，
30. 強連通分量 t a r j a n tarjan tarjan不要打錯，
31. 網路流本質：找增廣路，
32. 要多思維發展，
33. 多想一想高奆給我們講的故事，
34. 不會一定打暴力，
35. 對拍盡量10組+，

Day 1（正式比賽日）

Before CSP-J

在本校，
很早就起了，被同學吵醒了，
打鈴之前就醒了，
繼續追三體，，，
然后7:00去拿身份證然后沒吃早餐，
等會去吧，
感覺這天有點奇怪，，，secret

CSP-J

感覺要涼涼，，，
第一題很水，直接一個二進制搞一搞，好像9:00做完了并對拍了，
第二題想了三種方法：每個區間排序、插入排序、桶，還是打了桶，時間復雜度 O ( 600 n ) O(600n) O(600n)，感覺可以過，正解是對頂堆？？？沒學過，
第三題比較難，首先打了暴力，然后就想到了用后綴樹，建了后綴樹之后就開始想了一個樹上修改的方法，好像要樹剖優化，然而我不會，一直做到10點左右，正解是預處理出是否對結果影響，然后可以的就做一些事情，
第四題沒有時間，想了一種 d p dp dp再重復四次，結果掛了，然后就打了 d f s dfs dfs，結果沒時間打記憶化，，，
估分：100+100+50+20=270，
可能沒有一等，，，自閉了

Before CSP-S

來了機房寫了總結，
下午感覺要涼涼，，，
希望最難的資料結構是平衡樹，

CSP-S

在上午的教室的旁邊，旁邊一堆高中的，
然后發了下來題目，

14:30-15:00

看題時間，其中第二題有點沒看懂，最后還是懂了，

15:00-15:20

第一題不難，但是細節很多，不想推數學公式，所以打了一個暴力，

15:20-16:00

調了很久，第二個樣例死活過不去，
很慌，檢查了很久，最后發現把4713寫成4173，
暴力總算過了，

16:00-16:30

打第二題，
從20分打到40分，結果后面想到了乘法原理，
然后就應該可以滿分了，大樣例過了，
時間復雜度是 O ( n k ) O(nk) O(nk)，
應該行，但是好像要開unsigned long long，
而且還要特判 n = m = 0 , k = 64 n=m=0,k=64 n=m=0,k=64的情況，只能打表，

16:30-17:00

暴力解決第三題，
直接一個 d f s dfs dfs，
不想打了，
后來發現可以優化，

17:00-18:00

第一題打了一個常數為 1 365 \frac{1}{365} 3651?的方法，
然后沒有注意到某一年的10月，我掛了，從50到40，
然后想用二分，但是不會，

18:00-18:30

檢查了無數遍，

After CSP-S

感覺要涼涼，luogu自測提高組150，oi題庫自測普及組265，
普及T4直降15分，原因到底是什么，
提高組T2還真的毒瘤，出了三個大于long long的資料，還有一個是 2 64 2^{64} 264，選擇打表，
然后自閉了，
然后拿完東西回家了，

Day 1.9

聽zhy奆他普及300+，提高200+，
晚上很晚了，提高組T3感覺很水，一個類似線段樹的方法想了出來，
太水了還是，
終究還是沒有發揮好，
普及T4，類似我的 d p dp dp方法，用 0 / 1 0/1 0/1存狀態，
提高T1，數學題，但是不想打，
提高T3，直接一個線段樹？
提高T4，堆/平衡樹？

Day 2

自閉中，
在寫作業，
今天又要回校了，
明年加油！