Luogu CSP 2020 第一輪（初賽）模擬 題解&總結

R e s u l t Result Result

賽時：

賽后：

F e e l i n g Feeling Feeling

感覺難度偏低，題目考得面還是可以的，跟OI相關的多很多
甚至出現了閱讀2，閱讀3兩道原題，，，
修電腦的題終于tmd少點了
然后自我感覺狀態還可以，一個小時半做完的，最后是錯了第三題、十四題、二十題

其中第三題是我菜沒辦法，第十四題忘記了一棵樹也可以算作森林，第二十題算對了，選錯了，，，

嚴格意義上來說我應該是92，因為第二十題是4分的

S o l u t i o n s Solutions Solutions

紅色是考場時做的標記，藍色是修改后的

1~6

1：顯然-114在二進制下為11110010，然后補碼就是第一個1和最后一個1不變，中間的取反，得到A
2：Luogu就是洛谷啊，，，，Gitee是托管代碼的，，，Leetcode源自美國硅谷，是一個OJ，，，Codeforces是俄羅斯一個團隊創立的OJ
3：AAA對應703， 26 × 26 = 676 26\times 26=676 26×26=676，所以BAA對應703+676=1379，然后BBA對應1379+26=1405，所以BYA對應 1379 + 26 × 24 = 2003 1379+26\times 24=2003 1379+26×24=2003，然后T是第20個，對應加19，就是2022
4： 4096 × 2160 × 24 / 8 = 26542080 B = 25920 K B = 25.3512 M B 4096\times 2160\times 24/8=26542080B=25920KB=25.3512MB 4096×2160×24/8=26542080B=25920KB=25.3512MB（其實還要加上54B，但可以忽略不計）
5：《演算法競賽進階指南》上面有講，用快排的思想，可以做到 O ( n ) O(n) O(n)
6：第一個的話是因為要聯通，第四個的話樹上是沒有環的

7~15

7：我蒙的！我蒙的！我蒙的！
8：可以把這棵樹畫出來

9：顯然，，，
10：最理想的情況下一找就找到了，所以是 k k k次
11：列舉C班選了多少個風紀委員，再討論，兩側是討論的程序，數一下正好18種
12：計數排序的復雜度與每個數的大小有關，插入排序就是 n 2 n^2 n2，希爾排序是 n 3 2 n^{\frac 32} n23?，歸并是 n l o g n nlogn nlogn的
13：隨機一個 [ a , b ) ? N + [a,b)\bigcap N^+ [a,b)?N+，實際上就是隨機一個 [ a , b ? 1 ] ? N + [a,b-1]\bigcap N^+ [a,b?1]?N+，如果你做過資料，這題隨便拿下
14：7個頂點的完全圖有 7 × 6 / 2 = 21 7\times 6/2=21 7×6/2=21條邊，邊數最多的森林是樹，它有 n ? 1 = 7 ? 1 = 6 n-1=7-1=6 n?1=7?1=6條邊，所以要刪去15條
15：常識題，NOI從1983年開始舉辦，NOI2020是在長沙（我太菜了，去不了）

閱讀1

1：顯然輸入就可以輸入一個奇數
2：顯然
3：這些行是為了記憶化的，刪去只會影響程式效率
4：確實
5：上面有我的推導程序，加在一起就是8
6：最壞情況下縱向推 n n n層，橫向訪問 m 2 m^2 m2遍

閱讀2

原題題解
1：錯誤， f l o y d floyd floyd順序不能改變， k k k是階段， i , j i,j i,j是列舉轉移的點
2：錯誤，輸入都有 m m m，怎么可能無關？
3：正確，最大的答案可能是1e9級別的
4：正確， i , j i,j i,j相當于列舉哪兩個點是可以“瞬移”的（可以耗費0到達彼此），列舉兩個瞬移點做 f l o y d floyd floyd，更新 F F F陣列
5：看圖自行推導
6：顯然

閱讀3

原題題解


1：當且僅當 i < j i<j i<j時才成立，如果 i = j i=j i=j的話是1
2：錯誤，是組合
3：不一定，有模數
4：確實
5：顯然 C 10 5 C_{10}^5 C105?肯定是最大值，而且沒有超過模數
6：自己畫一個楊輝三角求個前綴和即可

完善1

1：這個點遍歷了，相當于去掉它
2：如果這個點沒有入度了，相當于沒有限制了，可以直接跑，如果 w = 0 w=0 w=0，說明它的父親是沒有洗掉的，那么自然它也可以遍歷
3：父親洗掉了，自己不能刪，父親沒刪，自己可以刪
4：每個沒有父親的點開始遍歷
5：把沒有遍歷到的點遍歷完

完善2

1：最開始的 s u m sum sum只有第 n n n個數
2：顯然放入 s i s_i si?這個數
3：去掉最小值，再取平均值
4：遇到更優的，則重置k陣列，并放入i-1
5：遇到相同的最優解，直接放入i-1

本人著作權意識薄弱，如果放出題目侵權請私信我
有意見和問題可以在下方評論區留言

T h e E n d The\ End The End