Codeforces 1277D. Let's Play the Words?

编程入门行业动态更新时间:2024-10-08 05:25:10

Codeforces 1277D. Let's Play the Words?

一、内容

题意：给定几个01二进制字符串，问你可以翻转任意的字符串，让所有的字符串能够拼接起来，且所有的串都是惟一的（不重复）。

二、思路

用map记录某个串是否存在，如果存在就进行翻转，如果翻转后还存在那么不合法。
0–0 1—1 这种字符串字节拼接在0—1 或者1—0的前面后面即可，所以我们统计出01,10,11,00开头结尾的字符串的个数，然后分情况讨论
输出-1的情况： 当00,11存在而10,01都不存这那么不可能拼接成功。
输出0的情况：
（1）当00 或者11存在一个，而10,01都不存在。
（2）当01，或者10存在，那么久可以不用管00,11了。通过拼接的规律可以发现当01和10的差值<=1时不用翻转即可拼接成功。 100110 或者011001（那个个数多就以哪个开头）。
输出翻转的情况：
翻转的次数为abs(01个数 - 10个数) / 2，那个串多我们就翻转那个串。翻转的时候还要判断下是否出现重复的。重复的就跳过这个串。最后统计一下翻转的次数，看是否相同，不相同说明还是不合法（因为翻转可能会出现重复）

三、代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath> 
#include <map>
#include <iostream>
using namespace std; 
const int N = 2e5 + 5, M = 4e6 + 5;
struct node {string s;int i;node (string s, int i): s(s), i(i){}
};
int t, n, len, ans, a, b, c, d, path[N];
char s[M];
vector<node> q[2]; //0装01的下标 1装10的下标 
map<string, bool> mp; 
int main() {scanf("%d", &t);while (t--) {q[0].clear(); q[1].clear();mp.clear();ans = a = b = c = d = 0;bool ok = false; scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%s", s);len = strlen(s);if (ok) continue;if (mp[s]) {//再判断翻转后是否相同reverse(s, s + len);if (mp[s]) ok = true;else mp[s] = true; } else {mp[s] = true; } if (s[0] == '0' && s[len - 1] == '1') {q[0].push_back(node(s, i)); a++;			} else if (s[0] == '1' && s[len - 1] == '0') {q[1].push_back(node(s, i)); b++;		} else if (s[0] == '0' && s[len - 1] == '0') {c++; //代表11 00结尾的数量 } else {d++;}} if (c && d && !a && !b) {//代表不合法printf("-1\n"); } else {//统计 01 和 10的差if (((c || d) && !a && !b) || abs(a - b) <= 1) {//代表不用翻转 printf("0\n\n");} else {int cnt = 0; //记录有多少个点输出 ans += abs(a - b) / 2;int t = a > b ? 0 : 1;for (int i = 0; i < q[t].size() && cnt < ans; i++) {string str = q[t][i].s;reverse(str.begin(), str.end());if (!mp[str]) path[++cnt] = q[t][i].i;}if (cnt != ans) {printf("-1\n");} else {printf("%d\n", ans);for (int i = 1; i <= cnt; i++) {printf("%d ", path[i]);}printf("\n");}}}}return 0;
}