P1706 全排列问题

#include<iostream>
using namespace std;
int n;
int v[10];//标记i有没被选中
int a[10];//记录最终的序列

void dfs(int k) { //层级，序列中已经有了几个数字
    if(k>n){//k==n+1
        for(int i=1;i<=n;i++){
            printf("%5d",a[i]);
        } 
        printf("\n");
        return;
    } 
    for(int i=1;i<=n;i++){
        if(!v[i]){//没有被选中的数字 
            v[i]=1;
            a[k]=i;
            dfs(k+1); 
            v[i]=0;//复原 
            a[k]=0;//可以省略 
        }
    }
    return; 
}

int main() {
    scanf("%d",&n);
    dfs(1);
    return 0;
}

STL：next_permutation

 1 #include<iostream>
 2 #include<algorithm>//使用 next_permutation()和sort()需要导入的头文件 
 3 using namespace std;
 4 int main(){
 5     int a[4]={2,1,4,3};
 6     
 7     sort(a,a+4);//对数组排序 
 8     
 9     do{
10         for(int i=0;i<4;i++){//打印排列 
11             cout<<a[i]<<' ';
12         }
13         cout<<endl;
14     }while(next_permutation(a,a+4));//获取下一个排列 
15 }

子集生成《算法竞赛入门经典》188页

需要大量做题以后才能够总结、掌握、理解，新课讲授时候可暂时略过

增量构造法

位向量法

二进制法（需要熟练掌握位运算）

P1219. [USACO1.5] 八皇后 Checker Challenge

 1 #include<iostream>
 2 using namespace std;
 3 int n;
 4 int tot=0;
 5 int a[15];
 6 void search(int k) {
 7     if(k>n) {
 8         tot++;//递归的边界，走到这一步必然符合条件
 9         if(tot<4) {
10             for(int i=1; i<=n; i++) {
11                 cout<<a[i]<<' ';
12             }
13             cout<<endl;
14         }
15         return;
16     }
17     for(int i=1; i<=n; i++) {
18         int ok=1;
19         a[k]=i;//把第k行的皇后放在i列
20         int ux=k;
21         int uy=i;
22         for(int j=1; j<k; j++) {
23             int vx=j;
24             int vy=a[j];
25             if(uy==vy||ux+uy==vx+vy||ux-uy==vx-vy) {//列冲突，左、右对角线冲突
26                 ok=0;
27                 break;
28             }
29         }
30         if(ok) search(k+1);
31     }
32     return;
33 }
34 int main() {
35     cin>>n;
36     search(1);
37     cout<<tot;
38     return 0;
39 }

 1 #include<iostream>
 2 using namespace std;
 3 int n;
 4 int tot=0;
 5 int a[15];
 6 int vy[30],vl[30],vr[30];
 7 void search(int k) {
 8     if(k>n) {
 9         tot++;//递归的边界，走到这一步必然符合条件
10         if(tot<4) {
11             for(int i=1; i<=n; i++) {
12                 cout<<a[i]<<' ';
13             }
14             cout<<endl;
15         }
16         return;
17     }
18     for(int i=1; i<=n; i++) {
19         int x=k;
20         int y=i;
21         if(!vy[y]&&!vl[x+y]&&!vr[x-y+n]) {
22             a[k]=i;
23             vy[y]=1;
24             vl[x+y]=1;
25             vr[x-y+n]=1;
26             search(k+1);
27             vy[y]=0;
28             vl[x+y]=0;
29             vr[x-y+n]=0;
30         }
31     }
32     return;
33 }
34 int main() {
35     cin>>n;
36     search(1);
37     cout<<tot;
38     return 0;
39 }

526互联

深度优先搜索DFS与回溯

P1706 全排列问题

子集生成《算法竞赛入门经典》188页

P1219. [USACO1.5] 八皇后 Checker Challenge