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

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

Easy 小红的对称串

简要题意

确定一个串镜面翻转后是否与原串相同。注意字母翻转后可能变成自身、其它字母或没有对应字母。

Solution

如果一个串中有翻转后没有对应字母的字母，翻转后一定与原串不同。

否则将翻转后变成其它字母的字母修改成翻转后对应字母，然后整体 reverse 跟原串比较即可。

Code

void R()
{
	string s,t,tab="ilmnouvwxpqbd";
	cin>>s;
	t=s;
	for (char &c:s)
	{
		if (count(tab.begin(),tab.end(),c)==0)
		{
			cout<<"No\n";
			return;
		}
		if (c=='p')
			c='q';
		else if (c=='q')
			c='p';
		else if (c=='b')
			c='d';
		else if (c=='d')
			c='b';
	}
	reverse(t.begin(),t.end());
	cout<<(s==t?"Yes\n":"No\n");
	return;
}

Medium Y型树

简要题意

将 $n-1$ 个无标号球放入 $3$ 个无标号盒里，使盒子均非空，求方案数。

Solution

题目要求的其实就是分拆数 $p(n-1,3)$ 。

考虑 $p(n,k)=p(n-1,k-1)+p(n-k,k)$ ，可以得到 $p(n,2)=\left\lfloor \frac{n}{2} \right\rfloor,p(n,3)=p(n-1,2)+p(n-3,3)$ 。

记 $f_n=p(n,3)$ ，令 $n$ 取偶数则有：

\begin{aligned} f_n &= f_{n-3}+\frac{n}{2}-1 \\ f_{n-1} &= f_{n-4}+\frac{n}{2}-1 \\ \end{aligned} \Rightarrow \begin{aligned} f_n+f_{n-1} &= f_{n-3}+f_{n-4}+n-2 \\ f_n-f_{n-1} &= f_{n-3}-f_{n-4} \\ \end{aligned} \Rightarrow \begin{aligned} f_n &= 2f_{n-3}+n-2 \\ f_{n-1} &= 2f_{n-4}+n-2 \\ \end{aligned}

所以 $f$ 有一个步长为 $6$ 的递推，形如 $f_n = 4f_{n-6}+3n+C$ ，则模 $6$ 同余位置的 $f$ ，是关于 $\left\lfloor \frac{n}{6} \right\rfloor$ 的二次多项式。

所以我们算出前 $18$ 位 $f$ ，根据 $n \bmod 6$ 插出对应的多项式即可。

Code

void R()
{
	constexpr int P=1e9+7;
	vector<array<i64,4>> p(18);
	p[0][0]=1;
	for (int i=1;i<18;i++)
		for (int j=1;j<4;j++)
			p[i][j]=p[i-1][j-1]+p[max(i-j,0)][j];
	
	i64 n;
	cin>>n;
	n--;
	i64 r=n%6,f0=p[r][3],f1=p[r+6][3],f2=p[r+12][3];
	i64 d=n/6%P,A=(f0+f2)/2-f1,B=f1-f0-A,C=f0;
	cout<<((A*d+B)%P*d+C)%P<<'\n';
	return;
}

Hard 【模板】二分

简要题意

给一个非降数组，每次选一个区间询问第一个大于/小于/大于等于/小于等于某个数的数。

Solution

写到这里大家应该都会二分，这题放在这里有点意义不明。

考察 lower_bound 的指针是否在首末位置即可。

Code

void R()
{
	int n,q;
	cin>>n>>q;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	while (q--)
	{
		int op,l,r,x;
		cin>>op>>l>>r>>x;
		if (op==1)
		{
			auto it=lower_bound(a.begin()+l,a.begin()+r,x);
			if (it==a.begin()+r) cout<<"-1\n";
			else cout<<*it<<'\n';
		}
		else if (op==2)
		{
			auto it=upper_bound(a.begin()+l,a.begin()+r,x);
			if (it==a.begin()+r) cout<<"-1\n";
			else cout<<*it<<'\n';
		}
		else if (op==3)
		{
			auto it=lower_bound(a.begin()+l,a.begin()+r,x);
			if (it==a.begin()+l) cout<<"-1\n";
			else cout<<*prev(it)<<'\n';
		}
		else
		{
			auto it=upper_bound(a.begin()+l,a.begin()+r,x);
			if (it==a.begin()+l) cout<<"-1\n";
			else cout<<*prev(it)<<'\n';
		}
	}
	return;
}

#牛客春招刷题训练营#