题解 P2856 【[USACO06FEB]手机Cellphones】

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