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