P2462 [SDOI2007] 游戏 题解
本题需要使用 STL std::map 和拓扑排序。
先将输入的字符串存入一个 vector，对其进行排序、去重（因为我们并不关心字符串的顺序，排序和去重可以大大减少状态数），便于进行下一步操作。
注意，在输入字符串时也可以对字符串本身排序，因为我们只关心里面的各种字符的个数，并不关心它实际上到底是什么样的，这样也可以减少状态数。但是在对其排序之前要注意建立映射，输出方案时可以快速找到原字符串。
对于每一个字符串，把它下一步可能变成的字符串枚举出来，再查看原字符串集合中有无此字符串（可以用 map 快速查找），如果有那么将前者向后者连边。
最后我们可以得到一个有向无环图，用拓扑排序跑最长路即可。具体地，每到一个点，看看它下一次可以到达的点中，哪些的最长路可以被更新。
在拓扑排序的过程中记一下每个结点的前驱，输出方案时不断找前驱即可。
放代码：
#include<bits/stdc++.h>
using namespace std;
vector<int> g[200001];
int d[200001],f[200001],p[200001];
map<string,int> m;
map<string,string> m2;
int main(){
ios::sync_with_stdio(false);
vector<string> v; string s;
while(cin>>s){
string x=s;
sort(x.begin(),x.end());
// 将字符串本身排序
m2[x]=s; // 把新串和原串建立映射
v.emplace_back(x);
}
sort(v.begin(),v.end()); // 排序
v.erase(unique(v.begin(),v.end()),v.end()); // 去重
for(int i=0;i<v.size();i++)m[v[i]]=i+1;
for(int i=0;i<v.size();i++)
for(char c=97;c<123;c++){
s=v[i]; s.insert(upper_bound(s.begin(),s.end(),c),c);
// 插入一个新的字符，注意要时刻保持字符串中的字符递增
if(m[s])g[i+1].emplace_back(m[s]),d[m[s]]++;
// 如果目标存在就连边
}
queue<int> q;
for(int i=1;i<=v.size();i++)
if(!d[i])q.emplace(i),f[i]=1;
while(!q.empty()){
int t=q.front(); q.pop();
for(int i:g[t]){
if(f[i]<f[t]+1)f[i]=f[t]+1,p[i]=t;
// 更新最长路和前驱
if(!--d[i])q.emplace(i);
}
}
int l=1,e=0;
stack<string> t;
for(int i=1;i<=v.size();i++)
if(f[i]>=l)l=f[i],e=i;
cout<<l<<endl; // 最长长度
while(e)t.emplace(m2[v[e-1]]),e=p[e]; // 不断找前驱
while(!t.empty())cout<<t.top()<<endl,t.pop();
return 0;
}