NOIP2017提高組比賽總結

前言

轉眼間，NOIP2017（經常叫他NOIP，其實全稱是全國青少年信息學奧林匹克聯賽）就這么過去了。回望這2個月，既有參加NOIP的激動，也有賽場上一些失利的遺憾。想一想，我應該給自己總結一下吧，希望其他人能從中獲益，也讓我明年再戰的時候能有所借鑒。

正文

NOIP2017初賽

今年的初賽，由于是到了提高組，選擇題有5題改成了不定項選擇題，就是一題可能會有多個答案的，這就比較難，于是我就提早了很長時間去網上搜羅提高組初賽的真題（明年一樣可以用呢），提早很多做（然而最后并沒有刷完所有真題），考試前還慌慌張張的復習組合的知識。在考試的時候，看到第一道選擇題就懵逼了，Pascal語言什么時候退役？我不知道啊。。。
開場以后，我極其認真的做每一題，但是發現速度不夠快，做完選擇題已花了很久，做問題求解的時候，一看是不是什么對偶圖最短路，發現手模就可以做出來。等我開始做讀程序寫結果的時候，坐在我左邊的杭二高三巨佬已經快做完了。
終于，我做完了所有的題目，時間已經不足10分鐘，我又檢查了一圈，查出了一些錯誤，在心慌中，初賽結束了。
一個星期以后，成績出來了，我好像是95.5，省里排名rank20，遺憾的是錯了3題選擇題啊，明年要好好努力，但總算是過了初賽這到坎。

NOIP2017復賽day1

NOIP的day1，是我第一次考提高組，無比認真也又十分激動，前一天晚上還在復習各種知識，生怕考到的知識沒掌握好

• day1 T1 小凱的疑惑（math）
  https://www.luogu.org/problemnew/show/P3951
  開場第一題，發現好像是數學題？（考試后有人說用擴展歐幾里得，我學的不好啊）場上推了一下，推出了答案是(a-1)b-a
  怎么**推（猜結論）**的呢？
  首先，數據保證有答案，
  然后，考慮a的倍數一定是能取到的，那么不能被a整除的數除a的余數（除了0）只有a-1種，由于有條件：a和b是互質的，所以設x=b%a（x!=0），那么大于等于b的模a余數為x的數都能取到了，b設y=2b%a(x!=y)，所以大于等于2*b的模a余數為x的數都能取到了…以此類推，因為有a-1種余數，所以最后一個取到的余數是(a-1)*b%a，這個余數的上一個數是(a-1)*b-a，所以答案就是這個

• day1 T2 時間復雜度（complexity）
  https://www.luogu.org/problemnew/show/P3952
  快速的打完T1，就可以開T2了，一看T2，感覺就是一道模擬題嘛，考驗代碼精細的時候到了。根據題意，很自然的想到維護一個棧來處理，用幾個變量記錄是否有語法錯誤、最大的答案，在退棧的時候清空數組，讀入的時候寫的有條理一點，就好了

• day1 T3 逛公園（park）
  https://www.luogu.org/problemnew/show/P3953
  不到1個小時打完T1、T2，就摩拳擦掌的準備T3了，T3是什么啊？一看到題目，有點懵逼，暴力模擬顯然是不能過的，因為方案數還要模，那肯定是很多的吧，那么考慮dp，f[i][j]表示到了第i個點，還可以繞遠j的距離的方案數，因為n<=100000,k<=50,O(n*k)顯然沒問題，那么好了，正著、倒著一遍最短路是不能避免的。然而看到題，還有無數解的情況，怎么樣會無數解呢？那就是你發現走到一個地方，發現有0環，那么就可以在0環上無線繞，方案就有無限種了，但是發現，出現0環并不一定是影響答案的，只有在路徑長度<=最短路長度+k的路徑上的0環上的點才會影響答案。一開始我想錯了，打了半個小時。后來把dp、spfa都打好了，就差一個判無限方案情況。事后得知判0環其實也可以找出所有有用邊、點，把0邊拖出來拓撲判環就好了，但是我考場上沒有想清楚，直接拓撲，所以從0環上指出來的0邊指向的點會被我判在0環上，所以我的公式：起點到他的最短路+終點到他的最短路<=起點到終點的最短路+K不能完全得到應用。在民間數據中我的T3沒有被卡，但是不知道官方數據會不會卡。

day1的考試我剩下了一個小時，最后在那里手構數據，檢查代碼、freopen，進行對拍，卻沒想到T3會有正確性問題，希望官方數據出來后day1能考的好一點

NOIP2017復賽day2

考完了day1休息了半天，和大家一起揣摩T2可能考什么題目，day1不是很難，day2可能就要出難題了，終于，day2開始了~

• day2 T1 奶酪（cheese）
  https://www.luogu.org/problemnew/show/P3958
  day2T1,看到距離公式，嚇的以為是計算幾何，但是仔細一看其實是一個并查集的題目，最后看到下表面和上表面是否并查集的值相同就好了

• day2 T2 寶藏（treasure）
  https://www.luogu.org/problemnew/show/P3959
  T2，n那么小，就覺得是狀壓dp，但是狀態怎么表示呢?我想了一個方法，并且打完了，小樣例過了，大樣例卻沒過，仔細一想，正確性好像有問題，我f[i][j][k]表示現在的取到的點的狀態是i，枚舉到第j個點，j這個點的深度是k，但是轉移感覺不會寫，然后就掛了。最后我交上去了一個所有V相同的部分分，枚舉每一個起點BFS貪心的取，不知能拿多少分。事后得知這一題爆搜加剪枝就能拿很多分，而BFS的狀壓可以過掉此題。

• day2 T3 列隊（phalanx）
  https://www.luogu.org/problemnew/show/P3960
  T3感覺是數據結構題，但實在不知道怎么做，分塊？應該能拿到1e5時的分，暴力，優化一下內存能拿50分，加起來就有80分了，然而我打的時候內存優化（set維護哪些被用過）出了點問題，然后最后只有30分了。問一個dalao怎么數據結構，他說用treap維護，spilit一下就好，只是可能還是會T，線段樹加二分就好。

縱觀day2,不是很順，T2T3都和正解擦肩而過，部分分也沒打好，還是要提升代碼能力，要是T3部分分打出來了，正解該是也很好打的吧。

總結

NOIP2017結束了，day2實在是考的不盡如人意，沒有打好暴力，就落得如此下場，day2T2死磕太久，導致時間不夠，day1T3正確性沒得到保證，說明思路的嚴密性還不夠，所以以后要培養判斷一個算法正確性的能力吧。

后記

NOIP成績已出，100+100+70+100+15+40=425，很是一般，不過無妨，明年加油！

總結

以上是生活随笔為你收集整理的NOIP2017提高组比赛总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。