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

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

Easy 小美的排列询问

简要题意

询问一个排列中两个数是否相邻。

Solution

记录每个数的位置，判断绝对差是否为 即可。

Code

void R()
{
	int n,x,y;
	cin>>n;
	vector<int> p(n+1);
	for (int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		p[x]=i;
	}

	cin>>x>>y;
	cout<<(abs(p[x]-p[y])==1?"Yes":"No");
	return;
}

Medium 小红的字符串构造

简要题意

给一个字符串 ，构造一个字符串 ，使得 中每个字母的出现次数与 相同，且没有一个位置 使得 ，或报告无解。

Solution

记录每个字母出现位置，先按对应字母出现次数对位置排序，记排序得到的位置数组为 。

将 中第一个字母对应的位置段挪到最后，记为 。

令 ，若有交则无解，否则得到构造。

Code

void R()
{
	string s,t;
	cin>>s;

	t=s;
	int n=s.size();
	vector<int> A,B;

	vector<vector<int>> pos(26);
	for (int i=0;i<n;i++)
		pos[s[i]-'a'].push_back(i);
	sort(pos.begin(),pos.end(),[&](auto &x,auto &y)
	{
		return x.size()>y.size();
	});
	pos.push_back(pos[0]);
	for (int i=0;i<26;i++)
		for (int p:pos[i])
			A.push_back(p);
	for (int i=1;i<=26;i++)
		for (int p:pos[i])
			B.push_back(p);
	for (int i=0;i<n;i++)
		t[B[i]]=s[A[i]];
	for (int i=0;i<n;i++)
		if (s[i]==t[i])
		{
			cout<<-1;
			return;
		}
	cout<<t;
	return;
}

Hard [ZJOI2010]COUNT 数字计数

简要题意

对区间 内自然数的各个数位，求 分别出现了多少次。

Solution

只要能求 的答案 ， 即为原题的答案，下面考虑如何求 。

记 在十进制下有 位。

记 表示考虑到十进制下第 位（从高位到低位考虑，个位为第零位）为 ，当前以确定的数位是否与 的前 位一致的前提下，前 位有多少种方案，有转移：

其中 是 的第 位。

则数位 的出现次数为 。

Code

void R()
{
	auto solve=[&](i64 x)->vector<i64>
	{
		vector<i64> cnt(10),dig,pw;
		if (!x) return cnt;
		int L=0;
		i64 tmp=1;
		while (x>=tmp)
		{
			pw.push_back(tmp);
			dig.push_back(x/tmp%10);
			tmp*=10;
			L++;
		}
		pw.push_back(tmp);

		vector<vector<array<i64,2>>> dp(L,vector<array<i64,2>>(10));
		dp[L-1][dig[L-1]][1]=1;
		for (int i=1;i<dig[L-1];i++)
			dp[L-1][i][0]=1;
		for (int i=L-1;i;i--)
		{
			for (int j=1;j<10;j++)
				dp[i-1][j][0]++;
			for (int j=0;j<10;j++)
			{
				for (int k=0;k<10;k++)
				{
					dp[i-1][k][0]+=dp[i][j][0];
					if (k<dig[i-1])
						dp[i-1][k][0]+=dp[i][j][1];
				}
				dp[i-1][dig[i-1]][1]+=dp[i][j][1];
			}
		}

		for (int i=0;i<L;i++)
			for (int j=0;j<10;j++)
				cnt[j]+=dp[i][j][0]*pw[i]+dp[i][j][1]*(x%pw[i]+1);
		return cnt;
	};


	i64 a,b;
	cin>>a>>b;
	auto A=solve(a-1),B=solve(b);
	for (int i=0;i<10;i++)
		cout<<B[i]-A[i]<<" \n"[i==9];
	return;
}