CCF NOI plus 201(7)6 初赛题 解题报告
GTMDCCF。
今年這題怎么評價？
去看我在知乎的回答：https://www.zhihu.com/question/66621360/answer/244222388
挨個說一遍。
單項選擇題
T1.CCF有毒，我一個cpp選手有什么義務去關注pascal的存亡問題？挺讓我震驚的，雖然我知道這個時間。
2022年。
T2.補碼，考前正好復習到了這個考點，這個數是10101011，顯然它是負數，所以補碼等于反碼+1.
反碼為除符號位外按位取反，這樣就得到了11010100，補碼就是11010101，-(2^0 + 2^2 + 2^4 + 2^6) = -85.
T3.說實話一開始拿到這個題我是懵逼的，但其實一想發現，16位，16位。。嗯，8個二進制位是1byte，這樣一個16位是不是2啊。。
那我試試1600*900*2/1024？噫，還真算出來了。
T4.喪心病狂的推建國日的星期，我反正沒推出來。。查日歷可得是星期六。
T5.好題。有一個連通圖有n個節點m條邊，問至少刪掉多少邊會使這個圖變成一棵樹。
如果你代數求值會在A和B之間徘徊不定。但是?你可以想啊，樹有什么性質？一棵n個點的樹有n-1條邊啊，那不妨設我們最少需要刪掉x條邊，然后有m-x = n-1,算出x是m-n+1就好了。
T6.這個遞推關系式比去年那個稍微好看點。。
之前我貌似做過一個T(n) = 2T(n/2) + n的，我還記得答案，于是猜測是不是有相似的性質。。這個題，T(n) = 2T(n/2) + nlogn，前邊那個遞歸應該是logn，兩邊乘起來就是C選項，遂選之，居然對了。
T7.后綴表達式，考之前有好多人問我怎么做。。。
我記得老師用的方法是畫樹，這個太麻煩了。。
其實只需要按照每個操作加括號就好，保證每個括號里只有一個運算符外加兩個數，然后把符號相應的移到其所在的右括號之前，刪掉所有括號就是答案。
T8.我不會啊
T9.這個好像是一個排列組合。。我當時算錯了。。。應該選120但我選的96。。。
T10.說實話這題做錯也有我方法有誤的原因。本身這個是一個遞推式可以求通項公式然后再看無限逼近的。。。
我居然想到了畫圖。。。畫圖發現也是無限逼近，但畢竟草圖不精確，鬼知道我定到的點是0.666還是0.618。。
T11.臥槽這題我也做錯了？應該是2n-1。。
T12.這題做對了。。。
強行程序填空。。。從去年開始就是這樣，保不準明年還會有？
從一個地方就能看出來，c語句是給n賦值，而下面正好對應的是對n值的判定，那自然是第三個空填c語句，只有D選項是，選D。
T13.原來是動態規劃的老祖宗數字三角形。這題最早出現在IOI1994，當時難倒了不少人，現在已經成最簡單的例題之一了。。。時代變化真快
當時求的是最小路徑，這個求最大路徑，還不都一樣。。
選A。
T14.人教版高中數學選修2-3第二章，概率有關的內容。我就用平時做題的做法做出來了，挺簡單的。
設事件A = “第一個航班準點”
設事件B = “第二個航班準點”
設事件C = “第三個航班準點”
設事件D = “小明旅行成功”
則有P(A) = 0.9 , P(B) = 0.8 , P(C) = 0.9.
可以推出 P(A的對立面) = 0.1 , P(B的對立面) = 0.2.
（X的對立面應該寫作X上邊一道橫線，我不知道這樣的符號怎么打出來。。。）
由題意可知，第1個航班晚點，第2個航班準點，旅行失敗；且第2個航班晚點，第3個航班準點，旅行失敗
則可以推出P(D的對立面) = P(A的對立面)P(B) + P(B的對立面)P(C)? = 0.08 + 0.18 = 0.26.
則答案P(D) = 1 - P(D的對立面) = 1 - 0.26 = 0.74.
挺簡單吧。
T15.人教版高中數學選修2-3第二章，數學期望有關的內容。
我們知道，期望 =?均值*概率。
我們知道乒乓球平均噴出速度為2個/秒，噴三分鐘平均會出2 * 180 = 360個球
小朋友只能坐在某一節車廂里，一節車廂占整個場地面積的二十分之一，只有球落到車廂里面小朋友才能撿到。
由幾何概型的相關知識，接到球的概率就是二十分之一。
所以期望值 = 360 * 1/20 = 18.?壓軸題并沒有想象中那么難，反倒挺簡單。
?
不定向選擇題
T1.最壞情況下快排會退化，?歸并和堆排序不會退化。
T2.考察棧的常規操作，挨個模擬一下就好。
T3.希爾排序是什么？這題選D。
T4.QAQFortran不是面向對象的！！！！！！！！！！！！！！！！！！！！！！！
T5.GTMD王選，出題人你給我出來。這題選BD。
?
問題求解
T1.變換格子，看起來沒法下手其實挺簡單，瞎jb試試就知道是3步，不可能會有比3步更優的算法了。
T2.傳說中的最小割。最小代價是4，挨個試總能試出來。不同的方案數其實我也是查的，少查了兩種情況。。
?
讀程
T1.一道常規遞歸題，woc這我也做錯了。。。我菜爆了我退群吧。。。直接多算了一個10。。。。答案是15.
T2.?鬼知道這是http://www.cnblogs.com/OIerShawnZhou/p/7449299.html??
T3.第三題是歸并排序求逆序對，本來這題不該錯，因為我初賽之前剛做了一個求逆序對的題。這個答案是8但我查出來是7。。。
結果我數反了。。
T4.好像是數論。。而且據說第二個和第三個的測試數據要循環幾十萬次。。。woc。。
?
程序填空
依照慣例，正確的答案我會標成紅色。
T1.說好的不考高精度除法呢？說好的這東西不在NOIP范圍之內的呢？
沒辦法，憑著感覺走吧。。。
我真不會這個所以。。分析不出來。。
第一空是p[0]? 第二空是?rest< q?第三空是 rest / q?第四空是 rest % q * 10 + p[i]?第五空是?rest % q （我r我居然又寫錯了）
?
T2.驚了，這是拓撲排序。
對BFS了然于心的我很快就把這題一遍做出來了。
第一空的用途是記錄入度，方便以后查找入度為0的點。能很快想到degree[b]++。
第二空所在的循環是用來把所有開始時入度為0的點入隊的，那這個判定條件肯定是判斷某個點是不是入度為0，那么就是 degree[i] == 0?了。
第三空就是拓撲排序的主過程了，是一個裸的bfs。這里第三空所處的環境是程序在擴展節點的時候發現一個合法點，后文也明確表示如果這個點的入度變成0就會入隊，那應該不難會想到這個空填的應該是“刪邊”操作，即讓這個點的入度-1，那么就是degree[i]--了。
第四空有人看不出來嗎？可能有人真的看不出來，要知道bfs每次都是要彈出隊首的，但前面的代碼沒有寫這個操作，那自然第四空是需要做這個操作的，否則bfs就結束了。。
讓隊首+1不就相當于原來那個數彈出來了么？所以head++。
第五空就是去尋找最長路了。自然程序會把求得的答案放在len[a]里，我們要更新ans以便于輸出，所以這里的判斷條件應該就是，如果當前求得的這個值比ans大，那就讓ans更新為這個值。
所以，len[a] > ans 。
?
47.5分。。。。。應該。。。。不會。。。。出事。。。。吧。。。。吧。。。。吧。。。。
我。。。很。。。慌。。。張。。。啊。。。。
轉載于:https://www.cnblogs.com/OIerShawnZhou/p/7668499.html
總結
以上是生活随笔為你收集整理的CCF NOI plus 201(7)6 初赛题 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Educational Codeforc
- 下一篇： XVII Open Cup named