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

$Result$

賽時：

賽後：

---

$Feeling$

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

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

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

---

$Solutions$

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

1~6

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

---

7~15

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

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

---

閱讀1

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

---

閱讀2

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

---

閱讀3

原題題解


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

---

完善1

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

---

完善2

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

---

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

$TheEnd$