【ACM】—蓝桥杯大一暑期集训Day3-Toy模板网

这篇具有很好参考价值的文章主要介绍了【ACM】—蓝桥杯大一暑期集训Day3。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🚀欢迎来到本文🚀
🍉个人简介：陈童学哦，目前学习C/C++、算法、Python、Java等方向，一个正在慢慢前行的普通人。
🏀系列专栏：陈童学的日记
💡其他专栏：C++STL，感兴趣的小伙伴可以看看。
🎁希望各位→点赞👍 + 收藏⭐️ + 留言📝
⛱️学习应使你快乐！望与诸君共勉！🏄‍♂️

【ACM】—蓝桥杯大一暑期集训Day3,ACM,ACM,蓝桥杯,算法,c++,深度优先

前言

因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。

A - Subtraction Game

来源：CodeForces - 1844A. Subtraction Game
【ACM】—蓝桥杯大一暑期集训Day3,ACM,ACM,蓝桥杯,算法,c++,深度优先

题意： 两个人先后从一堆石子中取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 全排列问题
【ACM】—蓝桥杯大一暑期集训Day3,ACM,ACM,蓝桥杯,算法,c++,深度优先

解题思路

本题用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
【ACM】—蓝桥杯大一暑期集训Day3,ACM,ACM,蓝桥杯,算法,c++,深度优先

解题思路

这道题用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

【ACM】—蓝桥杯大一暑期集训Day3,ACM,ACM,蓝桥杯,算法,c++,深度优先

解题思路

这题用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等算法的使用还需多加做题才能深入理解
总结：每个算法都有其巧妙处，搜索算法更是巧妙文章来源地址https://www.toymoban.com/news/detail-569698.html

到了这里，关于【ACM】—蓝桥杯大一暑期集训Day3的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！