NC25223. Modify
描述
MINIEYE's engineer M wrote an article, but he is not satisfied with what he has written. He thinks there are too many vowels (a、e、i、o、u), making it not gentle enough. It's not concise enough, either.
M needs your help to polish his article.
There are n words in M's article and each word consists of lowercase letters only. M offers k rules of how to modify the article, each rule means that one word can be replaced by another word and you can use the rules any times. For example, there's a word ‘hello’ in M's article, and there's a rule to replace ‘hello’ with ‘hi’, and a rule to replace ‘hi’ with ‘hey’, then you can use both rules to finally replace ‘hello’ with ‘hey’.
M hopes he’s article to have as few vowels as possible; and if there are multiple ways to obtain the minimum number of vowels, you also need to make the total length of the article as short as possible.
输入描述
The first line contains a single integer n(1 ≤ n ≤ 105), the number of words inthe article. The second line contains words of the article, separated by asingle space. It is guaranteed that the total length of the words won't exceed 105 characters.
The next line contains a single integer k(1 ≤ k ≤ 105), the number of thetransform rules. The ith of the next k lines contains two space-separatednon-empty words Si and Ti. It means that word Si can be changed to word Ti (but not vice versa).
It is guaranteed that thetotal length of all transform rules doesn't exceed 5 × 105 characters.
输出描述
Two numbers in the first line, X and Y, indicate the minimum vowels number and the minimum length when the vowels number is minimum.
示例1
输入:
3 xxaeiou xxu zza 6 xxu aaa aaa zza zza xxu aaa xxx xxaeiou iiiiiiii xxaeiou aeiou
输出:
5 11
C++11(clang++ 3.9) 解法, 执行用时: 548ms, 内存消耗: 42340K, 提交时间: 2019-04-22 18:44:02
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[2 * maxn], cnt;
string s[maxn];
struct Node{ int val, len; }node[2 * maxn];
bool cmp(const int &a, const int &b) {return node[a].val == node[b].val ? node[a].len < node[b].len : node[a].val < node[b].val; }
int cal(string a)
{
int res = 0;
for(int i = 0; i < a.length();i++)
if(a[i] == 'a' || a[i] =='e' || a[i] == 'i' || a[i] == 'o' || a[i] == 'u') res++;
return res;
}
map<string, int> mp;
void add(string x)
{
if(mp.count(x)) return;
node[cnt].val = cal(x);
node[cnt].len = x.length();
mp[x] = cnt++;
}
vector<int> edge[2 * maxn];
bool vis[2 * maxn];
void BFS(int st)
{
queue<int> que;
que.push(st);
while(!que.empty())
{
int u = que.front();
que.pop();
vis[u] = true;
node[u].val = node[st].val;
node[u].len = node[st].len;
for(auto & v :edge[u]) if(!vis[v]) que.push(v);
}
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> s[i];
add(s[i]);
}
cin >> m;
string x, y;
while(m--)
{
cin >> x >> y;
add(x), add(y);
edge[mp[y]].push_back(mp[x]);
}
for(int i = 0; i < cnt; i++) a[i] = i;
sort(a, a + cnt, cmp);
for(int i = 0; i < cnt; i++) if(!vis[a[i]]) BFS(a[i]);
long long res1 = 0, res2 = 0;
for(int i = 0; i < n; i++) res1 += node[mp[s[i]]].val, res2 += node[mp[s[i]]].len;
cout << res1 << ' ' << res2 <<endl;
return 0;
}