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