H-Modify Minieye杯第十五届华中科技大学程序设计邀请赛现场赛

题面见 https://ac.nowcoder.com/acm/contest/700#question

题目大意是有n个单词，有k条替换规则（单向替换），每个单词会有一个元音度（单词里元音的个数）和长度，现在希望利用替换规则（每个规则可使用无限次或不用）将每个单词替换成元音度值最小的单词，如果有多个单词元音度同等最小，那么取长度最小的单词。最后输出替换后的n个单词的元音度值之和与长度之和。

单纯每个点暴力搜，无疑会有爆复杂度的风险 1e5*1e5 ，如果记录搜过的点之后不搜，也会有在一个强连通分量里最早的点能搜到最优解，而后来的点无法get到这个最有解。

于是我们可以用Tarjan求scc后缩点，然后在缩点之后的分量图开始DFS。因为这个分量图是绝对无环的图，所以可以在不重复搜点下得到最优解。

比赛时替换最优解的判断写错了，昏了头把长度的比较搞错。然后此题还有一个坑点，就是开始给的n个单词中可能会有重复，不能直接由string映射至点号。

比赛时代码修改后的通过版本：

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 #define IsVow(i) ((i)=='a'||(i)=='e'||(i)=='i'||(i)=='o'||(i)=='u')
  5 typedef long long ll;
  6 
  7 const int maxn=300000+5;
  8 struct Edge{
  9     int from,to;
 10     int nxt;
 11 };
 12 struct word{
 13     int vow,len;
 14 }voc[maxn], syno[maxn];;
 15 bool vis[maxn];
 16 int head[maxn],tot;
 17 Edge edges[maxn];
 18 map<string , int > dict;
 19 string ori[maxn];
 20 int DFN[maxn],LOW[maxn],STACK[maxn],Belong[maxn];
 21 int scc,dfs_no,top;
 22 bool Instack[maxn];
 23 vector< vector< int > > G(maxn, vector<int>() );
 24 
 25 void addedge(int u,int v){
 26     edges[tot].from=u;
 27     edges[tot].to=v;
 28     edges[tot].nxt=head[u];
 29     head[u]=tot++;
 30 }
 31 
 32 word make_word(string & s){
 33     int cnt=0;
 34     word ans;
 35     ans.len=(int) s.size();
 36     for(auto const& i:s)
 37         if(IsVow(i)) cnt++;
 38     ans.vow=cnt;
 39     return ans;
 40 }
 41 
 42 void Tarjan(int u){
 43     LOW[u]=DFN[u]=++dfs_no;
 44     STACK[++top]=u;
 45     Instack[u]=true;
 46     for(int i=head[u];i!=-1;i=edges[i].nxt){
 47         int v=edges[i].to;
 48         if(!DFN[v]){
 49             Tarjan(v);
 50             LOW[u]=min(LOW[u],LOW[v]);
 51         }
 52         else if(Instack[v])
 53             LOW[u]=min(LOW[u],DFN[v]);
 54     }
 55     if(LOW[u]==DFN[u]){
 56         scc++;
 57         syno[scc]=(word){500005,500005};
 58         while(STACK[top]!=u){
 59             int v=STACK[top];
 60             if(voc[v].vow < syno[scc].vow)
 61             {                      
 62                 syno[scc].vow=voc[v].vow;
 63                 syno[scc].len=voc[v].len;
 64             }
 65             else if( syno[scc].vow == voc[v].vow) 
 66                 syno[scc].len=min(syno[scc].len,voc[v].len);
 67             
 68 
 69             Instack[STACK[top]]=false;
 70             Belong[STACK[top--]]=scc;
 71 
 72         }
 73         Instack[u]=false;
 74         Belong[u]=scc;
 75         top--;
 76                     if(voc[u].vow < syno[scc].vow)
 77             {                      
 78                 syno[scc].vow=voc[u].vow;
 79                 syno[scc].len=voc[u].len;
 80             }
 81             else if( syno[scc].vow == voc[u].vow) 
 82                 syno[scc].len=min(syno[scc].len,voc[u].len);
 83                 }
 84 }
 85 
 86 void DFS(int ind){
 87     //cout<<ind<<":"<<syno[ind].vow<<" , "<<syno[ind].len<<endl;
 88     if(vis[ind]){
 89         return ;
 90     }
 91     vis[ind]=true;
 92 
 93     for(int i=0;i<G[ind].size();++i){
 94         int nxind=G[ind][i];
 95         DFS(nxind);
 96         if(syno[nxind].vow < syno[ind].vow)
 97         {                      
 98             syno[ind].vow=syno[nxind].vow;
 99             syno[ind].len=syno[nxind].len;
100         }
101         else if( syno[nxind].vow == syno[ind].vow) 
102                 syno[ind].len=min(syno[ind].len,syno[nxind].len);
103         }
104 }
105 
106 int main(){
107     ios::sync_with_stdio(false);cin.tie(0);
108     memset(head,-1,sizeof(head));
109     tot=0;
110     int n,k;
111     cin>>n;
112     int TOT=0;
113     for(int i=1;i<=n;++i){
114         string tmp;
115         cin>>tmp;
116         ori[i]=tmp;
117         if(dict.count(tmp)==0){
118         dict[tmp]=++TOT;
119         voc[dict[tmp]]=make_word(tmp);
120         }
121     }
122     cin>>k;
123     //cout<<"N:K:"<<n<<k<<endl;
124     for(int i=0;i<k;++i){
125         string frm,to;
126         cin>>frm>>to;
127         if(dict.count(frm)==0) {dict[frm]=++TOT;voc[dict[frm]]=make_word(frm);}
128         if(dict.count(to)==0)  {dict[to]=++TOT;voc[dict[to]]=make_word(to);}
129         addedge(dict[frm],dict[to]);
130     }
131     scc=0;
132     for(int i=1;i<=n;++i)
133         if(!DFN[i])
134             Tarjan(i);
135     /*
136     for(int i=1;i<=scc;++i)
137         syno[i]=(word){500000+5,5000000+5};
138         */
139     for(int i=0;i<tot;++i){
140         int u=edges[i].from,v=edges[i].to;
141         if(Belong[u]!=Belong[v]){
142             G[Belong[u]].push_back(Belong[v]);
143         }
144     }
145     
146     /*
147     for(int i=1;i<=TOT;++i){
148         int ind=Belong[i];
149         if(syno[ind].vow > voc[i].vow)
150         {
151             syno[ind].vow= voc[i].vow;
152             syno[ind].len= voc[i].len;
153         }
154         else if(syno[ind].vow == voc[i].len)
155             syno[ind].len= min(syno[ind].len,voc[i].len); 
156     }
157     */
158     ll X=0,Y=0;
159     //for(int i=1;i<=scc;++i)
160     //    cout<<"scc "<<i<<" : "<<syno[i].vow<<" and "<<syno[i].len<<endl;
161     
162     for(int i=1;i<=scc;++i){
163         int ans1,ans2;
164         ans1=syno[i].vow;
165         ans2=syno[i].len;
166         DFS(i);
167     }
168     
169     for(int i=1;i<=n;++i){
170         int ans1, ans2;
171         ans1=syno[Belong[dict[ori[i]]]].vow;
172         ans2=syno[Belong[dict[ori[i]]]].len;
173         //DFS(Belong[i],ans1,ans2);
174         //cout<<Belong[i]<<endl;
175         X+=1ll*ans1;
176         Y+=1ll*ans2;
177     }
178     cout<<X<<' '<<Y<<endl;
179     return 0;
180 }

View Code

后来看到别人代码，发现可以定义一个类，把优解与劣解的比较重载为<

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define IsVow(x) ((x)=='a'||(x)=='e'||(x)=='i'||(x)=='o'||(x)=='u')
  5 typedef long long ll;
  6 const int maxn=3e5+5;
  7 struct word{
  8     ll  vow;
  9     ll  len;
 10     word(){}
 11     word(ll _v,ll _l):vow(_v),len(_l){}
 12     bool operator< (const word & tmp)const{
 13         if(vow==tmp.vow) return len<tmp.len;
 14         return vow<tmp.vow;
 15     }
 16     word operator+ (const word& tmp)const{
 17         return word(vow+tmp.vow,len+tmp.len);
 18     }
 19 };
 20 word voc[maxn],syno[maxn];
 21 
 22 struct Edge{
 23     int from;
 24     int to;
 25     int nxt;
 26 }edges[maxn];
 27 map<string ,int > dict;
 28 string strcash[100000+5];
 29 int head[maxn],tot;
 30 
 31 int DFN[maxn],LOW[maxn],STK[maxn],BLG[maxn],top=0,scc=0,dfs_no=0;
 32 bool InSTK[maxn];
 33 vector< vector< int > > G(maxn+1,vector<int>() );
 34 int vis[maxn];
 35 void Tarjan(int u){
 36     LOW[u]=DFN[u]=++dfs_no;
 37     STK[top++]=u;
 38     InSTK[u]=true;
 39     for(int i=head[u];i!=-1;i=edges[i].nxt){
 40         int v=edges[i].to;
 41         if(!DFN[v]){
 42             Tarjan(v);
 43             LOW[u]=min(LOW[u],LOW[v]);
 44         }
 45         else if(InSTK[v])
 46             LOW[u]=min(LOW[u],DFN[v]);
 47     }
 48     if(DFN[u]==LOW[u]){
 49         int v;
 50         scc++;
 51         syno[scc]=word(500000+5,500000+5);
 52         do{
 53             v=STK[--top];
 54             InSTK[v]=false;
 55             BLG[v]=scc;
 56             if(voc[v]<syno[scc])
 57                 syno[scc]=voc[v];
 58         }while(u!=v);
 59     }
 60 }
 61 
 62 word make_word(string X){
 63     ll _l=1ll*X.length();
 64     ll _v=0;
 65     for(auto const & i:X){
 66         if(IsVow(i)) _v++;
 67     }
 68     return word(_v,_l);
 69 }
 70 
 71 void AddEdge(int u,int v){
 72     edges[tot].from=u;
 73     edges[tot].to=v;
 74     edges[tot].nxt=head[u];
 75     head[u]=tot++;
 76 }
 77 
 78 void DFS(int u){
 79     if(vis[u]) return;
 80     vis[u]=true;
 81     for(auto v:G[u]){
 82         DFS(v);
 83         if(syno[v]<syno[u]) syno[u]=syno[v];
 84     }
 85 }
 86 
 87 int main(){
 88     ios::sync_with_stdio(false);cin.tie(0);
 89     int _n,_k;
 90     int vtx_no=0;
 91     cin>>_n;
 92     for(int i=0;i<_n;++i){
 93         string tmp;cin>>tmp;
 94         strcash[i]=tmp;
 95         if(dict.count(tmp)==0){
 96             dict[tmp]=++vtx_no;
 97             voc[vtx_no]=make_word(tmp);
 98         }
 99     }
100     cin>>_k;
101     memset(head,-1,sizeof(head));
102     tot=0;
103     for(int i=0;i<_k;++i){
104         string frm,to;cin>>frm>>to;
105         if(dict.count(frm)==0){
106             dict[frm]=++vtx_no;
107             voc[vtx_no]=make_word(frm);
108         }
109         if(dict.count(to)==0){
110             dict[to]=++vtx_no;
111             voc[vtx_no]=make_word(to);
112         }
113         AddEdge(dict[frm],dict[to]);
114     }
115 
116     top=0,scc=0,dfs_no=0;
117     for(int i=1;i<=vtx_no;++i){
118         if(!DFN[i]) Tarjan(i);
119     }
120     for(int i=0;i<tot;++i){
121         int u=edges[i].from,v=edges[i].to;
122         u=BLG[u];
123         v=BLG[v];
124         if(u!=v) G[u].push_back(v);
125     }
126     //for(int i=1;i<=vtx_no;++i) cout<<"voc "<<i<<" : "<<voc[i].vow<<" , "<<voc[i].len<<endl;
127     //for(int i=1;i<=vtx_no;++i) cout<<strcash[i]<<":"<<i<<" belongs to "<<BLG[i]<<endl;
128     memset(vis,false,sizeof(vis));
129     //for(int i=1;i<=scc;++i) cout<<syno[i].vow<<" "<<syno[i].len<<endl;
130     for(int i=1;i<=scc;++i){
131         DFS(i);
132     }
133     //puts("after DFS:");for(int i=1;i<=scc;++i) cout<<syno[i].vow<<" "<<syno[i].len<<endl;
134     ll __X=0,__Y=0;
135     for(int i=0;i<_n;++i){
136         int ob=BLG[dict[strcash[i]]];
137         __X+=syno[ob].vow;
138         __Y+=syno[ob].len;
139     }
140     cout<<__X<<" "<<__Y<<endl;
141     return 0;
142 }

View Code

转念一想，所谓点之间的优劣比较不就是先比元音数，元音数同则比长度吗？这不就是 STL里pair 的比较吗！？要啥结构体，要啥重载< ！？

在算导上求scc那部分，有一个定理，有向图G=<V,E>的强连通分量与其逆图~G=<V,~E>的强连通分量是重合的。（逆图，，，沉思，，，

想一想，如果不缩点，在求解搜点时从每个点搜到其最优解点的路径是一条单向路径，同一个scc内的点能到的最优解是相同的，不同的scc也可能到相同的优解，它们的终点是相同的，终点相同我们可以做逆图！！！也就是从这个解按反向搜到可以到达这个解的所有点。

在建图时，有向边方向取逆，搜索时从最优的点（用间接排序）开始搜，如此只用一遍DFS。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define IsVow(i) ((i)=='a'||(i)=='e'||(i)=='i'||(i)=='o'||(i)=='u')
 5 typedef long long ll;
 6 
 7 string strcash[100000+5];
 8 
 9 map<string ,int > dict;
10 pair<ll,ll > word[300000+5];
11 int word_no=0;
12 
13 struct Edge{
14     int to;
15     int nxt;
16 }edges[200000+5];
17 int head[300000+5],tot;
18 
19 int id[300000+5];
20 bool vis[300000+5];
21 
22 pair<ll,ll> make_word(string X){
23     ll len=X.length();
24     ll cnt=0;
25     for(const auto  & i:X){
26         if(IsVow(i)) cnt++;
27     }
28     return make_pair(cnt,len);
29 }
30 
31 void AddVtx(string X){
32     if(dict.count(X)==0){
33         dict[X]=++word_no;
34         word[word_no]=make_word(X);
35     }
36 }
37 
38 void AddEdge(int u,int v){
39     edges[tot].to=v;
40     edges[tot].nxt=head[u];
41     head[u]=tot++;
42 }
43 
44 bool cmp(int i,int j){
45     return word[i]<word[j];
46 }
47 
48 void DFS(int u){
49     if(vis[u]) return;
50     vis[u]=true;
51     for(int i=head[u];i!=-1;i=edges[i].nxt){
52         int v=edges[i].to;
53         //cout<<u<<"->"<<v<<endl;
54         if(!vis[v]){
55             word[v]=word[u];
56             //cout<<"DFS "<<v<<endl;
57             DFS(v);
58         }
59     }
60 }
61 
62 int main(){
63     ios::sync_with_stdio(false);cin.tie(0);
64 
65     memset(head,-1,sizeof(head));
66     tot=0;
67 
68     int n,k;
69     cin>>n;
70     for(int i=0;i<n;++i){
71         cin>>strcash[i];
72         AddVtx(strcash[i]);
73     }
74     cin>>k;
75     for(int i=0;i<k;++i){
76         string f,t;cin>>f>>t;
77         AddVtx(f);
78         AddVtx(t);
79         AddEdge(dict[t],dict[f]);// ~G
80     }
81 
82     for(int i=1;i<=word_no;++i)
83         id[i]=i;
84     sort(id+1,id+1+word_no,cmp);
85     memset(vis,false,sizeof(vis));
86     for(int i=1;i<=word_no;++i){
87         DFS(id[i]);
88     }
89 
90     ll X=0,Y=0;
91     for(int i=0;i<n;++i){
92         int _no=dict[strcash[i]];
93         X+=word[_no].first;
94         Y+=word[_no].second;
95     }
96     cout<<X<<" "<<Y<<endl;
97     return 0;
98 }

View Code