自动搬运

查看原文

来自洛谷，原作者为

	HPXXZYY 笑看世事似水变迁

搬运于2025-08-24 21:42:20，当前版本为作者最后更新于2020-01-01 20:40:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

【题目翻译】： 奶牛的名字都是由英文字母表的前$L(1 \leq L \leq 26)$个字母构成的（全部为大写字母且长度$\leq 10$）。现在奶牛们想设计一种手机， 有$B$个按键。请你把这$L$个字母按顺序分配给$B$个按键，使能够通过按这些键而唯一确定的奶牛数尽量多。求最多可以唯一确定多少头奶牛，输出方案。如果有多种方案，输出编号小的按键容纳字母最多的方案。

【思路】： 暴力枚举每个字母分配给哪个按键。记$ch[i]$表示字母$i$分配给按键$ch[i]$。不难发现，$ch$可以用搜索算法得出。

假设我们已经得到了$ch[i]$，考虑如何计算可以唯一确定多少头奶牛的名字。

依题意，每头奶牛的名字长度$\leq 10$，我们可以视整个字符串为一个$B+1$进制的数，这样就可以判断每个字符串的hash值。得到hash值后，我们就可以判断每个字符串是否只出现一次了。

【注意】： 数据的开头有一个没有用的整数，必须把它输入但忽略掉。

【代码】：

int L,B,ans,ch[30],CH[30];
string str[1010];int n;
long long num[1010];
void updata_answer(){
	memset(num,0,sizeof(num));
	for(int i=1;i<=n;i++)
		for(int j=0;j<str[i].size();j++)
			num[i]=num[i]*(B+1)+ch[str[i][j]-'A'+1];//计算hash值
	sort(num+1,num+n+1);
	register int tot=0;
	for(int i=1;i<=n;i++)
		if (num[i]!=num[i-1]&&num[i]!=num[i+1]) tot++;//计算有多少个不同的字符串
	if (tot>=ans){//注意这样才保证了答案字典序最小
		ans=tot;
		memcpy(CH,ch,sizeof(ch));
	}
}
void dfs(int sub,int color){
	if (sub>L){
		if (color>=B)
			updata_answer();
		return;
	}
	if (sub>1&&color<B){
		ch[sub]=color+1;
		dfs(sub+1,color+1);
	}
	if (color+L-sub>=B){
		ch[sub]=color;
		dfs(sub+1,color);
	}
	ch[sub]=-1;
}
int test_number;
int main(){
	cin>>test_number;test_number=1;//忽略掉这个无用的数字
	while (test_number--){
		memset(ch,-1,sizeof(ch));
		cin>>B>>L>>n;
		for(int i=1;i<=n;i++)
			cin>>str[i];
		dfs(1,1);CH[0]=CH[1]-1;
		printf("%d",ans);
		for(int i=1;i<=L;i++)
			if (CH[i]!=CH[i-1])
				printf("\n%c",(char)(i+'A'-1));
			else printf("%c",(char)(i+'A'-1));
		printf("\n");
	}
	return 0;
}