1. 項目概述為什么我們需要復(fù)盤2020年藍(lán)橋杯國賽填空題如果你是參加過藍(lán)橋杯或者正在備賽的選手看到“2020年藍(lán)橋杯B組國賽填空題整理”這個標(biāo)題大概會心一笑。這玩意兒懂的都懂。它不像那些動輒幾百行代碼的大題有完整的題目描述和輸入輸出樣例。填空題往往就藏在試卷的角落里題干可能只有一兩行但背后考察的知識點卻可能非常刁鉆或者需要巧妙的數(shù)學(xué)思維和編程技巧才能快速求解。很多人考完試大題思路還記得填空的答案卻模糊了更別提完整的解題過程。所以系統(tǒng)性地整理、復(fù)盤某一年的國賽填空題其價值遠(yuǎn)超“對答案”本身。我之所以花時間整理2020年B組國賽的填空是因為這一年的題目在命題思路上有很強的代表性。它承接著前幾年算法競賽普及化的趨勢又明顯加強了對基礎(chǔ)數(shù)學(xué)、邏輯思維和邊界條件處理的考察。很多題目你暴力枚舉不是不行但時間復(fù)雜度和比賽時的心理壓力會讓你崩潰。而一旦掌握了正確的思路可能就是幾行代碼的事。這份整理目的就是把這些“正確的思路”以及我當(dāng)時踩過的坑、想到的優(yōu)化點毫無保留地分享出來。無論你是想了解國賽難度查漏補缺還是為下一屆比賽做準(zhǔn)備這份基于實戰(zhàn)的復(fù)盤都能給你提供一個清晰的“作戰(zhàn)地圖”。2. 核心考點與命題趨勢深度解析要有效復(fù)盤不能就題論題。我們得先站在出題人的角度看看2020年B組國賽填空題到底想考我們什么?？v觀這幾年的藍(lán)橋杯尤其是國賽級別填空題早已不再是“送分題”而是區(qū)分度極高的“思維題”。2.1 從“暴力枚舉”到“數(shù)學(xué)優(yōu)化”的思維躍遷早年的藍(lán)橋杯填空很多題目確實可以通過簡單的循環(huán)甚至手算得出答案。但2020年的題目釋放了一個明確信號無腦暴力在國賽場上是行不通的。命題者精心設(shè)置了數(shù)據(jù)范圍讓你的樸素算法要么超時要么根本無從下手。這就要求我們必須具備將實際問題抽象為數(shù)學(xué)模型并尋找優(yōu)化規(guī)律的能力。例如一道關(guān)于日期計算或者序列生成的題目數(shù)據(jù)范圍可能給到10^9甚至更大。你的for循環(huán)從1跑到10^9比賽時間結(jié)束它都跑不完。這時候考點就變成了你是否能發(fā)現(xiàn)周期律是否能利用容斥原理是否能通過數(shù)位DP或公式推導(dǎo)來避免遍歷這種從“計算機思維”讓我算到“數(shù)學(xué)思維”讓我推的轉(zhuǎn)變是應(yīng)對國賽填空的第一道門檻。2.2 對“邊界條件”和“精度問題”的極致苛求這是藍(lán)橋杯尤其是填空題的“傳統(tǒng)藝能”但在2020年國賽中被強調(diào)到了新的高度。題目描述可能風(fēng)平浪靜但答案往往是一個巨大的整數(shù)或者一個需要特定格式的字符串。這里常見的坑包括開根號與精度涉及浮點數(shù)運算時比較是否相等不能直接用要設(shè)置一個極小的誤差范圍eps。有時甚至需要避免浮點數(shù)全程用整數(shù)處理。大整數(shù)處理答案可能超出int甚至long long的范圍在C/C中需要用到高精度計算或__int128在Java中用BigInteger在Python中則天然支持這也是Python在藍(lán)橋杯中的一個優(yōu)勢。邊界包含與否“從a到b之間”是否包含a和b“第n天”是從0開始還是從1開始計數(shù)這些細(xì)節(jié)直接決定答案的正誤必須在審題時圈出來。初始化與重置在模擬過程中循環(huán)變量的初始值、狀態(tài)數(shù)組的清零時機一個疏忽就會導(dǎo)致滿盤皆輸。2.3 多知識點融合與閱讀理解能力國賽填空的題干可能很短但信息密度極高。一道題可能同時融合了數(shù)論、組合數(shù)學(xué)、字符串處理、DFS/BFS搜索等多個知識點。更“狡猾”的是題目有時會使用一些生活化或跨學(xué)科的術(shù)語來描述一個經(jīng)典的算法問題考驗?zāi)愕膯栴}轉(zhuǎn)化和閱讀理解能力。你能否在短時間內(nèi)透過現(xiàn)象看本質(zhì)識別出這其實是一道“求最大公約數(shù)”、“最短路徑”或“狀態(tài)壓縮”的題目3. 2020年B組國賽填空題精講與實戰(zhàn)復(fù)盤下面我將選取當(dāng)年最具代表性的幾道填空題根據(jù)公開的題目回憶整理進(jìn)行詳細(xì)的思路拆解和代碼實現(xiàn)。請注意由于比賽過去一段時間題目描述和具體數(shù)據(jù)可能與原題有細(xì)微出入但核心考點和解題方法是準(zhǔn)確的。3.1 試題A日期問題考察模擬與邊界處理題目回憶已知某個參照日期是星期X求從該日期之后第N天N是一個很大的數(shù)例如10^9是星期幾。解題思路核心考點取模運算、周期律。星期是以7為周期的循環(huán)。關(guān)鍵技巧無論N有多大我們只關(guān)心N % 7的結(jié)果。因為每過7天星期幾會回到原點。邊界處理需要注意起始星期到目標(biāo)星期的映射。如果起始是星期一記為1那么k天后星期幾的計算公式是(1 k) % 7。如果結(jié)果是0則代表星期日。大數(shù)處理N可能很大直接加到日期上進(jìn)行模擬是不可行的必須用取模。參考代碼Python示例# 假設(shè)起始是星期一用1表示求第N天后是星期幾 def day_of_week(N): week [7, 1, 2, 3, 4, 5, 6] # 索引0對應(yīng)余數(shù)0即星期日方便映射 remainder N % 7 # 因為起始是星期一1所以偏移量是 (1 N) % 7但1已經(jīng)包含在week數(shù)組的排列里了嗎 # 更通用的方法定義起始日星期幾 start start 1 # 星期一 target (start N) % 7 return week[target] # 通過自定義數(shù)組處理余數(shù)0的情況 N 1000000000 print(day_of_week(N))注意這是最簡化的模型。真實題目可能涉及更復(fù)雜的日期背景比如給定具體年月日但核心思想不變尋找周期利用取模。如果涉及年月日可能需要考慮閏年規(guī)則但周期可能不再是簡單的7天而是一年或多年的天數(shù)。這時需要先計算大周期再處理余數(shù)。3.2 試題B矩陣計數(shù)/路徑問題考察DFS/BFS與DP題目回憶在一個n x m的網(wǎng)格中從左上角走到右下角只能向右或向下移動但其中某些格子有障礙物不能通過。求一共有多少種不同的路徑。解題思路核心考點動態(tài)規(guī)劃DP。這是經(jīng)典的“不同路徑II”問題。狀態(tài)定義設(shè)dp[i][j]為從起點(0,0)走到格子(i,j)的路徑數(shù)。狀態(tài)轉(zhuǎn)移如果(i,j)是障礙物則dp[i][j] 0。否則dp[i][j] dp[i-1][j] dp[i][j-1]即從上方或左方走來。初始化dp[0][0] 1如果起點不是障礙。第一行和第一列需要單獨初始化因為它們的路徑只能來自一個方向。優(yōu)化可以使用滾動數(shù)組將空間復(fù)雜度優(yōu)化到O(m)。參考代碼Python示例def unique_paths_with_obstacles(grid): if not grid or grid[0][0] 1: return 0 n, m len(grid), len(grid[0]) dp [[0] * m for _ in range(n)] dp[0][0] 1 # 初始化第一列 for i in range(1, n): if grid[i][0] 0: # 不是障礙 dp[i][0] dp[i-1][0] # 只能從上方來 # 初始化第一行 for j in range(1, m): if grid[0][j] 0: dp[0][j] dp[0][j-1] # 只能從左方來 # 狀態(tài)轉(zhuǎn)移 for i in range(1, n): for j in range(1, m): if grid[i][j] 0: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[n-1][m-1] # 示例0代表空地1代表障礙 grid [ [0,0,0], [0,1,0], [0,0,0] ] print(unique_paths_with_obstacles(grid)) # 輸出應(yīng)為2實操心得這類題在藍(lán)橋杯中非常常見。一定要先判斷起點和終點是否為障礙物這是一個常見的失分點。另外如果n和m很大比如超過100遞歸DFS會超時DP是唯一正解。如果題目要求輸出具體路徑則需要用DFS回溯但填空題通常只求數(shù)量。3.3 試題C數(shù)位相關(guān)或質(zhì)數(shù)問題考察數(shù)論與枚舉優(yōu)化題目回憶求在某個區(qū)間內(nèi)例如1到2020滿足某種特定條件的數(shù)的個數(shù)。條件可能與數(shù)位有關(guān)如包含數(shù)字2或與質(zhì)數(shù)、因子有關(guān)。解題思路核心考點枚舉優(yōu)化、數(shù)位分離、質(zhì)數(shù)篩法。暴力法可行性分析先看數(shù)據(jù)范圍。如果是1到2020暴力枚舉每個數(shù)并檢查是可行的。但如果范圍是1到10^9暴力法就不可行需要數(shù)位DP等高級技巧。2020年國賽B組的數(shù)據(jù)范圍通常會在暴力枚舉的邊界上鼓勵你尋找優(yōu)化。優(yōu)化技巧數(shù)位問題對于“包含數(shù)字X”的問題可以逐位判斷。更復(fù)雜的情況如數(shù)位和、數(shù)位乘積可能需要預(yù)處理。質(zhì)數(shù)問題需要快速判斷一個數(shù)是否為質(zhì)數(shù)。對于小區(qū)間可以用試除法優(yōu)化到sqrt(n)。對于大區(qū)間或需要頻繁判斷必須用埃拉托斯特尼篩法或線性篩預(yù)處理出一個質(zhì)數(shù)布爾數(shù)組。因子問題求約數(shù)個數(shù)、判斷完數(shù)等都需要遍歷可能的因子。優(yōu)化關(guān)鍵是循環(huán)到sqrt(n)即可同時注意完全平方數(shù)的特殊情況。參考代碼判斷質(zhì)數(shù)并計數(shù)示例def is_prime(num): if num 2: return False if num 2 or num 3: return True if num % 2 0 or num % 3 0: return False i 5 # 6k±1 法進(jìn)行試除 while i * i num: if num % i 0 or num % (i 2) 0: return False i 6 return True def count_primes_in_range(start, end): count 0 for num in range(start, end 1): if is_prime(num): count 1 return count # 如果是超大范圍必須用篩法 def count_primes_sieve(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: # 從i*i開始標(biāo)記因為2*i, 3*i ... (i-1)*i 已經(jīng)被更小的質(zhì)數(shù)標(biāo)記過了 for j in range(i * i, n 1, i): is_prime[j] False return sum(is_prime) # 計算True的個數(shù) print(count_primes_in_range(1, 100)) print(count_primes_sieve(1000000)) # 篩法處理百萬級數(shù)據(jù)很快注意事項在比賽中不要自己重復(fù)造輪子。像質(zhì)數(shù)篩、最大公約數(shù)gcd、快速冪這些基礎(chǔ)算法一定要提前準(zhǔn)備好模板代碼比賽時直接套用。判斷質(zhì)數(shù)的循環(huán)條件i * i num比i sqrt(num)更快因為避免了重復(fù)調(diào)用sqrt函數(shù)。3.4 試題D組合數(shù)學(xué)或邏輯推理題題目回憶這類題目往往描述一個游戲或生活場景需要你推導(dǎo)出數(shù)學(xué)公式或進(jìn)行邏輯推理。例如“幾個人握手每兩人之間握一次共握了xx次問有幾個人”解題思路核心考點將文字描述轉(zhuǎn)化為數(shù)學(xué)模型。握手問題本質(zhì)是求組合數(shù) C(n,2) n*(n-1)/2。解題步驟抽象模型仔細(xì)閱讀題目找出核心變量和關(guān)系。是排列順序有關(guān)還是組合順序無關(guān)是等差數(shù)列求和還是等比數(shù)列建立方程根據(jù)條件列出方程或不等式。求解驗證解方程并且注意解必須是正整數(shù)、在合理范圍內(nèi)。有時可能需要枚舉驗證。參考代碼解握手問題方程def solve_handshake(total_handshakes): # 解方程 n*(n-1)/2 total_handshakes # 即 n^2 - n - 2*total 0 import math discriminant 1 8 * total_handshakes n (1 math.isqrt(discriminant)) // 2 # 使用整數(shù)開方取正根 # 驗證 if n * (n - 1) // 2 total_handshakes: return n else: return -1 # 無解 print(solve_handshake(10)) # 輸出5常見問題這類題最容易出錯的地方是漏解或多解。一定要把求得的解代回原題場景驗證看是否符合所有條件比如人數(shù)不能是小數(shù)不能是負(fù)數(shù)。對于更復(fù)雜的邏輯推理題可能需要畫表真值表、狀態(tài)表或編寫簡單的枚舉程序來輔助推理。4. 備賽策略與考場實戰(zhàn)技巧整理真題的目的是為了更好地應(yīng)對未來的比賽?；趯?020年及以往國賽填空題的分析我總結(jié)出以下備賽和應(yīng)試策略。4.1 系統(tǒng)性知識儲備你的彈藥庫填空題覆蓋面廣臨時抱佛腳效果甚微。必須建立系統(tǒng)的知識體系基礎(chǔ)數(shù)論質(zhì)數(shù)判斷與篩法、最大公約數(shù)/最小公倍數(shù)歐幾里得算法、同余定理、快速冪取模。這些是解決很多優(yōu)化問題的基石。組合數(shù)學(xué)排列組合公式、容斥原理、卡特蘭數(shù)、錯排公式等。要理解其應(yīng)用場景而不僅僅是背公式。日期與時間處理閏年判斷、星期幾計算基姆拉爾森公式或蔡勒公式、時間差計算。自己寫一個健壯的日期處理函數(shù)備用。字符串與進(jìn)制轉(zhuǎn)換熟練操作字符串掌握各種進(jìn)制特別是2、8、16進(jìn)制與十進(jìn)制之間的轉(zhuǎn)換。搜索與枚舉優(yōu)化DFS、BFS的基本框架剪枝技巧。對于枚舉題要第一時間分析數(shù)據(jù)范圍判斷暴力是否可行。4.2 高效的解題工作流考場上的時間管理國賽時間緊張?zhí)羁疹}必須快速拿下。建議采用以下步驟審題1-2分鐘圈出關(guān)鍵詞數(shù)據(jù)范圍、求解目標(biāo)個數(shù)、和、最大值、特殊條件“連續(xù)”、“不同”、“至少”。務(wù)必理解題意可舉例驗證自己的理解。思路構(gòu)建2-3分鐘判斷題型模擬、數(shù)學(xué)、搜索、DP。思考暴力法的復(fù)雜度立即尋找優(yōu)化點找規(guī)律、用公式、預(yù)處理。在草稿紙上推演核心步驟。編碼與測試5-8分鐘/題使用提前準(zhǔn)備好的模板。代碼盡量簡潔變量名清晰。編寫完成后立即用題目中的樣例或自己構(gòu)造的小樣例進(jìn)行測試。特別是邊界情況最小值、最大值、特殊情況。驗證與提交1分鐘對于填空題答案通常是整數(shù)或字符串。提交前最后檢查答案格式對嗎大小寫對嗎有沒有多輸出空格或換行對于數(shù)值巨大的答案可以用程序輸出一些中間結(jié)果進(jìn)行合理性驗證比如數(shù)量級是否對。4.3 常見“坑點”自查清單在考場上用這個清單快速掃描你的解題過程能避免很多低級錯誤[ ]數(shù)據(jù)范圍int會不會溢出是否需要long long或高精度[ ]初始化數(shù)組、變量是否在正確的位置初始化了多組數(shù)據(jù)輸入時狀態(tài)是否清空[ ]循環(huán)邊界for循環(huán)的起止點是否正確特別是從0開始還是從1開始。[ ]浮點誤差涉及除法、開方時是否進(jìn)行了精度處理比較是否使用了abs(a-b) eps[ ]多解情況題目是否暗示有多個解你求的是否是題目要求的那一個如最大值、最小值、個數(shù)[ ]輸出格式填空題是直接提交答案但自己測試時是否去掉了多余的調(diào)試輸出5. 從真題到能力如何利用整理資料實現(xiàn)突破僅僅做一遍題看一遍解析收獲是有限的。要讓這份2020年的真題整理發(fā)揮最大價值你需要進(jìn)行“主動式學(xué)習(xí)”。5.1 一題多解與橫向?qū)Ρ葘τ诿恳坏捞羁疹}不滿足于一種解法。例如那道路徑DP題解法一標(biāo)準(zhǔn)的二維DP這是最直觀的。解法二優(yōu)化空間的滾動數(shù)組DP。解法三如果障礙物很少能否用組合數(shù)學(xué)減去經(jīng)過障礙物的路徑 通過對比你能更深刻地理解不同算法在時間和空間上的權(quán)衡以及它們各自適用的場景。把這個習(xí)慣應(yīng)用到所有題目上你的思維會變得非常靈活。5.2 構(gòu)建專屬“錯題本”與“靈感集”準(zhǔn)備一個電子或紙質(zhì)的筆記本專門記錄填空題。錯題本記錄你做錯的、思路卡殼的題。不僅要記正確答案更要分析錯誤原因是知識點漏洞是審題不清還是粗心大意定期回顧避免再犯。靈感集記錄你在解題過程中產(chǎn)生的“妙想”或看到的“巧解”。比如某個數(shù)論問題的特殊結(jié)論某種搜索剪枝的巧妙策略。這些靈感是你未來解題的“火花塞”。5.3 模擬實戰(zhàn)與壓力測試找一段時間完全模擬比賽環(huán)境限時、無外界干擾、使用比賽規(guī)定的編程環(huán)境。專門做一套填空題。做完后嚴(yán)格批改分析時間都花在哪里了哪類題耗時最長。這種壓力測試能暴露出你知識體系和應(yīng)試心理的薄弱環(huán)節(jié)比平時松散的學(xué)習(xí)有效十倍。復(fù)盤2020年藍(lán)橋杯國賽的填空題就像一位棋手在賽后反復(fù)研究棋譜。目的不是記住那幾個具體的答案而是理解對手出題人的布局思路磨練自己的計算能力編程與數(shù)學(xué)并總結(jié)出一套屬于自己的應(yīng)對策略。國賽的填空題往往是智慧與細(xì)心雙重考驗的戰(zhàn)場。希望這份結(jié)合了具體題目分析和通用策略的整理能幫你更好地武裝自己。當(dāng)你再面對空白的答題框時心里有的將不再是迷茫和緊張而是清晰的路徑和十足的把握。剩下的就是用代碼去驗證你的思考了。