Educational Codeforces Round 75 (Rated for Div. 2)

A - Broken Keyboard

题意：键盘一些键坏了，按一下出俩字，给一个串，判断哪些键没坏。

题解：那肯定是至少有一段连续相同字母区间内的个数为奇数的没坏。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

char s[505];

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        vector<char> ans;
        for(int i = 1; i <= n; ++i) {
            int j = i;
            while(j + 1 <= n && s[j + 1] == s[i])
                ++j;
            if((j - i + 1) & 1)
                ans.push_back(s[i]);
            i = j;
        }
        sort(ans.begin(), ans.end());
        ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
        for(auto c : ans)
            printf("%c", c);
        printf("\n");
    }
}

B - Binary Palindromes

题意：给n个01串，可以在串之间任意交换字符，操作次数不限。求能构造的最多有几个回文串。

题解：一个直观的猜测是答案是n或者n-1（把一个串作为垃圾桶存放多出来的（奇数个的）那个位）。假如是全0或者全1就肯定都是回文串，否则，假如是其中的偶数个发生的翻转，全部丢在一个串的两侧翻转即可。假如是奇数个发生翻转，可以把奇数的那次放在某个奇数长度串的中间。

具体来说，设有a个0，b个1，假设a,b都是偶数，那么全部乱丢一通就可以了。假设a,b一奇一偶，那么把奇的那次丢给一定会出现至少一个的奇数串就可以了。假如a,b两个奇数，那么就判断有多少个奇数串，有两个以上奇数串就n，否则n-1（没有奇数串，必须破坏一个偶数串）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

char s[55];

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        int a = 0, b = 0, c = 0;
        for(int j = 1; j <= n; ++j) {
            scanf("%s", s + 1);
            int l = strlen(s + 1);
            c += l & 1;
            for(int i = 1; i <= l; ++i) {
                if(s[i] == '0')
                    ++a;
                else
                    ++b;
            }
        }
        printf("%d\n", n - ((a & 1) && (b & 1) && (c == 0)));
    }
}

Educational Codeforces Round 75 (Rated for Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/11823903.html