本次比赛是我打a以来最接近AK的一次，打的也非常顺，看了下大部分是构造以及数学题，我还是喜欢这两类。

比赛链接牛客2025秋季算法编程训练联赛5-基础组

A-模板

题意

给出有且仅由大写字母构成，长度为 $n$ 的字符串s1 以及长度为 $m$ 的字符串s2，求最小操作可以将其中一个字符串转化为另一个，操作有：

  • 将其中任意一个字母替换为另一个
  • 把最后一个字母删除
  • 在尾部添加一个字母

其中，$1 \leq n,m \leq 10^5$

思路

既然可以修改任意一个，或者修改（删除添加）末尾，那么直接统计在 $i:=0 \sim \min(n,m)$ 中s1[i]!=s2[i] 的个数（超过min(n,m)的直接删了，里面的修改），最后加上n和m的差输出即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m; cin >> n >> m;
	string s1,s2; cin >> s1 >> s2;
	int cnt=0;
	int len=min(n, m);
	for(int i=0; i<len; i++)if(s1[i]!=s2[i])cnt++;
	int ext=abs(n-m);
	cout << cnt+ext << endl;


	return 0;
}

B-I题是个签到题

题意

给出$9 \le n \le 13 \ ,\ 100 \le m \le 1000$ 分别代表比赛的总题数和比赛的人数，定义签到题：

  • 通过人数大于等于全场人数的 $80%$
  • 或者通过人数是所有题目前三多的题（也就是最多有两个题目通过人数严格比它多）

求I题是不是签到题

思路

直接模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

/*
I->8
*/

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m; cin >> n >> m;
	vector<int> a(n);
	for(auto &x:a)cin >> x;
	int ti=a[8];
	bool f1=((double)ti>=(double)m*0.8);
	int cnt=0;
	for(int i=0; i<n; i++)if(a[i]>ti)cnt++;
	bool f2=(cnt<=2);
	if(f1 || f2)cout << "Yes\n"; 
	else cout << "No\n";


	


	return 0;
}

C-牛牛战队的秀场

题意

给出一个整数半径为 $1 \le r \le 10^6$ 的圆，以及里面的内接 $3 \le n \le 1000$ 边形，两个人分别在n边形的第 $i,j$ 号顶点，求两人经过多边形的边的最短距离。

思路

由于两点的位置是在一个环上，那么最短经过的边数应该是 $\min(|i-j|,n-|i-j|)$ 也就是正向和反向走的最小值，这个值乘上每条边的长度就是答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	double n,r; 
	cin >> n >> r;
	int i, j; cin >> i >> j;
	double l0=2.0*r*sin(PI/n);
	int st=abs(i-j);
	int stp=(int)n-st;
	int minn=min(st,stp);
	double ans=(double)minn*l0;
	printf("%.10lf",ans);


	return 0;
}

D-Enjoy the game

看到博弈，被南京站的博弈吓怕了，蒟蒻以为很难，所以先跳过，写完F回来猜猜法猜出了答案，但是没敢交，后来严格证明发现是对的，可惜😭

题意

Bob和Alice进行一场比赛，初始有 $n$ 张牌，Bob和Alice轮流取牌，Bob先取，先取的牌数范围是 $1 \sim n-1$ ，接下来的每一步双方至少要取一张牌，且不能超过上一步对方所取得牌数，如果最后一张牌被Bob取走，Bob获胜，否则Alice获胜。双方都很聪明，输出谁会获胜。

思路

我们先打表一下：

$n$ Who will win
2 Alice
3 Bob
4 Alice
5 Bob
6 Bob
7 Bob
8 Alice

依此来看，如果n是奇数，Bob和Alice依次拿一张牌，Bob必胜，下面讨论n是偶数的情况：

如果Alice能赢，那么回合数一定是偶数；不想让Alice赢的话，每次拿出的牌数必须满足 $(n-x)/x$ 是偶数，并且此时的 $x<n/2$ 。

那么考虑 $n=2^k$ 时， 每次拿去 $x=n/2-1$ 后必定会剩下 $2^p+1$ 张牌，如果此时Alice拿去1张，又会递归到 $n=2^k$ 的情况。

注意到 $n={2,4,8}$ 时推断出ALice必胜，那么不难证明，$n=2^k$ 时Alice必胜。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define ll long long 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n; cin >> n;
	if(n&1)
	{
		cout << "Bob\n";
		return 0;
	}
	else
	{   // 这里直接用二进制位运算来判断
		if((n&(n-1LL))==0LL)cout << "Alice\n";
		else cout << "Bob\n";
	}

	return 0;
}

E-Hash

题意

对于这样的hash函数

1
2
3
4
5
6
7
8
9
10
11
const int LEN = 6;
int mod;
int Hash(char str[])
{
    int res = 0;
    for (int i = 0; i < LEN; i++)
    {
        res = (res * 26 + str[i] - 'a') % mod; 
    }
    return res;
}

给出一个长度位6且仅有小写字母构成的字符串s，和模数mod，找到字典序最小且大于s的一个长度为6的字符串s’，使得其俩的hash值相等。

思路

这题一看就是26进制的模数，利用模数的周期性就可以AC。具体来看如何利用。

我们这里考虑原字符串s的26进制数 $h0$（先不 $\mathbf{mod}$ ），我们知道

那么我们只需要将 $h0$ 加上一个模数，就可以将这个hash转到下一个周期，然后从这个新的hash中用26进制转化为字符串s’。

蒟蒻这里先wa了三发，给大家看看我的神奇构造

先修改最后一位S[5]，如果S[5]+mod还在25这个范围内，说明刚好下一个周期，直接输出修改后的即可

如果不能修改，那么构造最小修改：

  • 需要构造的 $h’-h_0=0$
  • 遍历 $i:=4~0$ 修改S[i]，直接构造S[i]++,并同时修改S[5]补齐模数
  • 此时S[5]应该等于$S[5]-w(5-i)$，权 $w(i)=26^{i} \mod m$

这个构造使得

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const ll maxn=308915775; // 26^6-1

void sol(string s,int mod)
{
	ll h0=0;
	for(int i=0; i<6; i++)h0=(h0*26+s[i]-'a');
	ll h=h0+mod;
	if(h>maxn) // 这里先判断是否超出范围（全是z的时候）
	{
		cout << "-1\n";
		return;
	}
	string ans(6,'a');
	for(int i=5; i>=0; i--)
	{
		ans[i]='a'+(h%26);
		h/=26;
	}
	cout << ans << endl;
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int mod; string s;
	while(cin >> s >> mod)
		sol(s,mod);


	return 0;
}

F-牛牛战队的比赛地

题意

二维平面上有 $n$ 和点 $(x_i,y_i)$ ，在x轴上找到一个点，使得这些点到这个点的最大距离最小。

思路

显然的，找到最大的最小值，要么二分要么三分。

如果二分，我的想法是二分x轴上的点以及以这个点作为圆心画出的圆，最大包裹所有点，但是这样写就会很复杂。

考虑三分，显然存在某个点 $(x_0,0)$ 是该函数的极小值点，写出函数为：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const double eps=1e-9;

int n;
vector<pdd> g;

double f(double x)
{
	double res=-1e9;
	for(auto [xi,yi]:g)
		res=max(res,(x-xi)*(x-xi)+yi*yi);
	return res;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	g.resize(n);
	for(auto &[x,y]:g)cin >> x >> y;
	double l=-1e4, r=1e4;
	for(int i=0; i<100; i++)
	{
		double m1=l+(r-l)/3.0;
		double m2=r-(r-l)/3.0;
		if(f(m1)>f(m2))l=m1;
		else r=m2;
	}
	double ans=sqrt(f((l+r)/2.0));
	printf("%.10lf",ans);
	

	return 0;
}