2020年csp總結

大前言

初三，初中最后一次比賽了，也是 csp-J 的第一次也是最后一次考試，

csp-j

分數

第一題

比賽時發現不符合的就只有 2 0 2^0 20 這一個，然后如果是奇數就輸出 ? 1 -1 ?1，否則就質因數分解就完事了，

賽后說要判斷 0 0 0，然后我沒有判斷，慌得一批，

后來發現資料范圍從 1 1 1 開始，然后就 100 100 100 了，
嚇死，

第二題

第二題一看到分數的范圍只有 600 600 600，就很自然的想到記錄每一個分數有多少人，然后對于每一次直接列舉分數線是多少找到分數線，

就是桶排，復雜度 O ( 600 × n ) O(600\times n) O(600×n)

第三題

第三題看到題目：有被嚇到謝謝，

然后就開始分析題目，發現輸出的答案要么是 1 1 1，要么是 0 0 0，
或者說，要么跟不翻轉時的答案一樣，要么不一樣，

然后就想到要看每個值的改變對答案起不起決定性作用，

然后就搞出了在一個運算中，兩邊要怎么樣才會有哪一邊翻轉對答案有決定性作用，
然后我就發現要讓一個函式它在一個式子中起作用，就是要包含他的運算中，它所在的那一邊一定都要翻轉后對答案有決定性作用，

然后就歡樂模擬了，

第四題

看到是 dp，給歷來 dp 較弱的我加了個油，就開始看題了，

首先看到題目，發現可以弄一個 n 3 n^3 n3 的 dp，直接 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]，表示走到 i i i 列，然后上一行的時候走到了 j j j，這一次走到了 k k k，然后就打了出來，

接著想把中間那一維弄掉，就先看走到這一列的最上面，然后直接上面維護最大值，下面用堆來維護最大值，然后不停的把要走到的點向下移，
（然而這個演算法好像有問題）

本來是想分段用不同的演算法的（因為我自己看自己的演算法后不能保證能對）

結果因為怕 MLE，就只弄了后面想到的演算法，然后就歡樂 30 30 30，

總結

血虧，

首先，第四題沒有想出正解，dp 還是太薄弱了，

第二，NT 的我竟然覺得會 MLE，這就離譜，然后完美的從應有的 370 370 370 掉到了 330 330 330，然后就被一個初二的神仙低了，（sto CXY orz）

第三，第四題本來打了個對拍，結果沒有打這一段：
sytem("sjs.exe");（就是沒有運行生成亂數的程式）
然后一直都是在拍同一組資料，

但起碼有個一等，勉勉強強過得去吧，
害

csp-s

分數

第一題

就是這一題，一分沒拿，裂開，

我看到題目，傻傻的直接想著要直接全部用公式，直接 O ( 1 ) O(1) O(1) 算，

然后我這個憨憨打了兩個多小時還打不出來，

然后反手一個爆蛋，悶聲發大財，

第二題

看了一遍題意，大概覺得是二進制之類的東西，
然后就看每一種糧食買不買，然后用可以搭配出來的全部動物總數減去動物園原有的，就是答案，

然后沒有開 unsigned long long，更沒有特判超過 unsigned long long 的情況，
然后就 75 75 75 分，
（不過好像我判斷數某一位是否為一的位運算也有一些小問題）

第三題

第一題做太久，就沒怎么多想，打了個暴力走人，

第四題

又是第一題做太久，在一開始看題的時候想了一會之后，發現如果最大的蛇打完最小的蛇不是倒數，就會再打，

然是代碼打著打著又發現有的時候最大的蛇就算打了最小的變成了最小，它也會打，因為第二回因為相同的原因不敢打它，

然后我就果斷去調我的第一題了，

總結

提高裂開，

主要是第一題出的問題有點大，

先是總想著直接用公式，就完全沒有想過要列舉年數，
想到時間復雜度的想法但是又很復雜（特別是推公式的時候）一定要想一想有沒有時間長一點的，

而且考場上用推公式的演算法就算打出來了也要分段，把可以暴力的暴力，
（就因為我是個數學菜雞）

第二題一般般吧，雖然說可以 A 的因為細節問題沒有 A 到，但是起碼有分，
不過以后要對資料的大小更加敏感一些，不然就會這樣丟分，

第三第四題，相對來說騙到了一點分，但感覺其實第四題如果有時間可以用遞回來騙 40 40 40 分，看看能不能水多一點的，

總的總結

這次，一般般吧，沒有考的很好，但勉強說得過去，
普及的唯一一次考試，起碼上了 300 300 300 吧，
提高雖然拿不到1=，但起碼也多了很多騙分和比賽經驗，

總的來說，繼續努力，下一年加油吧！