Codeforces Round #267 (Div. 2)
CF#267D
|
D. Fedor and Essay
time limit per test
2 seconds memory limit per test
256 megabytes input
standard input output
standard output After you had helped Fedor to find friends in the «Call of Soldiers 3» game, he stopped studying completely. Today, the English teacher told him to prepare an essay. Fedor didn't want to prepare the essay, so he asked Alex for help. Alex came to help and wrote the essay for Fedor. But Fedor didn't like the essay at all. Now Fedor is going to change the essay using the synonym dictionary of the English language. Fedor does not want to change the meaning of the essay. So the only change he would do: change a word from essay to one of its synonyms, basing on a replacement rule from the dictionary. Fedor may perform this operation any number of times. As a result, Fedor wants to get an essay which contains as little letters «R» (the case doesn't matter) as possible. If there are multiple essays with minimum number of «R»s he wants to get the one with minimum length (length of essay is the sum of the lengths of all the words in it). Help Fedor get the required essay. Please note that in this problem the case of letters doesn't matter. For example, if the synonym dictionary says that word cat can be replaced with word DOG, then it is allowed to replace the word Cat with the word doG. Input
The first line contains a single integer m (1 ≤ m ≤ 105) — the number of words in the initial essay. The second line contains words of the essay. The words are separated by a single space. It is guaranteed that the total length of the words won't exceed 105 characters. The next line contains a single integer n (0 ≤ n ≤ 105) — the number of pairs of words in synonym dictionary. The i-th of the next n lines contains two space-separated non-empty words xi and yi. They mean that word xi can be replaced with word yi (but not vise versa). It is guaranteed that the total length of all pairs of synonyms doesn't exceed 5·105 characters. All the words at input can only consist of uppercase and lowercase letters of the English alphabet. Output
Print two integers — the minimum number of letters «R» in an optimal essay and the minimum length of an optimal essay. Sample test(s)
Input
3 Output
2 6 Input
2 Output
1 10 |
题意：
给出m个单词，表示原文章。给出由n组单词组成的同义词字典，每组单词表示左边的可以换成右边的（单向）。（大小写均不敏感）。可以对原文章的各个单词进行若干次换，最后要得到字母“r”最少。若字母r数量相同，则要求总长度最短的（总长度为各个单词的长度和）。输出最后字母r的数量和总长度。
题解：
STLmap+建图+dfs
思路是把一个词向r尽量少、r相同的话长度尽量少的词变，于是可以对字典建个图，将能到达r最少的长度最短的点x的点全部标为换为x。
利用map将字典中的词与图中的点对应，将一组词的右边词向左边词连一条边（表示右边词有一条来自左边词的入边）。
将点按要求排序（r少的在前面，r相同的话长度小的在前面）。
然后依次对排序后的点进行dfs，所经之点的to[x]全部标为这次dfs的起点aim，只经过to[x]还没确定的点。
最后对原文章进行搞，如果原文章的某个词在字典里，就把它变成to[x]指向的词；否则不能换。
注意因为替换操作，会超int……
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back
const double eps=1e-;
const double pi=acos(-1.0); const int maxn=;
const int maxm=maxn; struct Edge {
int v,next;
} e[maxm];
int en=;
int head[maxn]; void add(int x,int y) {
e[en].v=y;
e[en].next=head[x];
head[x]=en++;
} struct Node {
int r,len,no;
};
bool operator<(const Node &x,const Node &y) {
if(x.r<y.r)return ;
if(x.r>y.r)return ;
return x.len<y.len;
} int to[maxn];
int aim;
void dfs(int x){
to[x]=aim;
for(int i=head[x];i!=-;i=e[i].next){
if(to[e[i].v]==) dfs(e[i].v);
}
} int m,n;
string s[];
map<string,int>S;
Node a[maxn];
int cnt=;
int main() {
int i,j,k;
string x[];
mf1(head);
en=;
cin>>m;
REP(i,m)cin>>s[i];
cin>>n;
REP(i,n) {
cin>>x[]>>x[];
REP(j,) {
transform(x[j].begin(), x[j].end(), x[j].begin(), ::tolower);
if(S[x[j]]==) {
S[x[j]]=++cnt;
int t=;
int size=x[j].size();
REP(k,size)if(x[j][k]=='r')t++;
a[cnt].r=t;
a[cnt].len=size;
a[cnt].no=cnt;
}
} add(S[x[]],S[x[]]);
}
sort(a+,a+cnt+);
mz(to);
FOR(i,,cnt){
if(to[a[i].no])continue;
aim=i;
dfs(a[i].no);
}
ll ans1=,ans2=;
REP(i,m){
transform(s[i].begin(), s[i].end(), s[i].begin(), ::tolower);
int x=S[s[i]];
if(x== || to[x]==){
int t=;
int size=s[i].length();
REP(k,size)if(s[i][k]=='r')t++;
ans1+=t;
ans2+=size;
}else{
ans1+=a[to[x]].r;
ans2+=a[to[x]].len;
}
//cout<<s[i]<<endl;
//printf("%d %d %d %d %d\n",i,x,to[x],ans1,ans2);
}
printf("%I64d %I64d\n",ans1,ans2);
return ;
}