本文分享的必刷題目是從藍(lán)橋云課、洛谷、AcWing等知名刷題平臺精心挑選而來并結(jié)合各平臺提供的算法標(biāo)簽和難度等級進行了系統(tǒng)分類。題目涵蓋了從基礎(chǔ)到進階的多種算法和數(shù)據(jù)結(jié)構(gòu)旨在為不同階段的編程學(xué)習(xí)者提供一條清晰、平穩(wěn)的學(xué)習(xí)提升路徑。歡迎大家訂閱我的專欄算法題解C與Python實現(xiàn)附上匯總貼算法競賽備考沖刺必刷題C | 匯總【題目來源】洛谷P10132 [USACO24JAN] Cannonball B - 洛谷【題目描述】Bessie 已經(jīng)精通了變成炮彈并沿著長度為N NN1 ≤ N ≤ 10 5 1\le N\le 10^51≤N≤105的數(shù)軸彈跳的藝術(shù)數(shù)軸上的位置從左到右編號為1 , 2 , ? , N 1,2,\cdots,N1,2,?,N。她從某個整數(shù)位置S SS1 ≤ S ≤ N 1\le S\le N1≤S≤N開始以1 11的起始能量向右彈跳。如果 Bessie 的能量為k kk則她將彈跳至距當(dāng)前位置向前距離k kk處進行下一次彈跳。從1 11到N NN的每個整數(shù)位置上均有炮擊目標(biāo)或跳板。每個炮擊目標(biāo)和跳板都有一個在0 00到N NN范圍內(nèi)的整數(shù)值。一個數(shù)值為v vv的跳板會使 Bessie 的能量增加v vv并反轉(zhuǎn)她的方向。一個數(shù)值為v vv的炮擊目標(biāo)會當(dāng)著陸時能量不小于v vv時被擊破。著陸在炮擊目標(biāo)上不會改變 Bessie 的能量和方向。被擊破的炮擊目標(biāo)將保持擊破狀態(tài)Bessie 依然可以該炮擊目標(biāo)上彈跳同樣不會改變能量和方向。如果 Bessie 彈跳無限長的時間或直到她離開數(shù)軸她會擊破多少個炮擊目標(biāo)如果 Bessie 開始時位于一個她可以擊破的炮擊目標(biāo)她會立刻這樣做。類似地如果 Bessie 開始時位于一個跳板跳板的效果將在她第一次跳躍之前生效?！据斎搿枯斎氲牡谝恍邪琋 NN和S SS其中N NN為數(shù)軸的長度S SS為 Bessie 的起始位置。以下N NN行描述了每一個位置。其中第i ii行包含整數(shù)q i q_iqi?和v i v_ivi?如果位置i ii上有一個跳板則q i 0 q_i0qi?0位置i ii上有一個炮擊目標(biāo)則q i 1 q_i1qi?1v i v_ivi?是位置i ii上的跳板或炮擊目標(biāo)的數(shù)值。【輸出】輸出一個整數(shù)為將被擊破的炮擊目標(biāo)數(shù)量?！据斎霕永? 2 0 1 1 1 1 2 0 1 1 1【輸出樣例】1【核心思想】問題分析Bessie 在一條長為N NN的數(shù)軸上彈跳起始位置S SS初始能量為1 11方向向右。每個位置要么是跳板q i 0 q_i0qi?0數(shù)值v i v_ivi?要么是炮擊目標(biāo)q i 1 q_i1qi?1閾值v i v_ivi?。Bessie 每次以當(dāng)前能量k kk向前跳k kk格若落在跳板上則能量增加v i v_ivi?并反轉(zhuǎn)方向若落在炮擊目標(biāo)上若當(dāng)前能量≥ v i \ge v_i≥vi?則擊破它擊破后仍可停留但不再改變狀態(tài)。求她能擊破的炮擊目標(biāo)總數(shù)。由于能量和方向會不斷變化可能進入無限循環(huán)或最終離開數(shù)軸。核心是模擬彈跳過程并檢測循環(huán)。算法選擇模擬 循環(huán)檢測按規(guī)則逐步模擬 Bessie 的跳躍。關(guān)鍵優(yōu)化是檢測跳板狀態(tài)的重復(fù)——因為只有跳板會改變能量和方向而炮擊目標(biāo)不會改變狀態(tài)。若 Bessie 以相同的能量和方向再次到達同一個跳板則后續(xù)軌跡將完全重復(fù)進入無限循環(huán)此時應(yīng)停止模擬不會再擊破新的目標(biāo)。代碼中用vis和lastpower記錄每個跳板是否被訪問過以及當(dāng)時的力量值若重復(fù)則跳出。炮擊目標(biāo)處理著陸在炮擊目標(biāo)上時若能量足夠則擊破計數(shù)并標(biāo)記為已破將閾值設(shè)為大數(shù)但無論是否擊破Bessie 的能量和方向均不變繼續(xù)下一次跳躍。關(guān)鍵步驟讀入讀取N , S N, SN,S以及每個位置的類型type和數(shù)值val。初始化Bessie 狀態(tài)pos Spower 1dir 1向右。cnt 0擊破數(shù)tot為炮擊目標(biāo)總數(shù)可提前統(tǒng)計用于提前終止。模擬循環(huán)當(dāng)pos在[ 1 , N ] [1, N][1,N]內(nèi)且cnt tot時若當(dāng)前位置是炮擊目標(biāo)若power val且尚未擊破val未被設(shè)為大數(shù)則cnt并將val設(shè)為INF標(biāo)記已破。位置、能量、方向不變。若當(dāng)前位置是跳板循環(huán)檢測若該跳板已被訪問過且記錄的lastpower power則說明進入重復(fù)狀態(tài)跳出循環(huán)。否則記錄vis 1lastpower power。方向反轉(zhuǎn)dir -dir。能量增加power val。計算下一步位置pos dir * power。輸出cnt。時間/空間復(fù)雜度時間復(fù)雜度O ( N 跳躍次數(shù) ) O(N \text{跳躍次數(shù)})O(N跳躍次數(shù))。由于每個跳板狀態(tài)方向能量最多被有效訪問一次重復(fù)即終止跳躍次數(shù)受限于狀態(tài)數(shù)實際可行。空間復(fù)雜度O ( N ) O(N)O(N)存儲每個位置的類型、數(shù)值和跳板的訪問記錄。模擬 循環(huán)檢測的核心思想狀態(tài)關(guān)鍵點Bessie 的狀態(tài)變化只發(fā)生在跳板上炮擊目標(biāo)不會改變狀態(tài)。因此跳板是決定軌跡是否重復(fù)的關(guān)鍵節(jié)點。重復(fù)判定如果 Bessie 以完全相同的能量和方向再次到達同一個跳板那么之后的所有跳躍都將與之前相同進入無限循環(huán)且不會再擊破新的炮擊目標(biāo)。及時檢測并退出可避免無限循環(huán)。炮擊目標(biāo)只影響計數(shù)炮擊目標(biāo)被擊破后只是標(biāo)記為“已破”不影響 Bessie 的物理狀態(tài)所以無需特殊處理除了防止重復(fù)計數(shù)。適用場景適用于“狀態(tài)轉(zhuǎn)移由特定節(jié)點跳板改變其他節(jié)點不影響狀態(tài)”的模擬問題。核心是通過記憶關(guān)鍵節(jié)點的狀態(tài)組合來檢測環(huán)?！舅惴?biāo)簽】#普及- #模擬【代碼詳解】#includebits/stdc.husingnamespacestd;intn;// 房間數(shù)量ints;// 起始房間編號intcnt;// 已擊敗的敵人數(shù)量inttot;// 敵人總數(shù)intstep;// 移動步數(shù)用于調(diào)試或限制循環(huán)次數(shù)// 房間結(jié)構(gòu)體structnode{inttype;// 房間類型0彈簧1敵人intweight;// 房間數(shù)值彈簧的彈力值/敵人的生命值intvis;// 標(biāo)記彈簧是否被訪問過intlastpower;// 上次訪問彈簧時的力量值}p[100005];// 人物結(jié)構(gòu)體structPerson{intdir;// 移動方向1向右-1向左intpower;// 當(dāng)前力量值intpos;// 當(dāng)前位置房間編號};intmain(){// 輸入房間數(shù)量和起始位置cinns;// 輸入每個房間的信息for(inti1;in;i){cinp[i].typep[i].weight;if(p[i].type1){tot;// 統(tǒng)計敵人總數(shù)}}// 初始化貝西的狀態(tài)Person bessie{1,1,s};// 初始方向向右力量為1位置為sintflag0;// 標(biāo)志變量未使用// 主循環(huán)貝西在房間之間移動while(bessie.pos1bessie.posn){// 調(diào)試用的步數(shù)限制注釋掉的代碼// if (step n - 1) break;// 如果已擊敗所有敵人退出循環(huán)if(totcnt){// flag 1;break;}// 調(diào)試輸出注釋掉的代碼// cout pos bessie.pos endl;// cout power bessie.power endl;// 處理敵人房間type1if(p[bessie.pos].type1){// 調(diào)試輸出注釋掉的代碼// cout 1 power bessie.power endl;// 如果力量足夠擊敗敵人if(bessie.powerp[bessie.pos].weight){cnt;// 擊敗敵人計數(shù)加1p[bessie.pos].weight1e9;// 將敵人生命值設(shè)為極大值標(biāo)記為已擊敗}}// 處理彈簧房間type0if(p[bessie.pos].type0){// 調(diào)試輸出注釋掉的代碼// cout 0 power bessie.power endl;// 檢測循環(huán)如果彈簧已被訪問過且力量值相同說明進入死循環(huán)if(p[bessie.pos].vis1bessie.powerp[bessie.pos].lastpower){break;// 退出循環(huán)避免無限循環(huán)}// 改變移動方向bessie.dirbessie.dir*-1;// 標(biāo)記彈簧已被訪問記錄當(dāng)前力量值p[bessie.pos].vis1;p[bessie.pos].lastpowerbessie.power;// 增加力量值彈簧效果bessie.powerbessie.powerp[bessie.pos].weight;}// 移動到下一個位置bessie.posbessie.pos(bessie.dir*bessie.power);step;// 步數(shù)計數(shù)用于調(diào)試或循環(huán)控制}// 輸出擊敗的敵人數(shù)量coutcntendl;return0;}【運行結(jié)果】5 2 0 1 1 1 1 2 0 1 1 1