牛客春招刷题训练营 - 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型树

简要题意

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

Solution

题目要求的其实就是分拆数 。

考虑 ，可以得到 。

记 ，令 取偶数则有：

所以 有一个步长为 的递推，形如 ，则模 同余位置的 ，是关于 的二次多项式。

所以我们算出前 位 ，根据 插出对应的多项式即可。

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;
}