前言
因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。
A - Subtraction Game
来源：CodeForces - 1844A. Subtraction Game
题意： 两个人先后从一堆石子中取a或b个石子，最先无法取得石子的人就输了，输入给出a和b，要求输出的n使得先手开局必输。
解题思路
这道题其实是雷声大雨点小啦，就是谁先把石子取完让另一个人无法再取的话就赢了，那么只要后手的那个人取石子的时候能够全部取完让先手的无法取得即可求解，题目所给样例可能有点迷惑性哈。
示例代码
#include <bits/stdc++.h> using namespace std; int main() { int t,a,b; cin>>t; while (t--) { cin>>a>>b; cout<<a+b<<endl; } return 0; }
B - 全排列
解题思路
本题用dfs深搜回溯再剪枝把所有情况罗列出来即可
示例代码
#include<bits/stdc++.h> 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<bits/stdc++.h> 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<a[i]) return false; } return true; } void dfs(int t,int s){ if(t>m){ if(judge(s)){ if(s<minn){ 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<<minn<<' '; for(int i=1;i<=minn;i++) cout<<co[i]<<' '; }
D - New Year Transportation
来源：CodeForces - 500A. New Year Transportation
解题思路
这题用for循环递推一下，理清思路即可。
示例代码
#include<iostream> using namespace std; int main() { int a[30005]; int n,t,i; cin>>n>>t; for(i=1;i<n;i++) cin>>a[i]; for(i=1;i<t;i+=a[i]); //递推 if(i==t) cout<<"YES"<<endl; else cout<<"NO"<<endl; }
总结
Day3的题主要考察搜索，这类算法通常较难，需多加理解递归思想。
算法：dfs、bfs、回溯、递归、递推
感悟：dfs、bfs等算法的使用还需多加做题才能深入理解
总结：每个算法都有其巧妙处，搜索算法更是巧妙
