题解：CF1739F Keyboard Design

· · 题解

思维题。码量题。

首先一个单次如果能被便捷的敲出来，当且仅当它的所有字母两边的字母都与它在键盘上相邻。这样我们可以对于每个单词整理出一个计入贡献时字母在键盘上的相邻关系。接下来我们针对 12 个不同字母分析。

我们很容易注意到，如果一个单词要求一个字母周围有大于等于 3 个邻近的不同字母，那么这个单词无论如何都无法计入贡献。否则必然至多存在 2 个出现在此单词中的字母邻近于仅 1 个不同字母。

数学归纳法。只有两个字母的字符串显然满足条件。假设 S 为一个字符串且 c 为一个字符，并且 S 满足至多存在 2 个出现在 S 中的字母邻近于仅 1 个不同字母，且不存在一个字母邻近于至少 3 个不同字母，以及 S+c 也不存在一个字母临近于至少 3 个不同字母（S+c 相邻字符不同）。

扯那么多是干嘛呢？如果一个单词（没有出现邻近于 3 个不同字母的字母）所有字母按照上述连边方式连出来一个环，那无论如何都无法便捷的被敲出来，而如果连出来的是条链，那么只要这条链从链头到链尾正着或者反着出现在键盘中，该单词就可以贡献频率权值。

由于不同字母数量非常少，时间限制又很大，一条链又无法正着反着同时出现在键盘里，我们可以将所有合法单词的链正反一起建一个 \text{AC} 自动机并且将频率权值下传到可以通过失配指针（也即 \text{border} 指针）跳到当且点的所有点。然后利用状态压缩计算答案即可（方程式设 f_{i,j} 表示当前没定过的字母状态为 i，目前跳到 \text{AC} 自动机的 j 号点）。

代码实现非常长，相当适合锻炼码力：

#include<bits/stdc++.h>
using namespace std;

struct node{
    int son[13],fail,val;
}vert[18005];

int n,c[2005],len[2005],ths[2005][13],pt,clnk[12],ctow[12][12],pt2,rot,dp[4096][18005],H[4096][18005][2],ans,hs1,hs2;

int nw(){
    return++pt2;
}

int nwvert(int now,int num){
    if(vert[now].son[num]==0){
        return vert[now].son[num]=nw();
    }
    return vert[now].son[num];
}

int Link(int now,int num){
    if(vert[now].son[num]==0){
        if(vert[now].fail==0)return rot;
        return Link(vert[now].fail,num);
    }
    return vert[now].son[num];
}

void bfs(){
    queue<int>q;q.push(rot);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int o=1;o<=12;o++){
            if(vert[now].son[o]!=0){
                vert[vert[now].son[o]].fail=now==0?1:Link(vert[now].fail,o);
                vert[vert[now].son[o]].val+=vert[vert[vert[now].son[o]].fail].val;
                q.push(vert[now].son[o]);
            }
        }
    }
}

int main(){
    memset(dp,0xb0,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++){
        int val;string s;bool satis1=0,satis2=1;cin>>val>>s;
        for(int o=0;o<12;o++){
            clnk[o]=0;
            for(int oo=0;oo<12;oo++)ctow[o][oo]=0;
        }
        for(int o=0;o<s.size()-1;o++){
            if(!ctow[s[o]-'a'][s[o+1]-'a'])clnk[s[o]-'a']++;
            ctow[s[o]-'a'][s[o+1]-'a']=1;
            if(!ctow[s[o+1]-'a'][s[o]-'a'])clnk[s[o+1]-'a']++;
            ctow[s[o+1]-'a'][s[o]-'a']=1;
        }
        for(int o=0;o<12;o++){
            if(clnk[o]==1)satis1=1;
            if(clnk[o]>2)satis2=0;
        }
        if(!(satis1&satis2))continue;
        pt++;c[pt]=val;
        for(int o=0;o<12;o++){
            if(clnk[o]!=1)continue;
            for(int oo=o,Lst=-1;;){
                ths[pt][++len[pt]]=oo+1;
                int Nxt=-1;
                for(int ooo=0;ooo<12;ooo++){
                    if(ooo==Lst)continue;
                    if(ctow[oo][ooo]){
                        Nxt=ooo;break;
                    }
                }
                if(Nxt==-1)break;
                Lst=oo;oo=Nxt;
            }
            break;
        }
    }
    for(int i=1;i<=pt;i++){
        len[i+pt]=len[i];c[i+pt]=c[i];
        for(int j=1;j<=len[i];j++){
            ths[i+pt][j]=ths[i][len[i]+1-j];
        }
    }
    pt*=2;rot=nw();
    for(int i=1;i<=pt;i++){
        int cur=rot;
        for(int j=1;j<=len[i];j++){
            cur=nwvert(cur,ths[i][j]);
        }
        vert[cur].val+=c[i];
    }
    bfs();dp[0][1]=0;
    for(int zt=0;zt<4096;zt++){
        for(int o=1;o<=12;o++){
            if((zt&(1<<o-1))!=0)continue;
            for(int i=1;i<=pt2;i++){
                int Nxt=Link(i,o);
                dp[zt^(1<<o-1)][Nxt]=max(dp[zt^(1<<o-1)][Nxt],dp[zt][i]+vert[Nxt].val);
                if(H[zt^(1<<o-1)][Nxt][1]==0||dp[zt][i]+vert[Nxt].val==dp[zt^(1<<o-1)][Nxt]){
                    H[zt^(1<<o-1)][Nxt][0]=zt;H[zt^(1<<o-1)][Nxt][1]=i;
                }
            }
        }
    }
    hs1=4095;
    for(int i=1;i<=pt2;i++){
        ans=max(ans,dp[4095][i]);
        if(dp[4095][i]==ans)hs2=i;
    }
    while(hs1!=0){
        int xornum=hs1^H[hs1][hs2][0];
        for(int o=1;o<=12;o++){
            if(xornum==(1<<o-1)){
                cout<<char('a'+o-1);break;
            }
        }
        hs2=H[hs1][hs2][1];hs1^=xornum;
    }
    return 0;
}