Codeforces_467D

_5W1H_ · 2023-10-22 14:35:54 · 题解

题意

给你一个字符串，里面有 n 个单词，每个单词可以被替换为另一个词（改变是单向的!!!），其中要使得替换后 R 和 r 在单词中的出现数量尽可能少，在 R 和 r 尽可能少的情况下使得最后所有单词长度之和最小。

思路

一开始将大写全部改成小写，利用 map 记录每个单词的编号，再 tarjan 把单词缩一下，因为如果单词太多，会不太好做，缩成 Dag 后会简便很多，缩的时候要记得对于每个连通分量记录 r 的最少个数以及单词的最短的长度，最后进行一次拓扑排序求出答案，如果不会 tarjan，请前往 P3387 学习，最后输出即可。

代码

#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int N = 500010;

//答案
int res_l[N];
int res_r[N];

int idx;
int hr[N];
string a[N];
vector<int> P[N];
map<string, int> id;
vector<int> graph[N];
map<int, string> idxt;

//tarjan
bool in_stk[N];
int scc_cnt, top, timestamp;
int dfn[N], low[N], stk[N], idt[N], in[N];

//将大写改成小写
void do_(string& s)
{
    for (int i = 0; i < s.size(); i ++ )
        if ('A' <= s[i] && s[i] <= 'Z') s[i] = (char)(s[i] - 'A' + 'a');
}

//统计r的个数
void do__(string s)
{
    for (int i = 0; i < s.size(); i ++ )
        if (s[i] == 'r') hr[id[s]] ++ ;
}

//tarjan
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int j : graph[u])
    {
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            idt[y] = scc_cnt;
            if (res_r[scc_cnt] == hr[y]) 
                res_l[scc_cnt] = min(res_l[scc_cnt], (int)(idxt[y].size()));
            if (res_r[scc_cnt] > hr[y]) 
            {
                res_r[scc_cnt] = hr[y];
                res_l[scc_cnt] = idxt[y].size();
            }
        } while (y != u);
    }
}

signed main()
{
    memset(res_l, 0x3f, sizeof res_l);
    memset(res_r, 0x3f, sizeof res_r);

    int n;
    cin >> n;

    //输入处理
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i]; do_(a[i]);
        if (id[a[i]] == 0) id[a[i]] = ++ idx, do__(a[i]), idxt[idx] = a[i];
    }

    int T;
    cin >> T;

    while (T -- )
    {
        string s, t;
        cin >> s >> t;
        do_(s), do_(t);
        if (id[s] == 0) id[s] = ++ idx, do__(s), idxt[idx] = s;
        if (id[t] == 0) id[t] = ++ idx, do__(t), idxt[idx] = t;
        graph[id[s]].push_back(id[t]);
    }

    for (int i = 1; i <= idx; i ++ )
        if (!dfn[i]) tarjan(i);

    //缩点
    for (int i = 1; i <= idx; i ++ )
        for (int j = 0; j < graph[i].size(); j ++ )
            if (idt[graph[i][j]] != idt[i])
                P[idt[graph[i][j]]].push_back(idt[i]), in[idt[i]] ++ ;

    queue<int> q;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!in[i]) q.push(i);

   //拓扑序
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : P[u])
        {
            in[v] -- ;
            if (res_r[v] == res_r[u]) res_l[v] = min(res_l[v], res_l[u]);
            if (res_r[v] > res_r[u]) res_r[v] = res_r[u], res_l[v] = res_l[u];
            if (!in[v]) q.push(v);
        }
    }

    int res_len = 0, res_rs = 0;
    for (int i = 1; i <= n; i ++ )
        res_len += res_l[idt[id[a[i]]]], res_rs += res_r[idt[id[a[i]]]];

    cout << res_rs << " " << res_len;

    return 0;
}