递归
两个基本模型:组合型枚举、排列型枚举
1,组合型枚举:用参数start去重
题1 93. 递归实现组合型枚举
#include<iostream>
using namespace std;
const int N=30;
int n,m;
int path[N];
void dfs(int u,int start)
{
if(u==m)
{
for(int i=0;i<m;++i) printf("%d ",path[i]);
printf("\n");
}
for(int i=start;i<n;++i)
{
path[u]=i+1;
dfs(u+1,i+1);
}
}
int main()
{
scanf("%d%d",&n,&m);
dfs(0,0);
return 0;
}
#include<iostream>
using namespace std;
const int N=16;
int n;
int path[N];
void dfs(int u,int start)
{
for(int i=0;i<u;++i) printf("%d ",path[i]);
printf("\n");
for(int i=start;i<n;++i)
{
path[u]=i+1;
dfs(u+1,i+1);
}
}
int main()
{
scanf("%d",&n);
dfs(0,0);
return 0;
}
题3 116. 飞行员兄弟
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N=10;
char g[N][N];
vector<PII> ans,tmp;
void turn(int x,int y)
{
g[x][y]=g[x][y]=='+'?'-':'+';
}
void ch(int x,int y)
{
for(int i=0;i<4;++i)
turn(x,i),turn(i,y);
turn(x,y);
}
void dfs(int x,int y)
{
if(x==3&&y==4)
{
for(int i=0;i<4;++i)
for(int j=0;j<4;++j)
if(g[i][j]=='+') return;
if(ans.empty()||tmp.size()>ans.size())
ans=tmp;
return;
}
if(y==4) ++x,y=0;
//操作把手
ch(x,y);
tmp.push_back({x,y});
dfs(x,y+1);
tmp.pop_back();
ch(x,y);
//不操作把手
dfs(x,y+1);
}
int main()
{
for(int i=0;i<4;++i) scanf("%s",g[i]);
dfs(0,0);
cout<<ans.size()<<endl;
for(auto& x:ans)
cout<<x.first+1<<' '<<x.second+1<<endl;
return 0;
}
2,排列型枚举:用数组st[N]去重
题1 94. 递归实现排列型枚举
#include<iostream>
using namespace std;
const int N=11;
int n;
int path[N];
bool st[N];
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;++i) printf("%d ",path[i]);
printf("\n");
}
for(int i=0;i<n;++i)
if(!st[i])
{
st[i]=true;
path[u]=i+1;
dfs(u+1);
//path[u]=0;
st[i]=false;
}
}
int main()
{
scanf("%d",&n);
dfs(0);
return 0;
}
题2 1209. 带分数
#include<iostream>
using namespace std;
const int N=10;
int n,ans;
int num[N];
bool st[N];
int calc(int l,int r)
{
int res=0;
for(int i=l;i<=r;++i)
res=res*10+num[i];
return res;
}
void dfs(int u)
{
if(u==9)
{
for(int i=0;i<7;++i)
for(int j=i+1;j<8;++j)
{
int a=calc(0,i),b=calc(i+1,j),c=calc(j+1,8);
if(a*c+b==c*n) ++ans;
}
}
for(int i=1;i<=9;++i)
if(!st[i])
{
num[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
int main()
{
scanf("%d",&n);
dfs(0);
printf("%d",ans);
return 0;
}
递推
题1 1208. 翻硬币
#include<iostream>
#include<string>
using namespace std;
void turn(char& x)
{
x=x=='*'?'o':'*';
}
int main()
{
string a,b;
cin>>a>>b;
int cnt=0;
for(int i=0;i<a.size()-1;++i)
{
if(a[i]==b[i]) continue;
turn(a[i]),turn(a[i+1]),++cnt;
}
printf("%d",cnt);
return 0;
}
题2 95. 费解的开关
#include<iostream>
#include<cstring>
using namespace std;
const int N=6;
char g[N][N],bg[N][N];
int dx[]={-1,0,1,0,0},dy[]={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||a<0||b>=5) continue;
g[a][b]^=1;
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
for(int i=0;i<5;++i)
scanf("%s",bg[i]);
int res=10;
for(int op=0;op<32;++op)
{
memcpy(g,bg,sizeof bg);
int cnt=0;
for(int j=0;j<5;++j)
if(op>>j&1)
{
turn(0,j);
++cnt;
}
for(int i=0;i<4;++i)
for(int j=0;j<5;++j)
if(g[i][j]=='0')
{
turn(i+1,j);
++cnt;
}
bool f=true;
for(int j=0;j<5;++j)
if(g[4][j]=='0') f=false;
if(f) res=min(res,cnt);
}
if(res>6) res=-1;
printf("%d\n",res);
}
return 0;
}