Codeforces —— Let's Play the Words?(1277D)

input

output

题意

给定n个二进制串的集合，要求从第二个串开始每一个串的开头第一个字母必须是上一个
二进制的结尾字符，你可以翻转这n个字符串（翻转后不能出现相同字符），问操作数最
少的情况下翻转那些字符串，使得这n和字符进行排列后可以满足条件

思路

记录zz = 0...0, oo = 1...1, oz = 1...0, zo = 0...1字符串的数量
若!zo && !oz那么：
      若!zz || !oo则以及满足条件
      其他一定不能满足条件
最少操作次数为abs(zo-oz)/2, 每次将多出来的zo或者oz输出即可

代码

#pragma GCC optimize(2)
#include<unordered_map>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define Buff ios::sync_with_stdio(false)
#define rush() int Case = 0; int T; cin >> T;  while(T--)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define per(i, a, b) for(int i = a; i >= b; i --)
#define reps(i, a, b) for(int i = a; b; i ++)
#define clc(a, b) memset(a, b, sizeof(a))
#define Buff ios::sync_with_stdio(false)
#define readl(a) scanf("%lld", &a)
#define readd(a) scanf("%lf", &a)
#define readc(a) scanf("%c", &a)
#define reads(a) scanf("%s", a)
#define read(a) scanf("%d", &a)
#define lowbit(n) (n&(-n))
#define pb push_back
#define sqr(x) x*x
#define rs x<<1|1
#define y second
#define ls x<<1
#define x first
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>PII;
const int mod = 1e9+7;
const double eps = 1e-6;
const int N = 2e5+7;
string s[N];

int main()
{
    rush()
    {
        int n;
        cin >> n;
        set<string> seen, bad;
        int oz = 0, zo = 0, zz = 0, oo = 0;
        rep(i, 0, n-1)
        {
            cin >> s[i];
            string rev(s[i].rbegin(), s[i].rend());
            if(s[i][0] == '0' && s[i].back() == '1')    
            {
                zo ++;
                if(seen.count(rev))
                    bad.insert(s[i]), bad.insert(rev);
                seen.insert(s[i]);
            }
            else if(s[i][0] == '1' && s[i].back() == '0')
            {
                oz ++;
                if(seen.count(rev))
                    bad.insert(rev), bad.insert(s[i]);
                seen.insert(s[i]);
            }
            else if(s[i][0] == '0' && s[i].back() == '0')   zz ++;
            else                                            oo ++;
        }
        if(!zo && !oz)
        {
            if(!oo || !zz)  cout << 0 <<"

";
            else            cout << -1 <<endl;
        }
        else
        {
            int res = abs(oz-zo)/2;
            cout << res <<endl;
            rep(i, 0, n-1)
            {
                if(!res)    break;
                if(zo > oz && s[i][0] == '0' && s[i].back() == '1' && !bad.count(s[i]))
                    {cout << i + 1 <<" ";   res --;}
                if(oz > zo && s[i][0] == '1' && s[i].back() == '0' && !bad.count(s[i]))
                    {cout << i + 1 <<" ";   res --;}
            }
            cout << endl;
        }
        
    }
	return 0;
}