[ICPC2018 WF] Comma Sprinkler 题解

70CentsApple · 2023-11-16 19:29:24 · 题解

P6942 Comma Sprinkler

思考

因为每个单词需不需要加逗号是可以预先处理出来的，所以可以考虑读入的时候判重，第二次遇到的时候只需要添加第一次添加它时候分配给它的下标。

可以用并查集维护添加逗号的情况：并查集是一种用于管理元素分组的数据结构。它支持两种操作：查找（Find）和合并（Union）。查找操作用于确定元素所属的组，而合并操作用于将两个组合并为一个。 可以看这道 并查集模板题 来学习并查集。

在这个问题中，如果一个单词后面有逗号，那么所有与它右边相邻的单词前面也应该加逗号。这就是并查集可以解决的问题：通过合并操作将属于同一组的符号情况连接在一起。

接下来的部分建议结合代码使用：

记 cnt 为判重后的单词的数量。

comma 数组开两倍的 cnt：奇数代表后面加逗号的情况，偶数代表前面加逗号的情况；

循环遍历两遍输入的每个单词的下标：

• 第一个循环：如果后缀符号是逗号或没有后缀符号，就把当前单词后面的符号和下一个单词前面的符号进行合并（绑成一组）。

  merge(words_idx[i]*2+1, words_idx[i+1]*2);

• 第二个循环：如果后缀符号是逗号，就标记相应集合（这时候已经被第一个循环绑成了一组），表示该位置需要在后面添加逗号。

  comma[find(words_idx[i]*2+1)] = true;

代码

不要直接提交哦 ovo

#include <bits/stdc++.h>
using namespace std;
using ll = l0ng l0ng;
vector<ll> fa;

ll inline find(ll k) {
    return (fa[k] == k )? k : fa[k] = find(fa[k]);
}
void merge(ll x,ll y){
    fa[find(x)] = find(y);
}

int signed main() {
    string str;
    vector<string> unique_words;
    unordered_map<string, int> words_vis;
    vector<int> words_idx;
    vector<char> suffix_arr; // suffix_arr 记录每个单词的后缀
    ll cnt(0); // 储存 **不同** 的单词数目
    while (cin>>str) {
        // 获取后缀
        const char suffix = str[str.size()-1];
        if(suffix == '\r' or suffix == '\n')
            break;
        else if (suffix == '.' or suffix == ',')
            str=str.substr(0,str.size()-1), suffix_arr.emplace_back(suffix);
        else
            suffix_arr.emplace_back('~'); // 随便插入一个后缀占位

        if (words_vis.count(str)) // 已经遇过这个单词
            words_idx.emplace_back(words_vis[str]); // 存放它分配的下标
        else { // 第一次遇到这个单词
            words_idx.emplace_back(cnt);
            words_vis[str] = cnt++; // 分配一个下标
            unique_words.emplace_back(str);
        }
    }
    ll n = suffix_arr.size()-1;
    vector<bool> comma(cnt*2, false);
    fa.resize(cnt*2);
    for (ll i=0; i<cnt*2;i++) fa[i] = i; // 初始化并查集
    for (ll i=0; i<=n-1;i++)
        if (suffix_arr[i] != '.')
            merge(words_idx[i]*2+1, words_idx[i+1]*2);
    for (ll i=0; i<=n-1;i++)
        if (suffix_arr[i] == ',')
            comma[find(words_idx[i]*2+1)] = true;
    for (ll i=0; i<=n; i++) {
        cout << unique_words[words_idx[i]];
        if (suffix_arr[i] == '.') // 句号优先
            cout << '.';
        else if (comma[find(words_idx[i]*2+1)]) // 如果后面应该加逗号
            cout << ',';
        cout << ' ';
    }
    return (0-0);
}