0x02递推与递归

(1)递归

AcWing 92. 递归实现指数型枚举 

选or不选

#include<bits/stdc++.h> using namespace std; int n; vector<int>a; void dfs(int x){ if(x==n+1){ for(int i=0;i<a.size();i++){ printf("%d ",a[i]); } printf("\n"); return; } dfs(x+1); a.push_back(x); dfs(x+1); a.pop_back(); } int main(){ scanf("%d",&n); dfs(1); return 0; }

AcWing 93. 递归实现组合型枚举 

加减枝，关于到不了和超了

#include<bits/stdc++.h> using namespace std; int n,m; vector<int>a; void dfs(int x){ if(a.size()>m||(n-x+1+a.size())<m)return ;//****************** if(x==n+1){ for(int i=0;i<a.size();i++){ printf("%d ",a[i]); } printf("\n"); return; } a.push_back(x); dfs(x+1); a.pop_back(); dfs(x+1); } int main(){ scanf("%d%d",&n,&m); dfs(1); return 0; }

AcWing 94. 递归实现排列型枚举 

随机选，记录已选的

#include<bits/stdc++.h> using namespace std; int n,vis[10]; vector<int>a; void dfs(int x){ if(x==n+1){ for(int i=0;i<a.size();i++){ printf("%d ",a[i]); } printf("\n"); return; } for(int i=1;i<=n;i++){ if(!vis[i]){ vis[i]=1; a.push_back(i); dfs(x+1); a.pop_back(); vis[i]=0; } } } int main(){ scanf("%d",&n); dfs(1); return 0; }

AcWing 95. 费解的开关 

枚举第一行方案，剩下的行数模拟下去，判断是否可行，更新答案

#include<bits/stdc++.h> using namespace std; int n=5,T,a[10][10],tmp[10][10]; char s[10][10]; void cz(int i,int j){ tmp[i][j]^=1;tmp[i-1][j]^=1;tmp[i+1][j]^=1;tmp[i][j-1]^=1;tmp[i][j+1]^=1; } bool check(){ for(int i=1;i<=n;i++)if(!tmp[n][i])return 0; return 1; } int main(){ scanf("%d",&T); while(T--){ int flag=1,ans=1e9; for(int i=1;i<=n;i++){ scanf("%s",s[i]+1); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=s[i][j]-'0'; } } for(int s=0;s<(1<<n);s++){ int cnt=0; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)tmp[i][j]=a[i][j]; for(int i=1;i<=n;i++){ if(s>>i-1&1){ cz(1,i); cnt++; } } for(int i=2;i<=n;i++){ for(int j=1;j<=n;j++){ if(tmp[i-1][j]==0){ cz(i,j); cnt++; } } } if(cnt<=6&&check()){ flag=0; ans=cnt; } } if(flag)printf("-1\n"); else printf("%d\n",ans); } return 0; } (2)递推

AcWing 96. 奇怪的汉诺塔 

三塔模式d[n]=2*d[n-1]+1，表示把n-1个移到B柱，把最大的移到C柱，最后把n-1个移到C柱

四塔f[n]=min{2*f[i]+d[n-i]} 其中，表示把i个移到B柱，把n-i个移到D柱，再把剩下的i个再移到D柱

#include<bits/stdc++.h> using namespace std; long long f[70][70],n=4,m=12; void init(){ for(int i=3;i<=n;i++)f[i][1]=1; for(int i=2;i<=m;i++){ f[3][i]=f[3][i-1]*2+1; } } int main(){ init(); for(int i=4;i<=n;i++){ for(int j=2;j<=m;j++){ f[i][j]=1e9; for(int k=1;k<j;k++){ f[i][j]=min(f[i][k]*2+f[i-1][j-k],f[i][j]); } } } for(int i=1;i<=m;i++)printf("%d\n",f[n][i]); return 0; } (3)分治

AcWing 97. 约数之和 

求等比数列

c为奇数时

sum（p,c)=p+p^2+...+p^c

=1+p+p^2+...+p^(c-1)/2+p^(c+1)/2+...+p^c

=sum(p,(c-1)/2)*(1+p^(c+1)/2)

c为偶数

sum（p,c)=sum(p,c/2)*(1+p^(c/2-1))+p^c

#include<bits/stdc++.h> using namespace std; long long a,b,ans=1; const long long mod=9901; long long ksm(long long a,long long b){ long long res=1; while(b){ if(b&1)res=res*a%mod; b>>=1;a=a*a%mod; } return res; } long long calc(long long p,long long n){ if(n==0)return 1;if(n==1)return (p+1)%9901; if(n&1)return calc(p,(n-1)/2)*(1+ksm(p,(n+1)/2))%mod; else return (calc(p,n-1)+ksm(p,n))%mod; } int main(){ scanf("%lld%lld",&a,&b); if(a==0){printf("0");return 0;} for(long long i=2;i*i<a;i++){ long long cnt=0; while(a%i==0){a/=i;cnt++;} ans=(ans*calc(i,cnt*b))%mod; } if(a>1)ans=(ans*calc(a,b))%mod; printf("%lld",ans); return 0; } (4)分形

AcWing 98. 分形之城 

四份四份分形，记录左上角坐标及尺寸

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll T,n,a,b; pair<ll,ll> calc(ll n,ll p){ if(n==0)return {0,0}; ll len=1ll<<(n-1),cnt=1ll<<(2*n-2); pair<ll,ll>q=calc(n-1,p%cnt); ll x=q.first,y=q.second; long long m=p/cnt; if(m==0)return {-y-len,-x+len}; if(m==1)return {x+len,y+len}; if(m==2)return {x+len,y-len}; return {y-len,x-len}; } double js(){ pair<ll,ll>x=calc(n,a),y=calc(n,b); return sqrt(((double)(x.first-y.first)*(double)(x.first-y.first)+(double)(y.second-x.second)*(double)(y.second-x.second)))*5; } int main(){ scanf("%lld",&T); while(T--){ scanf("%lld%lld%lld",&n,&a,&b); a--,b--; printf("%.0lf\n",js()); } return 0; }

AcWing 118. 分形 

这个不用说

#include<bits/stdc++.h> using namespace std; int n,mp[2505][2505]; void init(){ mp[1][1]=1; int len=1; for(int s=1;s<=7;s++){ for(int i=1;i<=len;i++){ for(int j=1;j<=len;j++){ mp[i+len*2][j]=mp[i][j]; mp[i+len*2][j+len*2]=mp[i][j]; mp[i][j+len*2]=mp[i][j]; mp[i+len][j+len]=mp[i][j]; } } len*=3; } } int main(){ init(); while(scanf("%d",&n)){ if(n==-1)return 0; else{ n--; for(int i=1;i<=pow(3,n);i++){ for(int j=1;j<=pow(3,n);j++){ printf("%c",(mp[i][j])?'X':' '); } printf("\n"); } printf("-\n"); } } return 0; }