【ACM】—蓝桥杯大一暑期集训Day3

🚀欢迎来到本文🚀
🍉个人简介：陈童学哦，目前学习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 <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;
	else
		cout<<"NO"<<endl;
}

总结

Day3的题主要考察搜索，这类算法通常较难，需多加理解递归思想。
算法：dfs、bfs、回溯、递归、递推
感悟：dfs、bfs等算法的使用还需多加做题才能深入理解
总结：每个算法都有其巧妙处，搜索算法更是巧妙