【第二十四屆全國青少年資訊學奧林匹克聯賽】NOIP2018普及組初賽試題決議（C++語言）

選擇題

1.D 【決議】列印機屬于輸出設備，它將一些資訊通過列印機列印出來，掃描儀，鍵盤，滑鼠屬于輸入設備，
2.D 【決議】 A，B，C選項的十進制數值都是 617 617 617，D選項的數值是 619 619 619，
3.D 【決議】 1 M B = 1024 K B = 1024 × 1024 B 1MB=1024KB=1024×1024B 1MB=1024KB=1024×1024B
4.B 【決議】 廣域網的縮寫是 W A N WAN WAN，局域網是 L A N LAN LAN，城域網是 M A N MAN MAN，
5.B 【決議】 常識，要對資訊學競賽的背景有所了解，
6.A 【決議】首先我們要知道CapsLock是鍵盤上用于切換大小寫得鍵，例如，你們來輸入的是小寫的a，如果你按了CapsLock鍵，輸出的就是大寫的 A A A，模擬題目中的規矩，可以得到回圈： （ A ， S ， D ， F ， a ， s ， d ， f ） （A，S，D，F，a，s，d，f） （A，S，D，F，a，s，d，f），其中每八個字母一個回圈， 81 m o d 8 = 1 81 mod 8=1 81mod8=1，那么輸出的就是回圈節的第一個字符 A A A，
7.A 【決議】 節點總數為： k k k⁰ + + + k k k¹ + + +… + + + k k k^h，接下來的問題就是如何化簡這個等比數列了，設 S = k S=k S=k⁰ + + + k k k¹ + + +… + + + k k k^h，則 k S = k kS=k kS=k¹ + + + k k k² + + +… + + + k k k³， k S ? S = S ( k ? 1 ) = k kS-S=S(k-1)=k kS?S=S(k?1)=k^h+1 ? 1 -1 ?1,化簡一下就是 S = （ k S=（k S=（k^h+1 ? 1 ） / （ k ? 1 ） -1）/（k-1） ?1）/（k?1），
8.A 【決議】 基數排序是根據每一個數位的大小進行排序的，類似于桶排序的思想，而冒泡排序，堆排序和直接插入排序都是基于比較的，
9.A 【決議】我們可以選用遞推的方法，設f[i]為i個數比大小的最小次數， f [ i ] = f [ i ? 2 ] + 3 , f [ 1 ] = 0 , f [ 2 ] = 1 f[i]=f[i-2]+3,f[1]=0,f[2]=1 f[i]=f[i?2]+3,f[1]=0,f[2]=1，含義就是對于每一組數，取兩個數比大小要 1 1 1次，對于剩下的 i ? 2 i-2 i?2個數要 f [ i ? 2 ] f[i-2] f[i?2]次，一次最大，一次最小，所以要 f [ i ? 2 ] + 1 + 2 = f [ i ? 2 ] + 3 f[i-2]+1+2=f[i-2]+3 f[i?2]+1+2=f[i?2]+3次，n=3-10的資料分別是 3 , 4 , 6 , 7 , 9 , 10 , 12 , 13 3,4,6,7,9,10,12,13 3,4,6,7,9,10,12,13，帶入得A （好吧我也不是特別會）
10.B【決議】NOIP原題，不斷的出現重復和遞回的結構十分相似，
11.A【決議】畫圖，略，
12.B【決議】對于我們所要求的S，相當于一個 10 10 10位的二進制位， 1 1 1表示取， 0 0 0表示不取，則共有 2 2 2¹⁰ = 1024 =1024 =1024種方案，或者暴力一點， C ( 0 , 10 ) + C ( 1 , 10 ) + C ( 2 , 10 ) + . . . + C ( 10 , 10 ) = 1024 C(0,10)+C(1,10)+C(2,10)+...+C(10,10)=1024 C(0,10)+C(1,10)+C(2,10)+...+C(10,10)=1024,顯然這兩種方法都是可行的；對于T，顯然是10選7的組合數，即 C ( 7 , 10 ) = 120 C(7,10)=120 C(7,10)=120，那么 T / S = 120 / 1024 = 15 / 128 T/S=120/1024=15/128 T/S=120/1024=15/128,選擇答案B，
13.B【決議】求10000的歐拉函式，根據唯一分解定理， 10000 = 2 10000=2 10000=2⁴ ? 5 *5 ?5⁴,那么就可以直接根據公式， φ ( 10000 ) = 10000 × ( 1 ? 1 / 2 ) × ( 1 ? 1 / 5 ) = 4000 ， φ(10000)=10000×(1-1/2)×(1-1/5)=4000， φ(10000)=10000×(1?1/2)×(1?1/5)=4000，
14.B【決議】樹狀陣列 l o w b i t lowbit lowbit運算，求二進制位有多少個 1 1 1，當然考場上最簡單的方法莫過于帶一個數進去了，算完后就知道ACD算不出答案，
15.B【決議】結構類似于桶，先進后出，屬于資料結構堆疊，

問題求解

第一題.去了 沒去 沒去 沒下雨
【決議】
從中我們知道一個規律，如果 A B AB AB都成立那么 C C C成立，若C不成立，A和B中有一個成立的時候另一個便不成立，
因為丙去了，根據已知 ③ ③ ③可知丁不去，
根據 ④ ④ ④，如果丁和甲同時不去，說明丙也不能去，而因為丁去了，只有讓甲去丙才能不去，
根據 ② ② ②，如果乙去則丁去，當丁沒去說明乙也沒有去，
根據 ① ① ①，如果下雨且乙不去那么甲也不去，而乙去了，甲卻沒去，說明沒有下雨，
我們要根據已知去推，這也是一道比較簡單的邏輯題了，
第二題. 544 544 544
【決議】
我們從位數去考慮，
1位數： 1 1 1個，只有一個數字 8 8 8.
2位數：如果十位 1 , 2 , 3 , 4 , 5 , 6 , 7 , 9 1,2,3,4,5,6,7,9 1,2,3,4,5,6,7,9，那么有 8 8 8個（后面都接上1位的方案數）；如果十位是 8 8 8，則有 10 10 10個數字（ 8 8 8后接任意陣列均可），共有 8 + 10 = 18 8+10=18 8+10=18（個）
3位數：如果百位 1 , 2 , 3 , 4 , 5 , 6 , 7 , 9 1,2,3,4,5,6,7,9 1,2,3,4,5,6,7,9，那么有面可以跟個位有數字 8 8 8的（如 108 108 108），也可以跟十位有陣列 8 8 8的（如 188 188 188），共 8 × ( 1 + 18 ) = 152 8×(1+18)=152 8×(1+18)=152種；若百位是 8 8 8，有 100 100 100種方案，共有 152 + 100 = 252 152+100=252 152+100=252（個）
4位數： 1 1 1開頭有 1 + 18 + 252 = 271 1+18+252=271 1+18+252=271（個）； 2 2 2開頭有 2008 , 2018 2008,2018 2008,2018，共 2 2 2個；共有 271 + 2 = 273 271+2=273 271+2=273個，
共計： 1 + 18 + 252 + 273 = 544 1+18+252+273=544 1+18+252+273=544（個）

閱讀程式寫結果

1. R u a n H u o M i a n T a i RuanHuoMianTai RuanHuoMianTai
【決議】程式的左右是掃描字串的每一個字符，使得每一個大寫字母ASC碼+1，或者變成剛剛比它大1（或后面）的大寫字母，
2. 4 4 4
【決議】程式的作用是從1-14種尋著是否存在數i，使得 i i i² m o d 15 = 1 mod 15=1 mod15=1(或 i i i² % 15 = 1 15=1 15=1),通過手動計算不難發現滿足條件的數字是 1 , 4 , 11 , 14 1,4,11,14 1,4,11,14；共計 4 4 4個數，因此答案是 4 4 4，
3. 8 8 8
【決議】這是一道遞回的計算題，如果直接這么做顯然顯得麻煩了，因此我們可以通過畫二維表的方式來求解這個答案，

對于第0行，其大小為該縱坐標，
對于第0列，其大小為該橫坐標對于3取模的值，
對于任何一個非0坐標，其大小為上面的數值加上左上角的數值減去左邊的數值，
我們可以采用遞推的方法解決，
4. 6 6 6
【決議】這道題就是一個模擬鏈表的程序，查找有多少個聯通快，仔細模擬，發現是6個，

完善程式

1.最大公約數之和 答案：i * i; n/i; return a; a%b; ans+gcd(a[i],b[i])
【決議】 題目的程序就是先找到所有的因數，再進行累加，
我們首先看第一段，有一個函式的名稱叫做getDivisor，其實就是求解每一個n的因子，
依照題意，時間復雜度是（Osqrt(n)）,那么我們在每一因子i的時候就是1-sqrt（n）這個區間來列舉的，對于最大情況，只有i * i=n,超過就不滿足時間復雜度和列舉的要求了，因此第一空所填的就是i * i，當列舉的時候如果這個數是i的因子那么就接著統計，以36為例，i是從1-6來列舉的，如果列舉到2，那么因子18就是通過36/2，或者是n/i來得到；特別的，當i=6的時候，不需要操作，此時n=i*i,即n/i=i時不需要進行操作，所有第二空所填的是n/i，需要注意，盡管使用sqrt函式仍然屬于等價寫法，但是程式中并沒有加載cmath庫，因此這么寫是錯誤的，
再看求去最大公因數的程序gcd，這就是一個模擬輾轉相除法的程序，復雜度是O（logMAXAB）級別的，因此不要寫成是輾轉相減法，如果余數是0就回傳a，那么第三空就是return a；否則繼續取模，因此第四空是a%b，
接下來就是累加答案，累加每一個質因子即可，存在ans上面，因此第五空是ans+gcd(a[i],a[j])，
2.鏈表 答案：a[x]=i;i+1;R[a[i]];a[i];R[i]
【決議1】套路法（分數8-14）
空1：唯一可行的兩個答案a[i]=x和a[x]=i，若是前者可直接cin>>a[i]代替，故答案為后者，
空2：L是i-1，那么R是指向右節點的，上下符號相反，必然是i+1
空3/4：背景關系對稱，L和R恰好反一下，例如第一句是L[R[a[i]]]=L[a[i]];第二句是R[L[a[i]]]=R[a[i]],根據雙向鏈表的對稱性很容易得到答案，
空5：套中套，很多人想到的是R[a[i]]，符合上文的結構，但是陰險的出題人一定會在最后一個空坑你一把，只讓你輸出最簡單的R[i],你也可以考試的時候推一下，
【決議2】理解演算法含義
第一空是標記每一個x出現的位置；
第二空雙向鏈表R指向后面的元素，即i+1；
三四空是用于洗掉元素，這是鏈表最基本的洗掉操作，可以自行理解資料結構的實作；
第五空主要是輸出每一個元素的答案，但是要按照輸入的順序進行輸出因此要R[i]而不是R[a[i]],否則就按照了大小的順序輸出了，

試題答案

本人預估浙江分數線85上下
（不要14年那么恐怖就好）
浙江學子依舊生活在水深火熱之中…
能在考場上拿到90分已經是很滿意了，
若有疏忽或者意見望大家指正，