本文分享的必刷題目是從藍(lán)橋云課、洛谷、AcWing等知名刷題平臺精心挑選而來并結(jié)合各平臺提供的算法標(biāo)簽和難度等級進(jìn)行了系統(tǒng)分類。題目涵蓋了從基礎(chǔ)到進(jìn)階的多種算法和數(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處進(jìn)行下一次彈跳。從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 開始時位于一個跳板跳板的效果將在她第一次跳躍之前生效。【輸入】輸入的第一行包含N 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ù)。由于能量和方向會不斷變化可能進(jìn)入無限循環(huán)或最終離開數(shù)軸。核心是模擬彈跳過程并檢測循環(huán)。算法選擇模擬 循環(huán)檢測按規(guī)則逐步模擬 Bessie 的跳躍。關(guān)鍵優(yōu)化是檢測跳板狀態(tài)的重復(fù)——因為只有跳板會改變能量和方向而炮擊目標(biāo)不會改變狀態(tài)。若 Bessie 以相同的能量和方向再次到達(dá)同一個跳板則后續(xù)軌跡將完全重復(fù)進(jìn)入無限循環(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則說明進(jìn)入重復(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ù)實際可行?？臻g復(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 以完全相同的能量和方向再次到達(dá)同一個跳板那么之后的所有跳躍都將與之前相同進(jìn)入無限循環(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)如果彈簧已被訪問過且力量值相同說明進(jì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;}【運(yùn)行結(jié)果】5 2 0 1 1 1 1 2 0 1 1 1