Acwing 蓝桥杯 第一章 递归与递推

我上周在干什么，感觉我上周啥也没训，本来两天一次的vp也没v

很寄啊，再这样下去真不行了

先总结一下如何爆搜：

先去确定好枚举的对象

枚举的对象很重要！！这直接影响了复杂度

然后就是去想递归树就好了

一、确定状态：

状态分为全局变量和局部变量

考虑状态时去考虑三样东西：

1. 阶段（即深度），阶段作为出口

2. 影响决策的因素（全局or局部）

3. 要维护的答案

二、枚举决策+加限定条件

三、确定出口（根据阶段）

那么我们怎么去考虑复杂度：考虑每一层树的结点个数*每个结点的复杂度

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

思路：

一、先去确定状态：

1. 阶段就是深度，即选了几个数了

2. 决策就是选与不选，没东西影响决策

3. 开个全局数组记录答案即可

因此状态就是dfs(x)

二、枚举决策：选or不选

三、确定出口：深度>n

Code：

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;
vector<int> v;
int n;
int vis[mxn];
void print(){for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
}
void dfs(int u){if(u>n){print();return;}v.push_back(u);dfs(u+1);v.pop_back();dfs(u+1);
}
void solve(){cin>>n;dfs(1);cout<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

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

一、设状态：

1. 阶段：深度，即选了几个数

2. 影响决策的因素：只能选没选过的数：开个全局vis

3. 记录答案：开个全局数组记录答案

二、枚举决策：

1~n，然后不选vis[i]=1的就行

三、出口：

深度>n

Code：

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;
vector<int> v;
int n;
int vis[mxn];
void print(){for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
}
void dfs(int u){if(u>n){print();return;}for(int i=1;i<=n;i++){if(!vis[i]){v.push_back(i);vis[i]=1;dfs(u+1);vis[i]=0;v.pop_back();}}
}
void solve(){cin>>n;dfs(1);
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

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

一、确定状态：

1. 阶段：即深度，选不超过m个数

2. 影响决策的因素：每次选比上次选的数大的，因此要记录上次选的数

3. 记录结果：开个全局数组就行了

因此状态就是dfs(u,last)，第二维是上次选的数

二、枚举决策：

从last+1开始枚举即可，不用开vis数组，不会重复

三、出口：

选了>m个数

Code：

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;int n,m,len=0;
int vis[mxn],a[mxn];
void print(){for(int i=1;i<=len;i++) cout<<a[i]<<" \n"[i==len];
}
void dfs(int u,int last){if(u>m){print();return;}for(int i=last+1;i<=n;i++){if(!vis[i]){vis[i]=1;a[++len]=i;dfs(u+1,i);len--;vis[i]=0;}}
}
void solve(){cin>>n>>m;dfs(1,0);
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

AcWing 1209. 带分数 - AcWing

枚举对象：先去枚举全排列，然后枚举两个指针隔起来，验证正确性就好了，不需要dfs爆搜

有个细节就是：不要用substr，写个函数更清晰

Code：

#include <bits/stdc++.h>
//#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;int n;
string s="123456789";
bool check(int x1,int x2,int x3){if(x2%x3==0&&x1+x2/x3==n) return true;return false;
}
int trans(int l,int r){int res=0;for(int i=l;i<=r;i++){res=res*10+(s[i]-'0');}return res;
}
void solve(){int ans=0;cin>>n;do{for(int i=0;i<9;i++){for(int j=i+1;j<9;j++){int a1=trans(0,i);int a2=trans(i+1,j);int a3=trans(j+1,8);if(a1==0||a2==0||a3==0) continue;if(check(a1,a2,a3)) ans++;}}}while(next_permutation(s.begin(),s.end()));cout<<ans<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

AcWing 1208. 翻硬币 - AcWing

思路：

这是典中典，第一个是确定的，因此只需递推过去就好了

Code：

#include <bits/stdc++.h>
#define int long long
const int mxn=3e6+10;
const int mxe=2e5+10;
using namespace std;string s,t;
void solve(){cin>>s>>t;int cnt=0;for(int i=0;i<s.size();i++){if(s[i]!=t[i]){cnt++;if(s[i]=='*') s[i]='o';else s[i]='*';if(s[i+1]=='o') s[i+1]='*';else s[i+1]='o';}}cout<<cnt<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}