自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:26:14，当前版本为作者最后更新于2022-04-06 10:09:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题是 NWRRC 2015 Problem H。

本题在 CodeForces 上有提交通道：Gym 100801H。

首先，考虑下面的字符串：

cccccccccccccccccccccccccccccccccccccccccccccccccc

一共 $50$ 个 c。

此处，为了表述方便，将这 $50$ 个 c 从左往右依次记为第 $49,48,\ldots,0$ 位。

接下来，将任意多个（$0 \sim 25$ 个）互不重叠的 cc 改为 dD，即可构造哈希值相等的不同字符串。限制修改次数为 $0 \sim 2$ 次，即可得到 $1178$ 个字符串，通过本题。

证明：

设被修改的 cc 分别处于第 $i+1$ 位和第 $i$ 位（$i=48,47,\ldots,0$），则它们贡献的哈希值为：

$\quad 99 \times 31^{i+1}+99 \times 31^i$

$=99 \times 31 \times 31^i+99 \times 31^i$

$=(99 \times 31 +99) \times 31^i$

$=3168 \times 31^i.$

改为 dD 后，它们贡献的哈希值为：

$\quad 100 \times 31^{i+1}+68 \times 31^i$

$=100 \times 31 \times 31^i+68 \times 31^i$

$=(100 \times 31 +68) \times 31^i$

$=3168 \times 31^i.$

显然二者相等，因此修改后哈希值不变。

AC Code：

#include<iostream>
#include<string>
using namespace std;
const string stds="cccccccccccccccccccccccccccccccccccccccccccccccccc";//原字符串
const string rs="dD";//用于修改的字符串
int main()
{
	string s;
	int k,ans=1;
	cin>>k;
	cout<<stds<<'\n';//修改 0 次
	for(int i=0;i<=48;i++)//修改 1 次
	{
		if(ans==k) return 0;
		s=stds;
		s.replace(i,2,rs);
		cout<<s<<'\n';
		ans++;
	}
	for(int i=0;i<=46;i++)
		for(int j=i+2;j<=48;j++)//修改 2 次
		{
			if(ans==k) return 0;
			s=stds;
			s.replace(i,2,rs);
			s.replace(j,2,rs);
			cout<<s<<'\n';
			ans++;
		}
    return 0;
}