当前位置：首页 > article >正文

SMU2025-4

article 2025/2/24 8:16:42

一、训练内容

本周的训练主要就是蓝桥杯和天梯赛的训练赛

蓝桥杯训练1、蓝桥杯训练2、蓝桥杯训练3

二、补题

1、蓝桥杯训练1-A

题目大意：题目要求在一个涉密单位的票据管理系统中，找出两张特殊的票据：一张是断号的票据（即缺失的票据），另一张是重号的票据（即重复的票据）。

思路：拍一下序，找相邻两项相等的和相邻两项差值大于1的数

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define sc scanf
#define pr printf
const int N = 1e5+7;
const int mod = 1e9+7;
int a[N];
int main()
{
	int T=1;
	//sc("%d", &T);
	while(T--)
	{
		int n;
		cin>>n;
		int ans1, ans2, cnt;
		while(cin>>a[cnt]) cnt++;
		sort(a,a+cnt);
		for(int i=0;i<cnt;i++)
		{
			if(a[i]==a[i+1]) ans2=a[i];
			if(a[i+1]-a[i]>1) ans1=a[i]+1;
		}
		cout<<ans1<<" "<<ans2<<'\n';
	}
	return 0;
}

2、蓝桥杯训练1-F

思路：化简之后得知实际是求gcd(a,b,c)，根据定义可得所找的就是三个数中最大的公共因数，因此我们令 v[i] 数组为有哪些数包含因数 i，在处理后我们只需要从大到小遍历所有因数，找到首个 v[i] 的长度大于 3 的数即为答案（意义为在给出的数组中有大于等于 3 个数的其中一个因数为 i），其中包含的三个数的具体数值即为我们要找的答案，题目中要求字典序最小，故在此之前对数组进行排序即可

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define sc scanf
#define pr printf
const int N = 1e5+7;
const int mod = 1e9+7;
vector<int> v[N];
int a[N];
int main()
{
	int T=1;
	//sc("%d", &T);
	while(T--)
	{
		int n;
		cin >> n;
		for(int i = 1;i<=n;i++){
			cin >> a[i];
		}
		sort(a+1,a+1+n);
		for(int i = 1;i<=n;i++){
			for(int j = 1;j * j <= a[i];j++){
				if(a[i] % j == 0){
					if(v[j].size() < 3){
						v[j].push_back(a[i]);
					}
					
					if(j * j < a[i] && v[a[i]/j].size() < 3){
						v[a[i]/j].push_back(a[i]);
					}
				}
			}
		}
		for(int i = 100000;i>=1;i--){
			if(v[i].size() == 3){
				cout << v[i][0] << " " << v[i][1] << " " << v[i][2] << endl;
				break;
			}
		}
	}
	return 0;
}

3、蓝桥杯训练2-B

题目大意：这是一道组合数学问题，要求在一个 N×N 的点阵中，计算可以组成正方形的四个点的组合数。题目要求输出的结果对 109+7 取模。

思路：首先我们看到图的时候，可以发现，正方形可以分为很多板块，和不同的形状，那么我们用乘法原理和加法原理求解即可。需要注意的是，我们需要开long long 不然只能得30分。别问我怎么知道的，因为我就只得了30分。。。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define sc scanf
#define pr printf
const int N = 1e5+7;
const int mod = 1e9+7;
int main()
{
	int T=1;
	//sc("%d", &T);
	while(T--)
	{
		LL n;
		cin>>n;
		LL ans=0;
		for(int i=1;i<n;i++)
		{
			LL tmp=(n-i)*(n-i)*i;
			ans=(ans+tmp)%mod;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

4、蓝桥杯训练2-F

题目大意：小明在数轴上进行立定跳远，需要依次跳到 n 个检查点 a1,a2,…,an。他可以额外增加 m 个检查点来帮助自己完成跳跃。小明的单次跳跃距离为 L，并且可以使用一次“爆发技能”，使得某次跳跃的距离达到 2L。

思路：首先我们观察到添加检查点我们的跳的最远距离必定减少具有单调性，题目还说可以使用一次技能使用时可以在该次跳跃时的最远距离变为 2L，使用技能时相当于跳了两次，可以想到把这个技能转换成多加一个检查点

代码如下：

#include<bits/stdc++.h>
using namespace std;
//typedef long long LL;
#define int long long
#define sc scanf
#define pr printf
const int N = 1e5+7;
const int mod = 1e9+7;
int a[N];
int n,m;
int check(int x)
{
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]-a[i-1]>=x)
			if((a[i]-a[i-1])%x==0)
				ans+=(a[i]-a[i-1])/x-1;
		else
			ans+=(a[i]-a[i-1])/x;
	}
	if(ans<=m+1) return 1;
	return 0;
}
signed main()
{
	int T=1;
	//sc("%d", &T);
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		int l=0,r=1e8;
		while(l<r)
		{
			int mid=l+r>>1;
			if(check(mid))
				r=mid;
			else
				l=mid+1;
		}
		cout<<l;

	}
	return 0;
}

5、蓝桥杯训练2-G

题目大意：

小蓝有一个长度为 n 的数组 A=(a1,a2,…,an)。对于数组的任意子数组，定义其“近似 GCD”为 g，满足以下条件之一：

子数组的最大公约数本身就是 g。
通过修改子数组中的最多一个元素为任意值，使得子数组的最大公约数变为 g。

思路：从头到尾开始遍历，一个i指针，一个j指针，一个last指针

通过比较i和last查看是否可以对last进行移动，并且关乎者j的移动

代码如下：

#include<bits/stdc++.h>
using namespace std;
//typedef long long LL;
#define int long long
#define sc scanf
#define pr printf
const int N = 1e5+7;
const int mod = 1e9+7;
int n, g;
int a[N];
int cnt;
signed main()
{
	int T=1;
	//sc("%d", &T);
	while(T--)
	{
		cin >> n >> g;
		for(int i=1;i<=n;i++){
			cin >> a[i];
		}
		int j=1;
		int last=-1;
		for(int i=1;i<=n;i++){
			while(j<=n&&(a[j]%g==0||last<i)){
				if(a[j]%g!=0){
					last=j;
				}
				j++;
			}
			if(j>i+1){
				cnt+=j-i-1;
			}
		}
		cout << cnt;
	}
	return 0;
}

6、蓝桥杯训练3-D

题目大意：这是一道关于判断数字性质的算法问题，目标是通过删除数组中某些数字，使得剩下的数字都满足特定的“诗意”条件。具体来说，一个数字如果能表示为若干个（至少两个）连续正整数的和，则称其为“蕴含诗意”的数字。

思路：通过打表验证总结规律有：如果一个数是奇数就一定有诗意，是奇数 * 2的次方的偶数一定有诗意，所有2的幂次方都没有诗意（1也没有诗意，题目要求至少两个连续的数）。

代码如下：

（待补）

7、蓝桥杯训练3-E

题目大意：

小明正在玩一款解谜游戏，游戏中有 24 根塑料棒，分别由 4 根黄色（Y）、8 根红色（R）和 12 根绿色（G）组成。这些塑料棒初始时排成三圈：

外圈：12 根塑料棒。
中圈：8 根塑料棒。
内圈：4 根塑料棒。

小明可以进行以下三种操作：

顺时针旋转：将三圈塑料棒都顺时针旋转一个单位。
逆时针旋转：将三圈塑料棒都逆时针旋转一个单位。
轮换：将三圈 0 点位置的塑料棒进行轮换（外圈 0 点 → 内圈 0 点，内圈 0 点 → 中圈 0 点，中圈 0 点 → 外圈 0 点）。

小明的目标是通过上述操作，将所有绿色棒移到外圈，所有红色棒移到中圈，所有黄色棒移到内圈。问的是，小明可不可以完成这个目标

思路：它有三种移动方式，其中第一种和第二种是类似的，是不将颜色块所属的圈子更换的，就只是同时顺时针和逆时针，同时我们可以发现，外圈有12个，中圈8个，内圈4个。也就是说，同时顺时针和逆时针旋转的时候，内圈的颜色块是固定的对应中圈的两个颜色块和外圈的三个颜色块。也就是说，在不更改颜色块的圈子的操作中，内1个、中2个和外3个是固定搭配的，无论怎么操作顺逆时针，都是固定的。这六个颜色块：外1、2、3、中1、2、内1无法和其他的颜色块交换。

代码如下：

#include<bits/stdc++.h>
using namespace std;
//typedef long long LL;
#define int long long
#define sc scanf
#define pr printf
const int N = 1e5+7;
const int mod = 1e9+7;
signed main()
{
	int T=1;
	//sc("%d", &T);
	while(T--)
	{
		int n;
		cin>>n;
		while(n--)
		{
			bool flag=true;
			string in_color,mid_color,out_color;
			cin>>out_color>>mid_color>>in_color;
			for(int i=0;i<4;i++)
			{
				map<char,int>color;
				color[in_color[i]]++;
				color[mid_color[i]]++;
				color[mid_color[i+4]]++;
				color[out_color[i]]++;
				color[out_color[i+4]]++;
				color[out_color[i+8]]++;
				if(color['Y']!=1||color['R']!=2||color['G']!=3)
				{
					flag=false;
					break;
				}
			}
			if(flag)
				cout<<"YES"<<endl;
			else
				cout<<"NO"<<endl;
		}
	}
	return 0;
}

三、总结

在这一周的集训中，我完成了最后阶段的冲刺，通过高强度的训练和模拟赛，对所学知识进行了的梳理和巩固。在算法学习上，对动态规划、二分等核心知识点有了更深入的理解，尤其是在复杂问题的建模和优化上有了新的突破。通过大量实战题目，我不仅提升了编程能力，还学会了如何在压力下快速调整思路，合理分配时间和精力。虽然集训即将结束，但学习和进步的脚步不会停止。这一周的经历让我更加清晰地认识到自己的潜力和需要改进的地方。未来，我会继续钻研算法，提升能力，将集训中学到的知识应用到实际问题中，努力在接下来的比赛中取得更好的成绩。

查看全文

http://www.kler.cn/a/558657.html