Luogup2462 “SDOI2007” game

On how to use \(stl\) to get rid of this question

Open\( Maxl\) \(vector\), use \(string_i\) to save the length as \(i\) all the strings, so enumerating in order can guarantee no aftereffect

We found that the transfer only sum The number of occurrences of each letter \(c\) \(cnt_c\) is related if and only if the following Conditions \(j\) can be used to update \(i\)

< li>\(l_i=l_j+1\)
1. \(\exists c,cnt_ {ic}=cnt_{jc}+1\)
2. \(\forall c’\ne c,cnt_{ic’}=cnt_{ jc’)\)

Using violence \(hash\), each Letters \(c\) are assigned \(key_c\), the hash value of each string is equal to The sum of all letters, enumerate \(c\) when updating, look at the hash value of the entire string minus \( key_c\) Can you bring it Just update, this can be saved directly with disordered \(map\)

Pay attention to the output scheme, so disordered\(map\) is mapped to a \(pair\)

complexity\(O(n*max(26,Maxl))\)

\(code:\)

#includeusing namespace std;const int mod=1e9+7;typedef long long ll;typedef pair pii;int key[ 30],maxl,fr[30],ans=1,las,pre[10100],n;string s;vectorbuc[233];ll seed;string S[10010];int rnd(){ ll ret=seed; seed=(seed*7+13)%mod; return ret%mod;}unordered_mapf;#define mp(x,y) make_pair(x,y)void print(int x) {if(pre[x])print(pre[x]); cout<>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
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);}

< /p>