2017年ACM模板（常用）弱渣整理 一、暴力

一、 枚举排列

生成指定集合的排列:

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; void print_per(int n,int *P,int *A,int cur) { if(cur==n) { for(int i=0;i<n;i++) { printf("%d ",A[i]); } printf("\n"); } else for(int i=0;i<n;i++) { if(!i||P[i]!=P[i-1])//最少递归一次，如1,1,1只递归一次 { int c1=0,c2=0; for(int j=0;j<cur;j++) { if(A[j]==P[i]) c1++;//统计c1 } for(int j =0;j<n;j++) { if(P[j]==P[i]) c2++;//统计c2 } if(c1<c2) { A[cur] = P[i]; print_per(n,P,A,cur+1); } } } } int main() { int P[20]; int A[20]; int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&P[i]); } sort(P,P+n); print_per(n,P,A,0); return 0; }

next_ permutation()：

#include<cstdio> #include<algorithm> using namespace std; int main() { int n,p[10]; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&p[i]); } sort(p,p+n); do{ for(int i=0;i<n;i++) printf("%d ",p[i]); printf("\n"); }while(next_permutation(p,p+n)); return 0; }

---

二、 子集生成：

递归：

void print_subset(int n,int* A,int cur) { for(int i=0;i<cur;i++) printf("%d ",A[i]);//打印当前集合 printf("\n"); int s = cur?A[cur-1]+1:0;//确定当前元素的最小可能值 for(int i=s;i<n;i++) { A[cur] = i; print_subset(n,A,cur+1);//递归构造子集 } }

位向量法：

void print_subset(int n,int *B,int cur) { if(cur==n){ for(int i=0;i<n;i++) if(B[i]) printf("%d ",i); printf("\n"); return; } B[cur]=1; print_subset(n,B,cur+1);//选第cur个元素 B[cur]=0; print_subset(n,B,cur+1);//不选第cur个元素 }

二进制法：

#include<cstdio> using namespace std; void print_subset(int n,int s) { for(int i=0;i<n;i++) { if(s&(1<<i)) printf("%d ",i);//二进制的位运算 } printf("\n"); } int main() { int n; scanf("%d",&n); for(int i=0;i<(1<<n);i++) print_subset(n,i); return 0; }