自动搬运

查看原文

来自洛谷，原作者为

	70CentsApple 不会 不懂 不知道 70centsapple.top

搬运于2025-08-24 22:25:20，当前版本为作者最后更新于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);
}