牛客春招刷题训练营 - 2025.5.8 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 墙壁划线

简要题意

有一个 块大小为 的小矩形组成的大矩形，求大矩形两条对角线与小矩形边的交点数。

Solution

首先，主对角线与反对角线上点数一致，我们只考虑主对角线上的点数，最后考虑二者交点是否在边上即可。

对于主对角线， 的答案 。

记 ，有 ，此时 。

当 中存在偶数时，两条对角线交点在小矩形边上，此时要再将答案减去一。

Code

void R()
{
	int a,b,x,y;
	cin>>a>>b>>x>>y;
	cout<<(a+b-gcd(a,b))*2+((a&1)&&(b&1))+1;
	return;
}

Medium 小红的排列构造

简要题意

构造排列 ，使得 不是质数，或报告无解。

Solution

关键是大于 的偶数都是合数。

对 ，显然是无解的。

对 ，直接取 即可。

对 ，令 ，然后转化为上者处理即可。

Code

void R()
{
	int n;
	cin>>n;

	if (n<3)
	{
		cout<<-1;
		return;
	}

	vector<int> a(n);
	iota(a.begin(),a.end(),1);
	reverse(a.begin(),a.end()-(n%2==0));
	for (int i=0;i<n;i++)
		cout<<a[i]<<" \n"[i+1==n];
	return;
}

Hard 串

简要题意

求长度不超过 ，且包含子序列 ab 的小写字符串个数。

Solution

简单数学题。

先考虑长度恰好为 的方案数。

正难则反，我们考虑不含子序列 ab 的小写字符串数，再用 减去即可。

首先，不含 a,b 的串有 中，只含 a 或只含 b 的串各有 种，它们显然都不含子序列 ab 。

考虑同时含有 a,b 的串，要令其不含子序列 ab，则需要所有 a 都出现在串的最后一个 b 之后。

我们枚举最后一个 b 的位置 ，此时方案数则为 。

则长度恰好为 的方案数为 。

记 ，我们要求的答案就是 ，即两个等比数列与一个等差乘等比数列求和。

由高中知识易得，对 ， ，其中 。

时间复杂度 ，瓶颈在于求幂。

下面的代码实现中使用的 MInt 具体实现见此处。

Code

constexpr int P=1e9+7;
using Z=MInt<P>;

void R()
{
	int n;
	cin>>n;

	auto S=[&](Z a,Z b,Z q)->Z
	{
		Z A=a/(q-1),B=(b-A)/(q-1);
		return (A*n+B)*power(q,n)-B;
	};

	cout<<S(0,1,26)*26-S(0,1,25)*25-S(1,0,25);
	return;
}