欢迎来到本文 个人简介：陈童学哦，目前学习C/C++、算法、Python、Java等方向，一个正在慢慢前行的普通人。 系列专栏：陈童学的日记 其他专栏：C++STL，感兴趣的小伙伴可以看看。 希望各位→点赞 + 收藏⭐️ + 留言 ⛱️学习应使你快乐！望与诸君共勉！♂️
Day3集训
前言A - Subtraction Game解题思路示例代码
B - 全排列解题思路示例代码
C - 健康的奶牛解题思路示例代码
D - New Year Transportation解题思路示例代码
总结
前言
因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。
A - Subtraction Game
来源：CodeForces - 1844A. Subtraction Game 题意： 两个人先后从一堆石子中取a或b个石子，最先无法取得石子的人就输了，输入给出a和b，要求输出的n使得先手开局必输。
解题思路
这道题其实是雷声大雨点小啦，就是谁先把石子取完让另一个人无法再取的话就赢了，那么只要后手的那个人取石子的时候能够全部取完让先手的无法取得即可求解，题目所给样例可能有点迷惑性哈。
示例代码
#include
using namespace std;
int main() {
int t,a,b;
cin>>t;
while (t--) {
cin>>a>>b;
cout< } return 0; } B - 全排列 来源：洛谷P1706 全排列问题 解题思路 本题用dfs深搜回溯再剪枝把所有情况罗列出来即可 示例代码 #include using namespace std; int n,g[105],s[105]; void print(){ for(int i=1;i<=n;i++) printf("%5d",s[i]); printf("\n"); } void dfs(int x){ if(x==n){ print(); return; } for(int i=1;i<=n;i++){ if(!g[i]){ g[i]=1; s[x+1]=i; dfs(x+1); g[i]=0; } } } int main(){ cin>>n; dfs(0); } C - 健康的奶牛 来源：洛谷P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins 解题思路 这道题用dfs深搜不需要剪枝，本蒟蒻没有做出来，看了某位神犇的哇 示例代码 #include using namespace std; int co[1001]; int a[1001]; int b[1001][1001]; int c[1001]; int n,m,minn=0x3f3f3f3f; bool judge(int x){ for(int i=1;i<=n;i++){ int sum=0; for(int j=1;j<=x;j++) sum+=b[c[j]][i]; if(sum return false; } return true; } void dfs(int t,int s){ if(t>m){ if(judge(s)){ if(s minn=s; for(int i=1;i<=minn;i++) co[i]=c[i]; } } return; } c[s+1]=t; dfs(t+1,s+1); c[s+1]=0; dfs(t+1,s); } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cin>>m; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++) cin>>b[i][j]; } dfs(1,0); cout< for(int i=1;i<=minn;i++) cout< } D - New Year Transportation 来源：CodeForces - 500A. New Year Transportation 解题思路 这题用for循环递推一下，理清思路即可。 示例代码 #include using namespace std; int main() { int a[30005]; int n,t,i; cin>>n>>t; for(i=1;i cin>>a[i]; for(i=1;i if(i==t) cout<<"YES"< else cout<<"NO"< } 总结 Day3的题主要考察搜索，这类算法通常较难，需多加理解递归思想。 算法：dfs、bfs、回溯、递归、递推 感悟：dfs、bfs等算法的使用还需多加做题才能深入理解 总结：每个算法都有其巧妙处，搜索算法更是巧妙 好文阅读
您阅读本篇文章共花了：
发表评论