luoguP2462「SDOI2007」游戏

题目描述

链接

接龙的规则如下:

1 前一个单词拥有的所有字母，在后一个单词里必须出现，而且字母出现次数不少于前一单词。

2 后一个单词的长度比前一个单词的长度恰好多1

求最长的接龙长度

\(l_i \leq 100,n \leq 10^4\)

题解

论如何使用 \(stl\) 搞掉此题

开 \(Maxl\) 个 \(vector\),用 \(string_i\) 存下长度为 \(i\) 的所有字符串,这样按照顺序枚举能保证无后效性

我们发现这道题中转移只和每个字母 \(c\) 的出现次数 \(cnt_c\) 有关,当且仅当满足如下条件时 \(j\) 能用来更新 \(i\)

1. \(l_i=l_j+1\)
   
2. \(\exists c,cnt_{ic}=cnt_{jc}+1\)
3. \(\forall c'\ne c,cnt_{ic'}=cnt_{jc'}\)

利用暴力 \(hash\) ,将每个字母 \(c\) 赋值 \(key_c\) ,每个字符串的哈希值就等于所有字母之和,更新的时候枚举 \(c\) ,看一下整串的哈希值减去 \(key_c\) 能不能拿来更新即可,这个可以直接用无序 \(map\) 来存

注意要输出方案,所以无序 \(map\) 中映射到的是一个 \(pair\)

复杂度 \(O(n*max(26,Maxl))\)

\(code:\)

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int key[30],maxl,fr[30],ans=1,las,pre[10100],n;
string s;
vector<string>buc[233];
ll seed;
string S[10010];
int rnd()
{
    ll ret=seed;
    seed=(seed*7+13)%mod;
    return ret%mod;
}
unordered_map<int,pii>f;
#define mp(x,y) make_pair(x,y)
void print(int x)
{
    if(pre[x])print(pre[x]);
    cout<<S[x]<<endl;   
}
int main()
{
    seed=19260817;
    for(int i=0;i<26;++i)key[i]=rnd();
    while(cin>>s)
    {
        int l=s.length();
        buc[l].push_back(s);
        if(l>maxl)maxl=l;
    }
    for(int l=1;l<=maxl;++l)
    {
        if(buc[l].empty())continue;
        for(int i=0,p=buc[l].size();i<p;++i)
        {
            int has=0;
            s=buc[l][i];S[++n]=s;
            for(int j=0;j<26;++j)fr[j]=0;
            for(int j=0;j<l;++j)++fr[s[j]-'a'],has=(has+key[s[j]-'a'])%mod;
            f[has].first=1,f[has].second=n;
            for(int j=0;j<26;++j)
            {
                int pp=(has-key[j]+mod)%mod;
                if(f.count(pp)&&f[pp].first+1>f[has].first)f[has].first=f[pp].first+1,pre[n]=f[pp].second;
            }
            if(f[has].first>=ans)las=n,ans=f[has].first;
        }
    }
    printf("%d\n",ans);
    print(las);
}