一、递归实现指数型枚举（递归）
任意门
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=16;
int n ;
int st[N];//状态，记录每个位置当前的状态，0表示还没考虑，1表示选他，2表示不选他
void dfs(int u)
{
if(u>n)
{
for(int i=1;i<=n;i++)
if(st[i]==1)
printf("%d ",i);
printf("\n");
return;
}
st[u]=2;
dfs(u+1);
st[u]=0;//恢复现场
st[u]=1;
dfs(u+1);
st[u]=0;//恢复现场
return;
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}
二、递归实现排列型枚举（递归）
任意门
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10;
int n;
int state[N];//0表示还没放数，1-n表示放了哪个数
bool used[N];//true表示用过，false表示没有用过
void dfs(int u)
{
if(u>n)
{
for(int i=1;i<=n;i++)
printf("%d ",state[i]);
puts("");
return;
}
for(int i=1;i<=n;i++)
if(!used[i])
{
state[u]=i;
used[i]=true;
dfs(u+1);
state[u]=0;
used[i]=false;
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}
三、简单斐波那契
任意门
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int f[50];
void init()
{
}
int main()
{
int n;
cin>>n;
if(n<1)
return 0;
if(n==1)
cout<<"0"<<endl;
else if(n==2)
cout<<"0 1"<<endl;
else{
f[1]=0;
f[2]=1;
cout<<"0 1";
for(int i=3;i<=n;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<" "<<f[i];
}
}
return 0;
}
四、费解的开关
任意门
#include <bits/stdc++.h>
using namespace std;
const int N=6;//我们这里多开一位
//是因为我们这里是用字符串来读的
//然后字符串最后有一个'\0'
char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};
void turn(int x,int y)
{
for(int i=0;i<5;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=5||b<0||b>=5)
continue;
g[a][b]^=1;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int res=10;
int step=0;
for(int i=0;i<5;i++)cin>>g[i];//相当于字符串的读入，最后还有一个'\0'
for(int op=0;op<32;op++)//因为无法根据第一行灯的亮暗来确定第一行的开关该如何操作，
//所以才要枚举第一行的所有操作方案。
{
memcpy(backup,g,sizeof g);//要记录一下，保留上一个状态
int step=0;
for(int i=0;i<5;i++)
if(op>>i&1)
{
step++;
turn(0,i);
}
for(int i=0;i<4;i++)
for(int j=0;j<5;j++)
{
if(g[i][j]=='0')
{
step++;
turn(i+1,j);
}
}
bool dark=false;
for(int i=0;i<5;i++)
if(g[4][i]=='0')
{
dark=true;
break;
}
if(!dark)res=min(res,step);
memcpy(g,backup,sizeof g);
}
if(res>6)res=-1;
cout<<res<<endl;
}
return 0;
}
五、递归实现组合型枚举
任意门
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=30;
int n,m,k=1,j=0;
int state[N];//0表示还没放数，1-n表示放了哪个数
bool used[N];//true表示用过，false表示没有用过
void dfs(int u,int j)
{
if(u>m)
{
for(int i=1;i<=m;i++)
printf("%d ",state[i]);
puts("");
return;
}
for(int i=j;i<=n;i++)
if(!used[i])
{
state[k++]=i;
used[i]=true;
dfs(u+1,i);
state[k--]=0;
used[i]=false;
}
}
int main()
{
scanf("%d%d",&n,&m);
dfs(1,1);
return 0;
}
六、带分数
任意门
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,ans;
int st[15],backup[15];
bool check(int a,int c)
{
long long b=n*(long long)c-a*c;
if(!a||!b||!c)return false;
memcpy(backup,st,sizeof(st));
while(b)
{
int x=b%10;
if(!x||backup[x])
return false;
backup[x]=true;
b/=10;
}
for(int i=1;i<=9;i++)
{
if(!backup[i])
return false;
}
return true;
}
void dfs_c(int a,int u,int k)
{
if(a>9)return;
if(check(u,k))ans++;
for(int i=1;i<=9;i++)
{
if(!st[i])
{
st[i]=true;
dfs_c(a+1,u,k*10+i);
st[i]=false;
}
}
}
void dfs_a(int a,int u)
{
if(u>=n)return;
if(a)dfs_c(a,u,0);//第三位数表示c的可能值
for(int i=1;i<=9;i++)
if(!st[i])
{
st[i]=true;
dfs_a(a+1,u*10+i);
st[i]=false;
}
}
int main()
{
//n=a+b/c==>b=nc-ac
scanf("%d",&n);
dfs_a(0,0);//第一个数表示位数，第二个数表示数字大小
cout<<ans<<endl;
return 0;
}
七、飞行员兄弟
任意门
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
#include<vector>
using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;
const int N=5;
char g[N][N],backup[N][N];
int get(int x,int y)
{
return x*4+y;
}
void turn_one(int x,int y)
{
if(g[x][y]=='+')g[x][y]='-';
else g[x][y]='+';
}
void turn_all(int x,int y)
{
for(int i=0;i<4;i++)
{
turn_one(x,i);
turn_one(i,y);
}
turn_one(x,y);
}
int main()
{
for(int i=0;i<4;i++)
cin>>g[i];
vector<PII>res;
for(int op=0;op<1<<16;op++)
{
vector<PII>temp;
memcpy(backup,g,sizeof g);//备份
//进行操作
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(op>>get(i,j)&1)
{
temp.push_back({i,j});
turn_all(i,j);
}
//判断所有灯泡是否全亮
bool has_closed=false;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(g[i][j]=='+')
has_closed=true;
if(has_closed==false)
if(res.empty()||res.size()>temp.size())
res=temp;
memcpy(g,backup,sizeof g);
}
cout<<res.size()<<endl;
for(int i=0;i<res.size();i++)
cout<<res[i].x+1<<" "<<res[i].y+1<<endl;
return 0;
}
七、翻硬币
任意门
#include<bits/stdc++.h>
using namespace std;
const int N=110;
char start[N],aim[N];
void turn(int x)
{
if(start[x]=='*')start[x]='o';
else start[x]='*';
}
int main()
{
cin>>start>>aim;
int n=strlen(start);
int res=0;
for(int i=0;i<n-1;i++)
{
if(start[i]!=aim[i])
{
turn(i),turn(i+1);
res++;
}
}
cout<<res<<endl;
return 0;
}
