2020CSP-S1答案決議及總結

P r e p a r a t i o n Preparation Preparation

回想以前的初賽經歷，小學五年級第一次去初賽，差0.5分進普及組復賽，六年級因為特殊原因缺席了
初一第一次擠進普及組復賽，初二初三普及組就比較順利了，初三擠進了提高組，分數還是挺懸的，講真對這次初賽沒有特別大的把握

于是9.17的時候就開始備戰初賽了，起初是做做歷年的NOIP，當然成績不是很理想，開始整理錯題復習知識點，寫了一個錯題本，說實話這個東西確實對我的幫助很大，特別是在修電腦的知識方面，，，

10/05開始正式天天做初賽，第一做了91.5（這輩子第一次初賽上90QwQ），第二次只有76，第三次又搞到了89，然后洛谷初賽做到了94，興奮地寫了題解，沒想到看的人挺多的QwQ

然后間歇的刷刷復賽題，就到考試日了，，，

F e e l i n g Feeling Feeling

早上快八點出發去考點，到的時候和各位大佬復習了一下錯題（中間趁上廁所的時間甚至開了一把單挑？？？）
然后做的總的來說還可以吧，由于監考人員的失誤，大概開考5分鐘了才正式做題，不過無關緊要，
今年是第一年初賽用答題卡的呢，時間還是有點緊
閱讀2之前的題都很簡單，做得很快，閱讀2、3自閉了，完善1和2勉強能做到接近滿分吧，，，

今年的閱讀出奇的難，我這種菜雞估計只有80+了
如果覺得作者太菜了的大佬輕點噴，給我留點面子QwQ

S o l u t i o n s Solutions Solutions

1~5

1：四個選項分別是，A 550、B 511、C 1024、D 558
2：定義題，沒啥好說的
3：8分鐘=480秒，每秒24幀，對應11520幀，每一幀都是 2048 × 1024 2048\times 1024 2048×1024的像素，且有32位，32位對應4B，相乘得到 11520 × 2048 × 1024 × 4 B 11520\times 2048\times 1024\times 4B 11520×2048×1024×4B，三項分別提取一個1024，得到 11.25 × 2 × 1 × 4 G B = 90 G B 11.25\times 2\times 1\times 4 GB=90GB 11.25×2×1×4GB=90GB
4：如圖，最后堆疊中只剩下a和c，a是堆疊底，c是堆疊頂
5：A選項7和18會沖突，B選項7和18會沖突，C選項7和18會沖突，，，

6

單獨放出來不是因為它有多難或多重要，只是因為它占了兩頁，，，

7~15

7：每個點和每條邊只會被遍歷一次
8：左右側各12各點，左側的每個點都能向右連12條邊，所以是 12 × 12 = 144 12\times 12=144 12×12=144
9：常識題
10：可以暴力求解，也可以像我考場一樣列 C R T CRT CRT
{ x ≡ 2 ( m o d ?? 3 ) x ≡ 3 ( m o d ?? 5 ) x ≡ 4 ( m o d ?? 7 ) \left\{\begin{matrix} x\equiv 2 & (\mod\ 3)\\ x\equiv 3 & (\mod\ 5)\\ x\equiv 4 & (\mod\ 7) \end{matrix}\right. ????x≡2x≡3x≡4?(mod 3)(mod 5)(mod 7)?
M = 3 × 5 × 7 = 105 M=3\times 5\times 7=105 M=3×5×7=105
M 1 = M 3 = 35 M_1=\frac M3=35 M1?=3M?=35， M 1 M 1 ‘ ≡ 1 ( m o d ?? 3 ) M_1M_1^`\equiv 1(\mod 3) M1?M1‘?≡1(mod3)，得 M 1 ‘ = 2 M_1^`=2 M1‘?=2
M 2 = M 5 = 21 M_2=\frac M5=21 M2?=5M?=21， M 2 M 2 ‘ ≡ 1 ( m o d ?? 5 ) M_2M_2^`\equiv 1(\mod 5) M2?M2‘?≡1(mod5)，得 M 2 ‘ = 1 M_2^`=1 M2‘?=1
M 3 = M 7 = 15 M_3=\frac M7=15 M3?=7M?=15， M 3 M 3 ‘ ≡ 1 ( m o d ?? 7 ) M_3M_3^`\equiv 1(\mod 7) M3?M3‘?≡1(mod7)，得 M 3 ‘ = 1 M_3^`=1 M3‘?=1
所以該同余方程組有最小正整數解
x = ( 2 M 1 M 1 ‘ + 3 M 2 M 2 ‘ + 4 M 3 M 3 ‘ ) m o d ?? M x=(2M_1M_1^`+3M_2M_2^`+4M_3M_3^`)\mod M x=(2M1?M1‘?+3M2?M2‘?+4M3?M3‘?)modM
= ( 2 × 35 × 2 + 3 × 21 × 1 + 4 × 15 × 1 ) m o d ?? 105 =(2\times 35\times 2+3\times 21\times 1+4\times 15\times 1)\mod 105 =(2×35×2+3×21×1+4×15×1)mod105
= ( 140 + 63 + 60 ) m o d ?? 105 =(140+63+60)\mod 105 =(140+63+60)mod105
= 263 m o d ?? 105 =263\mod 105 =263mod105
= 53 =53 =53
所以， x ∈ ( 50 , 60 ) x\in(50,60) x∈(50,60)
11：爬到第 i i i層需要的體力為 ∑ i = 1 i ? 1 10 i = 10 ( i 2 ? i ) 2 \sum _{i=1}^{i-1}10i=\frac {10(i^2-i)}2 ∑i=1i?1?10i=210(i2?i)?，暴力帶入計算即可
12：如圖，畫出這個樹，然后寫出后序遍歷即可
13：每一個格子都能和九個格子連邊，這樣會多算一倍，所以是 16 × 9 2 = 72 \frac{16\times 9}2=72 216×9?=72
14：顯然
15：修電腦題，不多BB

閱讀1

1：可以等于1000
2：如果所有 d i d_i di?都相等，會輸出-1
3：改過來之后如果是不上升序列一定會輸出-1，不改的話不一定
4： i , j i,j i,j都判斷一次 d i < d j d_i<d_j di?<dj?或 d j < d i d_j<d_i dj?<di?，其實就相當于判斷 d i ≠ d j d_i\neq d_j di??=dj?
5：容易發現那個運算其實在二進制下是不進位的
6：自己看，反例都舉在旁邊了

閱讀2

1：顯然是 [ L , R ] [L,R] [L,R]
2：運行是不會出毛病的
3：答案應該是 l o g 2 n log^2n log2n，所以四個選項都給分
4~6：作者都錯了，無法給出決議（我太菜了5555）

閱讀3

1：當兩串完全相同時，輸出0
2~6：作者不是蒙對了就是錯了，無法給出決議（我是真的菜555）

完善1

1：提示里已經給出按照 w j v j \frac {w_j}{v_j} vj?wj??從大到小排序，容易看出代碼里寫的是冒泡排序，所以當前面的權值比后面小時，交換，即 w j v j ≤ w j + 1 v j + 1 \frac {w_j}{v_j}\leq \frac{w_{j+1}}{v_{j+1}} vj?wj??≤vj+1?wj+1??，由于是分數運算，容易有精度問題，兩邊同時乘 v j ( v j + 1 ) v_j(v_{j+1}) vj?(vj+1?)，即可得到 w j v j + 1 ≤ w j + 1 v j w_jv_{j+1}\leq w_{j+1}v_j wj?vj+1?≤wj+1?vj?
2：若體積不夠或剛剛好，才需要考慮后面的
3：初始化
4： p r i n t ( w , v ) print(w,v) print(w,v)其實相當于輸出 w v \frac w v vw?，之前的 c u r W curW curW都是可以完整選走的，由于輸出的時候除了 v [ i ] v[i] v[i]，所以要乘下去，然后剩下的空間 （ B ? c u r V ） （B-curV） （B?curV）全部填上 w [ i ] w[i] w[i]
5：如果能完全填滿，相當于輸出 c u r W curW curW，即 c u r W 1 \frac {curW}1 1curW?

完善2

1：可以帶入二進制下的1010去試驗，發現只有 D D D合法，其實其相當于 x ? = x & ? x x-=x\&-x x?=x&?x，即 l o w b i t lowbit lowbit
2：觀察發現 y y y取走了 a a a的低四位，那么顯然 x x x是要取走 a a a的高四位
3：我也錯了QwQ
4：低位轉移
5：高位轉移

有問題和建議可以在下方留言