🚀歡迎來到本文🚀
🍉個人簡介：陳童學哦，目前學習C/C++、算法、Python、Java等方向，一個正在慢慢前行的普通人。
🏀系列專欄：陳童學的日記
💡其他專欄：C++STL，感興趣的小伙伴可以看看。
🎁希望各位→點贊👍 + 收藏?? + 留言📝 ?
??學習應使你快樂！望與諸君共勉！🏄?♂?

前言

因參加了我校的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 - 全排列

來源：洛谷P1706 全排列問題

解題思路

本題用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;elsecout<<"NO"<<endl;
}

總結

Day3的題主要考察搜索，這類算法通常較難，需多加理解遞歸思想。
算法：dfs、bfs、回溯、遞歸、遞推
感悟：dfs、bfs等算法的使用還需多加做題才能深入理解
總結：每個算法都有其巧妙處，搜索算法更是巧妙