专栏文章

CF467D 题解

MMWL_wma
CF467D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqcrij5
此快照首次捕获于
2025/12/04 02:40
3 个月前
此快照最后确认于
2025/12/04 02:40
3 个月前
查看原文

思路

通过拓扑将含 r 或 R 较少的赋值给含 r 或 R 较多的即可。
然而又环会让拓扑难以完成，故 Tarjan 缩点是最好的方式。

细节

首先，使用 map 将字符串转化为数字，注意第 44 至 2+m2+m 行均要转化。
方便起见，建议大写转小写。
然后缩点。只要对第 22 行中输入的字符串数，及其能转化的字符串进行缩点即可。
存下强连通分量含第 22 行中输入的字符串数 cor⁡\operatorname{cor}，最小含 r 数 mnr⁡\operatorname{mnr}，含 r 最少时最短长度 mnl⁡\operatorname{mnl}。
建边。方便起见，反向建。
拓扑。
由于处于同一强连通分量的两点可互相抵达，故设两答案为 ans1⁡\operatorname{ans_1}，ans2⁡\operatorname{ans_2}，则 ans1⁡=cor⁡×mnr⁡\operatorname{ans_1}=\operatorname{cor}\times \operatorname{mnr} ans2⁡=cor⁡×mnl⁡\operatorname{ans_2}=\operatorname{cor}\times \operatorname{mnl}

代码实现

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,t,c;
map<string,int>mp;
int f[300002];
int cr[300002],cl[300002];
vector<int>e[300002],E[300002];
int dfn[300002],low[300002];
bool vis[300002];
int st[300002],top;
int tot;
int mnr[300002],mnl[300002],cor[300002];
bool in[300002];
void tarjan(int u){
	dfn[u]=low[u]=++c;
	st[++top]=u;
	vis[u]=1;
	for(int v:e[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++tot;
		while(1){
			int t=st[top--];
			vis[t]=0;
			f[t]=tot;
			if(cr[t]<mnr[tot]){
				mnr[tot]=cr[t];
				mnl[tot]=cl[t];
			}else if(cr[t]==mnr[tot]){
				mnl[tot]=min(mnl[tot],cl[t]);
			}
			if(t<=n){
				++cor[tot];
			}
			if(t==u){
				break;
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		cl[i]=s.length();
		for(int j=0;j<cl[i];j++){
			if(s[j]<'a'){
				s[j]+=32;
			}
			if(s[j]=='r'){
				++cr[i];
			}
		}
		mp[s]=++t;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		string x,y;
		cin>>x>>y;
		int lx=x.length(),ly=y.length();
		for(int j=0;j<lx;j++){
			if(x[j]<'a'){
				x[j]+=32;
			}
		}
		for(int j=0;j<ly;j++){
			if(y[j]<'a'){
				y[j]+=32;
			}
		}
		if(!mp[x]){
			mp[x]=++t;
			cl[mp[x]]=lx;
			for(int j=0;j<cl[mp[x]];j++){
				if(x[j]=='r'){
					++cr[mp[x]];
				}
			}
		}
		if(!mp[y]){
			mp[y]=++t;
			cl[mp[y]]=y.length();
			for(int j=0;j<cl[mp[y]];j++){
				if(y[j]=='r'){
					++cr[mp[y]];
				}
			}
		}
		e[mp[x]].push_back(mp[y]);
	}
	memset(mnr,0x3f,sizeof mnr);
	memset(mnl,0x3f,sizeof mnl);
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=t;i++){
		if(f[i]){
			for(auto v:e[i]){
				if(f[i]!=f[v]&&f[v]){
					E[f[v]].push_back(f[i]);
					in[f[i]]=1;
				}
			}
		}
	}
	queue<int>q;
	for(int i=1;i<=tot;i++){
		if(!in[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(auto v:E[t]){
			if(mnr[v]>mnr[t]){
				mnr[v]=mnr[t];
				mnl[v]=mnl[t];
			}else if(mnr[t]==mnr[v]){
				mnl[v]=min(mnl[t],mnl[v]);
			}
		}
	}
	long long ans1=0,ans2=0;
	for(int i=1;i<=tot;i++){
		ans1+=cor[i]*mnr[i];
		ans2+=cor[i]*mnl[i];
	}
	printf("%d %d",ans1,ans2);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...