單選
1.直接進行進位轉換即可。可以全部換成10進位。2.C,C++,Pascal都是編譯執行的語言，Python是解釋執行。 擴展：JS、PHP也是解釋運行語言。解釋性靈活但是效率較低。一些解釋性語言也有了也能在一定程度上編譯，或者使用虛擬機。3.今年是第35屆NOI，因此第一屆NOI是1984年。每次都有這種沒啥實際意義的題目。4.考慮一個等比數列求和。第一層的節點數是 k^0 ，接下來依次是 k^1,k^2,k^3…k^{h-1} ，也就是說節點總數是 \sum_{i=0}^{h-1}k^i ，根據等比數列求和公式 S_n=\frac{1-q^n}{1-q} ，可知答案為A。當然考場上以三叉樹為例舉例兩三層也可以得到A。5.考慮累加， T_n=T_{n-1}+n=T_{n-2}+n-1+n=…. =T_0+(1+2+3+…+n)=\frac{n*(n+1)}{2} 這題是2015年提高組初賽原題，如果有在洛谷有題上寫過這個題應該不會寫錯。6.建出表達式樹，然後先序遍歷即可。7.我們先考慮固定一個端點的情況，如果左端點固定在了最左邊那麼答案為1/2，既然左端點更大，那麼肯定答案會小於1/2，因此只能是B 熟悉ODT（即珂朵莉樹）理論的同學可以發現ODT複雜度證明裡面有這個東西，即隨機意義下期望區間長度。8.最簡單的辦法是把n=1帶入，然而熟悉卡特蘭數理論的同學會發現A選項的項數就是不對的。9.可以考慮每一輪一半人紅一半人藍 藍的進入下一輪 所以一直是1:1。當然藍色的個數也可以寫成 2S_n=2^{-1}+22^{-2}+32^{-3}+…+n*2^{-n} ， 熟悉文化課的同學會發現這是一個等差比數列，那麼我們對它進行求和，並且把小量近似掉，得到的結果為1/2，考慮紅是1/2，可以得到同樣的結論。10.熟悉樹狀數組的同學會發現B選項就是lowbit操作，可以得到最後一個1，因此不斷進行lowbit即可。當然帶入x=2也可以快速判斷。
多選
1.常識題，不過實際上很多考場執行標準不一，有的允許帶計算器，有的不允許。更多考場規則可以在NOI筆試題庫中找到。不過並找不到官方的考場規則。所以這種題目出的很勉強。2.把最底層的節點都畫出來向上連，先在符合條件的前提下把每2個點連到一起，這樣發現有8個點，可以發現這是上界。 同理把儘量多的3個點連在一起，答案是7，可以發現這是下屆，故選CD3.熟悉圖論的同學這是一個常識題。Dijkstra是單源最短路算法，因此多次調用必然能夠得到所有點對的最短路。如果圖中出現負環，那麼dijkstra算法就會在這個環裡不斷地轉，因此無法求出最短路。同理負權。4.樹的性質屬於常識。n個點，n-1條邊，無環，連通，任意兩點有且只有一個路徑。5.BCD屬於所謂常識，A項是ACM的創辦機構。
問題求解
1.由於點數很小，手動模擬下。從條件3開始找，即可找到答案。2.首先如果b是a的子集，那麼條件必然成立。然後手動簡單玩一下，發現只有1位和2位情況存在特例。手動找到這些的答案即可。科學的解釋是：設a and b=x,a xor x=y,b xor x=z，則(x+y)(x+z)=x(x+y+z)，即yz=0，即a and b=a或a and b=b
讀程序寫結果
1.簡單模擬即可。這種題非常需要細心、耐心。以前第一題常常會出複雜表達式求值。2.可以看到是讀入一個序列，每個點都有一個出度。可以發現這是在找環的個數，手動模擬或者畫個圖數一下都可以。3.可以發現magic(l,r)是對於s[l,r]的字符串哈希，底下枚舉了兩個子串，那麼答案其實就是不重複出現的子串個數，手動數一下就好了。4.可以發現這一大堆函數唯一的用處就是找到字典序大於他的下一個排列（其實看到輸入都是全排列的元素、以及一個next大概就可以猜到了。），對於第一個詢問可以手動找到下10個排列。對於第二個詢問，可以把後幾位帶在一起算，每次看把某一位更新成下一個值需要加上多少。當然也可以直接進行康託展開對全排列進行計數。
完善程序
1.一個有點鬼畜的雙向鍊表。對於第一個空我們會發現如果a[i]=x的話直接cin>>a[i]其實就好了，所以必然是a[x]=i，意思是x是在第幾個位置。2,3,4空 可以考慮仿寫。完善程序出現「複讀機」套路是很常見的。當然不能全部復讀，要講究對稱性。5空我們發現題目既然要求第i個數後面最近的一個比他大的，那麼必然是i的後繼，即R[i]。 當然已經做出前幾空了把題面的那組數據帶進去就會發現的確是R[i]。 如果原理不懂得可以畫圖進行模擬。不過反正寫題本身很簡單。2.首先先考慮算法：如果第一家便宜肯定選第一家。如果第一家打95折還是比第二家貴，那麼肯定選第二家。 那剩下的一些呢？我們稱為「中間物品」。儘可能選擇其中一些「中間物品」在A買，湊足50000元，使得比B便宜，但是儘可能的少。這是一個背包問題。 實現上，f[i,j]表示前i個物品，在額外在A店花了j元的情況下，購買B店「中間物品」的最小值。i呢？滾動數組空間降維。第一空：如果直接a[i]<=b[i]的話上文就算過了，沒必要單獨循環一次。考慮貪心那麼必然是看加了優惠之後a[i]是否優於b[i]；第二空：考慮printf裡面的部分，那麼如果a的總和已經滿足優惠，直接優惠掉即可；第三空：考慮仿寫min裡面的部分，那麼肯定是當前枚舉的優惠幅度超過了50000。這是考慮如果我們要買第i件，還額外花了j元在「中間物品」上的情況；第四空：這是計算總價，第一店所有東西打折後，加上所有第二點需要購買的東西；第五空：考慮它為啥要判j>=a[i]，這個是做個背包問題都知道，這是背包問題的轉移。如何評價noip2018初賽？1. 綜合難度比較大。今年的初賽難度主要體現在理解題目給出的程序思維上面。閱讀程序和問題求解都不太有那種需要爆肝枚舉硬肛的題目，如果知道它是想幹什麼，還是可以推導出來的。2.（那個全排列的，200個枚舉你是認真的嗎？）3. 完善填空的涉及的算法思維還是相比於之前的各種模板題大很多。如果這兩題作為NOIP複賽的題目，AC率應該不會很佳。但我認為出的不好。尤其是第一題，複讀機性太過於明顯，幾乎就是送的。這種投機取巧的填空實際上並不能體現出選手的算法素養水平。實際上，即使能夠全部寫對這題的填空（連蒙帶猜，全部寫對不是什麼困難的事情），也有可能並不懂這題的算法是在幹什麼。4. 選擇題相比於之前的題目，過於講理論，而以往的一些工程性的知識和計算機常識均沒有涉及。與其說是「信息學競賽」，不如說是「離散數學比賽」。考場能帶什麼東西這個題其實已經考爛了，但是實際上各個考場尺度不一，而且CCF也並沒有公開一個明確的標準。所以這種題目出的很無效。5.（有人說NOI筆試題庫有講到一些這方面的，但是參加初賽的有多少人參加過NOI的呢？不過洛谷有題也會在合適的時間加上NOI筆試題庫）6. 不出意外的話，今年的得分率會低一些，所以就算分數估出來低一點也不要太擔心。7. 其實我們並不怎麼需要專門準備NOIP初賽。算法學習到一定程度，去寫幾套歷年卷子並且弄懂，能力自然就會有很大的提高。
本文發布於洛穀日報，特約作者：zcysky & kkksc03
原文地址：https://www.luogu.org/blog/zcysky/noip2018-chusai-tg-sol