Day51 递归实现组合型枚举(递归写法（二进制m个1的写法），非递归写法)递归转非递归写法 第四届蓝桥 带分数

递归实现组合型枚举 普通递归剪枝 写法

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } ll T,N; int n,m; bool vis[100]; int ans[100]; void dfs(int cnt){ if(cnt>0&&n-ans[cnt-1]+1<m-cnt)return; if(cnt>=m){ for(int i=0;i<m;i++)cout<<ans[i]<<" "; cout<<endl; return; } for(int i=1;i<=n;i++){ if(cnt>0&&ans[cnt-1]>=i){ continue; } if(!vis[i]){ vis[i]=1; ans[cnt]=i; dfs(cnt+1); vis[i]=0; } } } void solve(){ cin>>n>>m; dfs(0); // ans.push_back(1); } int main(){ // std::ios::sync_with_stdio(0); // std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

另一种递归写法

是直接用状态压缩 抽离出n位二进制中m个1的所有数 很精妙，速度比起上面那个快一点

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } ll T,N; int n,m; void dfs(int u,int sum,int state){ if(sum+n-u<m)return; if(sum==m){ for(int i=0;i<n;i++){ if(state>>i&1){ printf("%d ",i+1); } } puts(""); return; } dfs(u+1,sum+1,state|1<<u); dfs(u+1,sum,state); } void solve(){ scanf("%d%d",&n,&m); dfs(0,0,0); } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

非递归写法

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<stack> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } struct node{ int pos,u,sum,state; }; ll T,N; int n,m; void dfs(int u,int sum,int state){ //0 if(sum+n-u<m)return; if(sum==m){ for(int i=0;i<n;i++){ if(state>>i&1){ printf("%d ",i+1); } } puts(""); return; } dfs(u+1,sum+1,state|1<<u); //1 dfs(u+1,sum,state); //2 } void solve(){ scanf("%d%d",&n,&m); //dfs(0,0,0); stack<node>Stack; Stack.push({0,0,0,0}); while(!Stack.empty()){ auto item=Stack.top(); Stack.pop(); if(item.pos==0){ if(item.sum+n-item.u<m)continue; if(item.sum==m){ for(int i=0;i<n;i++){ if(item.state>>i&1){ printf("%d ",i+1); } } puts(""); continue; } item.pos=1; Stack.push(item); Stack.push({0,item.u+1,item.sum+1,item.state|1<<item.u}); }else if(item.pos==1){ item.pos=2; Stack.push(item); Stack.push({0,item.u+1,item.sum,item.state}); }else { continue; } } } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

非递归跑的慢了一点 可能是stack的stl慢了

递归转成非递归是有技巧的

新建一个结构体

里面除了dfs的参数外，加一个pos

把dfs分成几个部分，就像我在代码里标注的

然后再用栈模拟一遍递归过程

这样就可以实现非递归了

---

带分数 由于公式 $n=a+\frac{b}{c}\mapsto c\cdot n-c\cdot a=b$ 枚举唯一的a和c,即可求出b

所以我们要唯一地枚举a和c 方法是一样的

见代码

然后再check一下就可以了

这种程度的dfs还有点意思

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } #define N 10 ll T; bool st[N],backup[N]; int n,ans; bool check(int a,int c){ ll b=(ll)(n-a)*c; if(!a||!b||!c)return 0; memcpy(backup,st,sizeof(backup)); while(b){ if(b==0||backup[b])return 0; backup[b]=1; b/=10; } for(int i=1;i<=9;i++){ if(!backup[i])return 0; } return 1; } void dfs_c(int a,int c){ if(check(a,c)){ ans++; } for(int i=1;i<=9;i++){ if(!st[i]){ st[i]=1; dfs_c(a,c*10+i); st[i]=0; } } } void dfs_a(int a){ if(a>=n)return; if(a){ // cout<<a<<endl; dfs_c(a,0); } for(int i=1;i<=9;i++){ if(!st[i]){ st[i]=1; dfs_a(a*10+i); st[i]=0; } } } void solve(){ //int n; cin>>n; dfs_a(0); cout<<ans; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }