题解：CF467D Fedor and Essay

· · 题解

CF467D Fedor and Essay

题目传送门

思路

将每一个字符串哈希，然后每个不同的哈希值对应一个点。每个对应点都开一个 pair，第一维是该串中 R 的个数，第二维是该串的长度。若串 x 可以变成串 y，则把 x 的对应点向 y 的对应点连一条边。

将对应点建出来的图缩点，其中每个强连通分量的权值就是里面所有点以第一维优先的最小值。对缩点后的图拓扑排序，每个点的 pair 的值是它能够到达的所有点的最小值。最后答案将 n 个文章中的串的对应点所在的强连通分量的 pair 加起来即可。

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pb push_back
#define pii  pair<int,int> 
#define mk make_pair
using namespace std;
const int N=1e6+10;
int n,m,color[N],p[N],cnt,tot,len,color_cnt,in[N],dfn[N],low[N];
pii a[N],a2[N];
vector<int>e[N],e2[N];
unordered_map<ull,int>mp; 
string s[N];
inline pii change(string &s){
    int cnt=0;
    for(int i=0;i<(int)s.size();++i){
      if(s[i]>='a'&&s[i]<='z')s[i]-='a'-'A';
      if(s[i]=='R')++cnt;
    }
    return mk(cnt,s.size());
}
inline ull hashs(string s){
    ull res=0,p=10007;
    for(char c:s)res=res*p+c;
    return res;
}
inline void dfs(int u){
    dfn[u]=low[u]=++cnt;
    in[u]=1;
    p[++len]=u;
    for(auto v:e[u]){
      if(!dfn[v]){
        dfs(v);
        low[u]=min(low[u],low[v]);
      }
      else if(in[v])low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
      ++color_cnt;
      a2[color_cnt]=a[u];
      while(p[len]!=u){
        in[p[len]]=0;
        color[p[len]]=color_cnt;
        if(a[p[len]].first<a2[color_cnt].first||(a[p[len]].first==a2[color_cnt].first&&a[p[len]].second<a2[color_cnt].second))
          a2[color_cnt]=a[p[len]];
        --len;
      }
      in[p[len]]=0;
      color[p[len]]=color_cnt;
      if(a[p[len]].first<a2[color_cnt].first||(a[p[len]].first==a2[color_cnt].first&&a[p[len]].second<a2[color_cnt].second))
        a2[color_cnt]=a[p[len]];
      --len;
    }
}
inline void topusort(){
    queue<int>q;
    for(int i=1;i<=color_cnt;++i)if(!in[i])q.push(i);
    while(q.size()){
      int u=q.front();
      q.pop();
      for(auto v:e2[u]){
        --in[v];
        if(!in[v])q.push(v);
        if(a2[u].first<a2[v].first||(a2[u].first==a2[v].first&&a2[u].second<a2[v].second))a2[v]=a2[u];
      }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
      cin>>s[i];
      pii id=change(s[i]);
      ull ha=hashs(s[i]);
      if(mp.find(ha)==mp.end()){
        mp[ha]=++tot;
        a[tot]=id;
      }
    }
    string s1,s2;
    cin>>m;
    for(int i=1;i<=m;++i){
      cin>>s1>>s2;
      pii id=change(s1);
      ull ha=hashs(s1);
      if(mp.find(ha)==mp.end()){
        mp[ha]=++tot;
        a[tot]=id;
      }
      id=change(s2);
      ull ha2=hashs(s2);
      if(mp.find(ha2)==mp.end()){
        mp[ha2]=++tot;
        a[tot]=id;
      }
      e[mp[ha]].pb(mp[ha2]);
    }
    for(int i=1;i<=tot;++i)if(!dfn[i])dfs(i);
    for(int i=1;i<=tot;++i){
      for(auto v:e[i]){
        if(color[i]!=color[v]){
          e2[color[v]].pb(color[i]);
          ++in[color[i]];
        }
      }
    }
    topusort();
    pii ans=mk(0,0);
    for(int i=1;i<=n;++i){
      ull ha=hashs(s[i]);
      ans.first+=a2[color[mp[ha]]].first;
      ans.second+=a2[color[mp[ha]]].second;
    }
    cout<<ans.first<<" "<<ans.second<<"\n";
    return 0;
}