T1:問題 A: 組合的輸出

題目描述

排列與組合是常用的數學方法，其中組合就是從 n 個元素中抽出 r 個元素(不分順序且 r<＝n)，我們可以簡單地將 n 個元素理解為自然數 1，2，…，n，從中任取 r 個數。
現要求你用遞歸的方法輸出所有組合。
例如 n＝5，r＝3，所有組合為：
l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

輸入

一行兩個自然數 n、r(1<n<21，1<＝r<＝n)。

輸出

所有的組合，每一個組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字符的位置，所有的組合也按字典順序。

樣例輸入

5 3

樣例輸出

??1 ?2 ?3

??1 ?2 ?4

??1 ?2 ?5

??1 ?3 ?4

??1 ?3 ?5

??1 ?4 ?5

??2 ?3 ?4

??2 ?3 ?5

??2 ?4 ?5

??3 ?4 ?5

題解

這道題考察了排列數的問題。只需要用一個pd數組來枚舉每一層（每一位）選什么數，再用一個VIS數組來記錄是否選過，若沒選則選，否則下一個。注意可能用快讀快寫優化時間。

參考代碼

#include<cstdio> using namespace std; int n,r,x[100],vis[100]; void dfs(int k) {if(k==r+1){for(int i=1;i<=r;i++)printf("%3d",x[i]);printf("\n");return ;}for(int i=x[k-1]+1;i<=n;i++){if(!vis[i]){vis[i]=1;x[k]=i;dfs(k+1);vis[i]=0;}} } int main() {scanf("%d%d",&n,&r);dfs(1);return 0; }

T2：問題 B: 門票問題

題目描述

??? 有很多人在門口排隊,每個人將會被發到一個有效的通行密碼作為門票。一個有效的密碼由L(3≤L≤15）個小寫英文字母組成，至少有一個元音（a、e、i、o或u）和兩個輔音（除去元音以為的音節），并且是按字母表順序出現的（例如abc是有效的，而bac不是）。
??? 現在給定一個期望長度為L和C(1≤C≤26）個小寫字母，寫一個程序，輸出所有的長度為L、能由所給頂的C個字母組成的有效密碼。密碼必須按字母表順序打印出來，一行一個。

輸入

??? 第1行是兩個由一個空格分開的正整數,L和C,3≤L≤15，1≤C≤26。
??? 第2行是C個由一個空格隔開的小寫字母密碼是由這個字母集中的字母來構建的。

輸出

??? 若干行，每行輸出一個長度為L個字符的密碼(沒有空格)。輸出行必須按照字母順序排列。程序只需要輸出前25000個有效密碼，即使后面還存在有效密碼。

樣例輸入

4 6

a t c i s w

樣例輸出

acis

acit

aciw

acst

acsw

actw

aist

aisw

aitw

astw

cist

cisw

citw

istw

題解

本題與上一道題相比，多了一些要求：至少一個元音，2個輔音。因此我們可以在搜索的過程中來剪枝。首先可以維護一個前綴和（倒著的），表示后面元音的個數。搜索過程中，如果當前枚舉到了k，前面沒有元音，而后面也沒有元音了（前綴和），那么就可以直接return。同理，輔音的處理與這個類似，只不過是個數<2。同時如果接下來的字母都用上，還達不到既定長度，那么也return。有了3重剪枝，就能極大的優化時間效率。

參考代碼

#include<cstdio> #include<algorithm> using namespace std; int l,c,x[100],seg[500],p[100],vis[100],tot=0; char s[100];int pd1[500],pd2[500],sis=0,ht[500]; bool pd(int k) { return k=='a'||k=='e'||k=='i'||k=='o'||k=='u'; } void dfs(int k) {if(tot>25000) return;pd1[k]=pd1[k-1];pd2[k]=pd2[k-1];if(k==l+1){if(pd1[k]==0||pd2[k]<2) return;tot++;if(tot>25000) return;for(int i=1;i<=l;i++)putchar(p[i]);printf("\n");return;}for(int i=seg[p[k-1]]+1;i<=c;i++){if(tot>25000) return;if(vis[i]) continue;if(i==sis&&pd1[k]==0) break;if(pd2[k]+ht[i]<2) break;if(c-i+1+k<l) break;vis[i]=1;p[k]=x[i];if(pd(x[i])) {pd1[k]++;dfs(k+1);pd1[k]--;}else{pd2[k]++;dfs(k+1);pd2[k]--;}vis[i]=0;} } int main() {scanf("%d%d",&l,&c);for(int i=1;i<=c;i++){scanf("%s",s);x[i]=s[0];} sort(x+1,x+c+1);for(int i=c;i>=1;i--) {seg[x[i]]=i;ht[i]=ht[i+1];if(pd(x[i])&&sis==0)sis=i+1;if(!pd(x[i]))ht[i]++;}dfs(1);return 0; }

T3：問題 C: 子集和問題

題目描述

子集和問題的一個實例為〈S,c〉。其中，S={ x1， x2，…， xn}是一個正整數的集合，c是一個正整數。子集和問題判定是否存在S的一個子集S1，使得子集S1和等于c。
對于給定的正整數的集合S={ x1， x2，…， xn}和正整數c，編程計算S 的一個子集S1，使得子集S1和等于c。

輸入

第1行有2個正整數n和c，n表示S的個數，c是子集和的目標值。

接下來的1 行中，有n個正整數，表示集合S中的元素。

n<=8000 c<=10^7

輸出

子集，各元素之間用空格隔開。當問題無解時，輸出“No solution!”。

樣例輸入

5 10

2 2 6 5 4

樣例輸出

2 2 6

題解

這道題忽略數據范圍吧?，F在只考慮怎么完成這道題。同樣的，用一個pd數組維護sum，如果sum=c就全部return。當然，還要用x數組記錄所選的元素。這樣還不夠，需要一點小剪枝。如果此刻的sum大于c，return；如果后面的數的和加上sum都小于c，那么也沒必要繼續搜了，直接return。如此就能找到一組答案就退出，或者輸出問題無解。

參考代碼

#include<cstdio> #define LL long long using namespace std; int n,c,a[10000],sum=0,sum1[10000]; int pd=0,x[10000]; void dfs(int k) {if(sum+sum1[n]-sum1[x[k-1]]<c) return;if(pd==1) return;if(sum==c){for(int i=1;i<k;i++) printf("%d ",a[x[i]]);pd=1;return;}for(int i=x[k-1]+1;i<=n;i++){x[k]=i;if(sum+a[i]>c) continue;sum+=a[i];dfs(k+1);sum-=a[i];} } int main() {scanf("%d%d",&n,&c);for(LL i=1;i<=n;i++) {scanf("%d",&a[i]);sum1[i]=sum1[i-1]+a[i];}dfs(1);if(pd==0) printf("No Solution!");return 0; }

T5：問題 E: 數獨

題目描述

數獨是一種傳統益智游戲，你需要把一個9 × 9的數獨補充完整，使得圖中每行、每列、每個3 × 3的九宮格內數字1~9均恰好出現一次。

請編寫一個程序填寫數獨。

?

輸入

輸入包含多組測試用例。

每個測試用例占一行，包含81個字符，代表數獨的81個格內數據（順序總體由上到下，同行由左到右）。

每個字符都是一個數字（1-9）或一個”.”（表示尚未填充）。

您可以假設輸入中的每個謎題都只有一個解決方案。

文件結尾處為包含單詞“end”的單行，表示輸入結束。

輸出

每個測試用例，輸出一行數據，代表填充完全后的數獨。

樣例輸入

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.

......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.

樣例輸出

527389416819426735436751829375692184194538267268174593643217958951843672782965341

416837529982465371735129468571298643293746185864351297647913852359682714128574936

題解

????????對于這道題我也算是頗有心得。我的代碼對于單個的九宮格不輸任何表答，但就是要跑2s！！所有我這個代碼無法過數獨這道題（淚流滿面，蒟蒻的悲傷~）?，F在來談談這道題。首先用一個e_map存一下地圖，然后把每一行、每一列、每一個3*3方塊壓縮成二進制保存下來。再把每一行還沒有填的格子記錄一下（這樣就不用重復找已經填過的數），然后就搜唄。

????????搜的話很簡單了，只用在（橫著的沒填的、豎著的沒填的、方塊里沒填的）求交集，然后枚舉數字即可。注意，是！沒！填！的！因此我們直接把之前二進制壓縮的結果亦或（^）511（二進制111111111）就可以了，相當于全部取個反（現實意義）。處理了這一位的數字后，來考慮下一次枚舉那一個位置。這時我就直接用了一個！！！大優化！！！就是每次把每一行能取的位置倒著枚舉，然后……直接取，并且把當前行的總共能填的總數-1，并且在回溯之后加回去就可以了。這一步十分精妙，可以動態剪枝，并且由于我的每一行總數組不變，變的只是尾指針，因此答案也是正確的，這部分參見代碼中search函數。

?????????為了進一步優化，我還用冒泡排序（個人認為應該用快排，可能會快一些，但是……寫不來那種）把每一行的能取的位置排了個序，關鍵字就是這個位置能填的數的可能性，可能性越小，說明需要回溯的機會越少，也就能越快的找到答案。還有一個明顯的優化，就是找到了唯一的一組解后，直接return，并且要讓所有正在運行的函數全部return，因此我定義了ed，當ed=1時，表示答案已找到，此時我在大量的區域做了ed的判斷（其實就2處），加快return的速度。對于找數字，此處還運用了lowbit的知識來優化選擇，有興趣者可以自行查閱，不用lowbit也能跑，for就行了，但是時間效率就會損失的比較多。

????????還有一點，用tot存一下此刻還有多少空格沒有選，當tot=0時表示答案已經出現，此刻更新ed，并且輸出答案。特別注意各個函數的初始化，這點十分重要。至于那幾個輸出的函數，只是為了驗算一些東西，可自行理解。如何處理3*3的塊？如果看過代碼（…………此處省略一萬字），就能發現我的數組的更新就解釋了這一點。（x+2）/3能夠準確表示這是上中下的那一塊區域，同理對于y也能確定在哪一豎行。

????????代碼最后可以計算出單純dfs的運行時間，我就是通過這個來判斷時間的，注意最后的輸出毫秒是浮點數，要用ctime的頭文件。最后為了提速，還用了各種方法，只是效果皆不明顯，此處就省略了。最后注意！！！這代碼能很快求一個的答案，卻沒法過！！！?

? ? ? ? 對了，這個代碼最后有很多我自己找的數據，答案可用下面代碼對拍。

參考代碼

#include<cstdio> #include<ctime> #include<iostream> using namespace std; char s[2000];int e_map[10][10],tot_x[10],max0=-1,tot=0; int tick_x[20],tick_y[20],tick_k[5][5],st_x,st_y; int max1(int p,int q) { return p>q?p:q; } int ed=0,lg[1025],went[10][10],goes[10]; void outputing() {for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)printf("%d",e_map[i][j]);printf("\n"); } void output2() {for(int i=1;i<=9;i++){for(int j=1;j<=9;j++)printf("%d",e_map[i][j]);printf("\n"); }printf("\n"); } void output3(int k) {for(int i=1;i<=9;i++){printf("%d",k%2);k/=2;}printf("\n"); } int search() {for(int i=1;i<=9;i++){for(int k=goes[i];k>=1;k--){int j=went[i][k];st_x=i;st_y=j;goes[i]--;return i;//找到一個直接取位置就可以//后面會把goes再加回去}} } void dfs(int x,int y) {if(ed==1) return;if(tot==0){outputing();ed=1;return;}int ttt=tick_x[x]^511;//取反while(ttt){if(ed==1) return;int pk=ttt&-ttt;ttt-=pk;//lowbit取數if((pk&tick_y[y])) continue;if((pk&tick_k[(x+2)/3][(y+2)/3])) continue;//行、列、塊不沖突tick_x[x]|=pk;tick_y[y]|=pk;tick_k[(x+2)/3][(y+2)/3]|=pk;//短暫更新地圖（行列塊）的數據e_map[x][y]=lg[pk];tot--;int rst=search();dfs(st_x,st_y);//把取出來的數“放回去”，關鍵的一步剪枝goes[rst]++;tot++;tick_x[x]^=pk;tick_y[y]^=pk;tick_k[(x+2)/3][(y+2)/3]^=pk;//回溯需要還原e_map[x][y]=0;} } int main() {lg[1]=1;lg[2]=2;lg[4]=3;lg[8]=4;lg[16]=5;lg[32]=6;lg[64]=7;lg[128]=8;lg[256]=9;//為lowbit的計算做準備while(1){tot=ed=max0=0;scanf("%s",s);if(s[0]=='e') break;for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)tick_k[i][j]=0;//數組初始化for(int i=1;i<=9;i++){goes[i]=0;//每一行尾指針tick_x[i]=0;tick_y[i]=0;for(int j=1;j<=9;j++)went[i][j]=0;}for(int i=1;i<=9;i++)for(int j=1;j<=9;j++){if(s[(i-1)*9+j-1]=='.'){went[i][++goes[i]]=j;//記錄每一行合法位置e_map[i][j]=0;tot++;}else {//二進制壓縮e_map[i][j]=s[(i-1)*9+j-1]-'0';tick_x[i]|=(1<<(e_map[i][j]-1));tick_y[j]|=(1<<(e_map[i][j]-1));tick_k[(i+2)/3][(j+2)/3]|=(1<<(e_map[i][j]-1));}}//冒泡排序for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)for(int k=1;k<=9;k++)if(went[i][j]>went[i][k]){int c=went[i][k];went[i][k]=went[i][j];went[i][j]=c;}search();//找出初始位置 // clock_t t; // t=clock();dfs(st_x,st_y); // t=clock()-t; // cout<<"時間為："<<(((float)t)/CLOCKS_PER_SEC*1000)<<"ms\n"; //記錄dfs時間}return 0; }................................................................................. .2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534. ......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3. 1.3...5.9..21.94.....7.4...3..5.2..6.6.....5.7..8.3..4...4.1.....92.58..8.4...1.7 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. ..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97.. 98.7..6..7......8...6.5....4....3.....89...7.....2.3...1....2....75...6......1.54 .3...7..46.2.41....5..3.967.4...3..6.87...35.9..7...2.718.2..4....16.8.94..5...3. ..5..43.1..........28..6.4....4.5...7......6.6......3...3...17....1.9.....9..2..8 .6.....75....4..9.8.3........8.9.....72..6...6..4.5...12.6......3..7.2....7..431. ...8......3..92..1.9..3....7...498....57..9..2....6.....352.1...5....4.2..6..4... 43.28...............84...1.9.3..2.4..7..3..2..5.9..8.1.2...65...............41.76 57.12...............67...8.3.4..9.7..2..7..5..1.3..9.2.8...21...............54.63 ...6....7...849...28......5..7315....4..7......2......91..8..6.7......9...34..5.. 75..9..469.1...3.2.........2..6.1..7.8.....2.1..3.8..5.........3.9...2.484..3..79 end

總結

以上是生活随笔為你收集整理的2021 9.14 p.m.小结 以及 数独问题探索（T3）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。