本文分享的必刷題目是從藍(lán)橋云課、洛谷、AcWing等知名刷題平臺(tái)精心挑選而來并結(jié)合各平臺(tái)提供的算法標(biāo)簽和難度等級(jí)進(jìn)行了系統(tǒng)分類。題目涵蓋了從基礎(chǔ)到進(jìn)階的多種算法和數(shù)據(jù)結(jié)構(gòu)旨在為不同階段的編程學(xué)習(xí)者提供一條清晰、平穩(wěn)的學(xué)習(xí)提升路徑。歡迎大家訂閱我的專欄算法題解C與Python實(shí)現(xiàn)附上匯總貼算法競(jìng)賽備考沖刺必刷題C | 匯總【題目來源】洛谷P2693 [USACO1.3] 號(hào)碼鎖 Combination Lock - 洛谷【題目描述】農(nóng)夫約翰的奶牛不停地從他的農(nóng)場(chǎng)中逃出來導(dǎo)致了很多損害。為了防止它們?cè)偬映鰜硭I了一只很大的號(hào)碼鎖以防止奶牛們打開牧場(chǎng)的門。農(nóng)夫約翰知道他的奶牛很聰明所以他希望確保它們不會(huì)在簡(jiǎn)單地試了很多不同的號(hào)碼組合之后就能輕易開鎖。鎖上有三個(gè)轉(zhuǎn)盤每個(gè)上面有數(shù)字 1 ~n因?yàn)檗D(zhuǎn)盤是圓的所以 1 和n是相鄰的。有兩種能開鎖的號(hào)碼組合一種是農(nóng)夫約翰設(shè)定的還有一種“預(yù)設(shè)”號(hào)碼組合是鎖匠設(shè)定的。但是鎖有一定的容錯(cuò)性所以在每個(gè)轉(zhuǎn)盤上的數(shù)字都與一個(gè)合法的號(hào)碼組合中相應(yīng)的數(shù)字相距兩個(gè)位置以內(nèi)時(shí)鎖也會(huì)打開。比如說如果農(nóng)夫約翰的號(hào)碼組合是 1 , 2 , 3 )預(yù)設(shè)號(hào)碼組合是 4 , 5 , 6 )在轉(zhuǎn)盤被設(shè)定為 1 , 4 , 5)因?yàn)檫@和農(nóng)夫約翰的號(hào)碼組合足夠接近或 2 , 4 , 8 )因?yàn)檫@和預(yù)設(shè)號(hào)碼組合足夠接近時(shí)可以打開鎖。注意( 1 , 5 , 6 并不會(huì)打開鎖因?yàn)樗c任一號(hào)碼組合都不夠接近。給出農(nóng)夫約翰的號(hào)碼組合和預(yù)設(shè)號(hào)碼組合請(qǐng)計(jì)算能夠開鎖的不同的號(hào)碼組合的數(shù)目。號(hào)碼是有序的所以 1 , 2 , 3 與 3 , 2 , 1 不同。【輸入】輸入的第一行是一個(gè)整數(shù)n代表鎖上的數(shù)字個(gè)數(shù)。輸入的第二行有三個(gè)整數(shù)x,y,z代表農(nóng)夫約翰的號(hào)碼組合。輸入的第三行有三個(gè)整數(shù)a,b,c代表預(yù)設(shè)的號(hào)碼組合?！据敵觥枯敵鲆恍幸粋€(gè)整數(shù)代表能夠開鎖的組合數(shù)目。【輸入樣例】50 1 2 3 5 6 7【輸出樣例】249【核心思想】問題分析給定三個(gè)轉(zhuǎn)盤的數(shù)字范圍[ 1 , n ] [1, n][1,n]環(huán)形相鄰1 和n nn相鄰以及兩個(gè)合法號(hào)碼組合( x , y , z ) (x, y, z)(x,y,z)和( a , b , c ) (a, b, c)(a,b,c)。鎖的容錯(cuò)規(guī)則為每個(gè)轉(zhuǎn)盤上的數(shù)字與任一合法組合中對(duì)應(yīng)位置數(shù)字的環(huán)形距離≤ 2 \leq 2≤2時(shí)鎖打開。求能開鎖的不同號(hào)碼組合數(shù)。算法選擇暴力枚舉由于n ≤ 100 n \leq 100n≤100三個(gè)轉(zhuǎn)盤的三重循環(huán)枚舉量最大為10 6 10^6106完全可行環(huán)形距離計(jì)算利用模運(yùn)算處理環(huán)形結(jié)構(gòu)計(jì)算兩個(gè)數(shù)字在環(huán)上的最短距離容斥思想分別判斷是否滿足約翰的組合或預(yù)設(shè)的組合滿足任一即可邏輯或關(guān)鍵步驟讀入數(shù)據(jù)n nn數(shù)字個(gè)數(shù)、約翰的組合( x , y , z ) (x, y, z)(x,y,z)、預(yù)設(shè)組合( a , b , c ) (a, b, c)(a,b,c)三重枚舉i , j , k i, j, ki,j,k分別從1 11到n nn枚舉三個(gè)轉(zhuǎn)盤的數(shù)字環(huán)形距離判斷對(duì)單個(gè)轉(zhuǎn)盤位置數(shù)字p pp與q qq的環(huán)形距離( p ? q n ) m o d n (p - q n) \bmod n(p?qn)modn或( q ? p n ) m o d n (q - p n) \bmod n(q?pn)modn取較小值條件( x ? i n ) m o d n ≤ 2 (x - i n) \bmod n \leq 2(x?in)modn≤2或( i ? x n ) m o d n ≤ 2 (i - x n) \bmod n \leq 2(i?xn)modn≤2表示i ii與x xx的環(huán)形距離≤ 2 \leq 2≤2組合判斷滿足約翰組合三個(gè)轉(zhuǎn)盤分別與( x , y , z ) (x, y, z)(x,y,z)的距離均≤ 2 \leq 2≤2邏輯與滿足預(yù)設(shè)組合三個(gè)轉(zhuǎn)盤分別與( a , b , c ) (a, b, c)(a,b,c)的距離均≤ 2 \leq 2≤2邏輯與滿足任一即可開鎖邏輯或統(tǒng)計(jì)答案滿足條件的組合數(shù)a n s ansans時(shí)間/空間復(fù)雜度時(shí)間復(fù)雜度O ( n 3 ) O(n^3)O(n3)三重循環(huán)枚舉所有組合空間復(fù)雜度O ( 1 ) O(1)O(1)僅需常數(shù)級(jí)變量環(huán)形枚舉的核心思想模運(yùn)算處理環(huán)形( p ? q n ) m o d n (p - q n) \bmod n(p?qn)modn消除了環(huán)形結(jié)構(gòu)的邊界問題將 1 和n nn的相鄰關(guān)系統(tǒng)一處理雙向距離取小兩個(gè)方向( p ? q n ) % n (p-qn)\%n(p?qn)%n和( q ? p n ) % n (q-pn)\%n(q?pn)%n分別表示順時(shí)針和逆時(shí)針距離滿足其一≤ 2 \leq 2≤2即表示在容錯(cuò)范圍內(nèi)容斥簡(jiǎn)化無需顯式計(jì)算并集直接用邏輯或判斷滿足約翰或滿足預(yù)設(shè)即可小規(guī)模暴力可行n ≤ 100 n \leq 100n≤100時(shí)n 3 10 6 n^3 10^6n3106在合理范圍內(nèi)無需復(fù)雜優(yōu)化適用于環(huán)形結(jié)構(gòu)、小范圍枚舉、多條件容斥類問題【解題思路】【算法標(biāo)簽】#普及- #模擬【代碼詳解】#includebits/stdc.husingnamespacestd;intn,x,y,z,a,b,c,ans0;intmain(){cinn;// 輸入ncinxyz;// 輸入約翰的號(hào)碼組合cinabc;// 輸入預(yù)設(shè)的號(hào)碼組合for(inti1;in;i){// 三個(gè)轉(zhuǎn)盤使用三個(gè)for循環(huán)for(intj1;jn;j){for(intk1;kn;k){if(((x-in)%n2||(i-xn)%n2)((y-jn)%n2||(j-yn)%n2)((z-kn)%n2||(k-zn)%n2)||((a-in)%n2||(i-an)%n2)((b-jn)%n2||(j-bn)%n2)((c-kn)%n2||(k-cn)%n2)){// 滿足轉(zhuǎn)盤向上或向下后的移動(dòng)次數(shù)需要小于等于2ans;// 方案數(shù)自增1}}}}coutansendl;// 輸出結(jié)果return0;}【運(yùn)行結(jié)果】50 1 2 3 5 6 7 249