Codeforces Round #616 (Div. 2)lyh's blog

Codeforces Round #616 (Div. 2)题解。脑子是个好东西。

A. Even But Not Even

容易发现删去偶数对数位和的奇偶性没有影响，于是我们删末尾的偶数只剩下一个奇数，然后再删一些其它的奇数调一调即可。不能调就是无解。纯拼手速题。

#include <bits/stdc++.h>
using namespace std;
char op[3005];
int n, t;
int main()
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%s", &n, op + 1);
        int j = 0, last = n;
        for (int i = 1; i <= n; i++) {
            if ((op[i] - '0') & 1) ++j;
        }
        while (last >= 1 && op[last] % 2 == 0) --last;
        if (last == 0 || j == 1) {
            printf("-1\n");
        }
        else if (j % 2) {
            --last;
            while (last >= 1 && op[last] % 2 == 0) --last;
            for (int i = 1; i <= last; i++) printf("%c", op[i]);
            printf("\n");
        }
        else {
            for (int i = 1; i <= last; i++) printf("%c", op[i]);
            printf("\n");
        }
    }
    return 0;
}

B. Array Sharpening

可以发现如果正着能够化成符合题意的形式，那么一定可以化成：0、1、2……这样的形式（暂且称为最小形式）。反过来同理，这样我们只需要比较给定数组与最小形式的关系，然后枚举转折点即可解决。

#include <bits/stdc++.h>
using namespace std;
int op[300005], n, l[300005], r[300005];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", op + i);
        l[0] = 1, r[n + 1] = 1;
        for (int i = 1; i <= n; i++) l[i] = l[i - 1] && (op[i] >= (i - 1));
        for (int i = n; i >= 1; i--) r[i] = r[i + 1] && (op[i] >= (n - i));
        for (int i = 1; i <= n; i++) {
            if (l[i] && r[i]) {
                printf("Yes\n");
                goto to;
            }
        }
        printf("No\n");
    to:;
    }
    return 0;
}

C. Mind Control

一道怡情的贪心。这个肯定是把前面$k$个人蛊惑了比较好。这样会留下我们想要的$n-k$这么大的一块区间。
但是如果$k+1$到自己之间还有别人，这些人没有办法蛊惑，所以我们可以拿到的数是不确定的，但是可以肯定的是，它们必然是从一个间距固定的数对中取得的，并且取最大的。于是问题转化为求最大值的最小值，枚举即可。

#include <bits/stdc++.h>
using namespace std;
int n, m, k, op[3600], sv[3600];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i++) scanf("%d", op + i);
        int c = min(m - 1, k), len = n - m + 1;
        for (int i = 1; i <= n + 1 - len; i++) sv[i] = max(op[i], op[i + len - 1]);
        int ans = 0;
        for (int i = 1; i <= c + 1; i++) {
            int p = 0x3f3f3f3f;
            for (int j = i; j + len - 1 <= i + n - c - 1 && j <= n + 1 - len; j++) p = min(p, sv[j]);
            ans = max(ans, p);
        }
        printf("%d\n", ans);
    }
    // PAUSE;
    return 0;
}

D. Irreducible Anagrams

只需要知道：一个串不存在符合题意的irreducible anagram的充要条件是它满足下面性质的一条：

长度为1
首末字符不同
至少由三个不同字符组成

证明脑补吧。
然后就没什么可说的了。是个结论题（智商题）。

#include <bits/stdc++.h>
using namespace std;
char op[200005];
int sum[200005][30], len;
int main()
{
    scanf("%s", op + 1), len = strlen(op + 1);
    for (int i = 1; i <= len; i++) {
        for (int j = 0; j < 26; j++) sum[i][j] = sum[i - 1][j] + (op[i] - 'a' == j);
    }
    int q, l, r;
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d", &l, &r);
        int cnt = 0;
        for (int i = 0; i < 26; i++) {
            if (sum[r][i] - sum[l - 1][i] > 0) ++cnt;
        }
        if (l == r || op[l] != op[r] || cnt >= 3)
            printf("Yes\n");
        else
            printf("No\n");
    }
    // PAUSE;
    return 0;
}

E. Prefix Enlightenment

        这个题出的很好，强烈建议一做。
        任意三个集合交集为空说明任何一个元素最多出现在两个集合中。我们把元素看成边，集合看成点，这样给定的若干集合可以构成一个图。
        对于只出现在一个集合中的元素，我们构造一个假象的集合（成为集合$S_0$），使其包含该元素，进而建图。
        我们给每一个集合一个状态，该状态只能为0和1，表示这个集合选不选。
        容易发现，如果某个元素原本为0，那么必须有恰好一个集合包含它，这样该元素对应边的两个点状态互异。同样地，如果某个元素原本为1，那么该元素对应边的两个点状态相同。如果这个元素没有对应边，那么忽略就好了。
        这样就得到了一些限制条件，问题转化为在给定的连通块状态限制条件下，最小化被选点的数量。这可以用加权并查集优雅地解决。
        定义并查集中的点权为与父节点的关系（1为互异，0为相同），然后上路径压缩更新点权。本题的难点在于并查集合并函数的实现，在合并两个连通块时，要更新连通块大小以及互异的点数，连带着更新答案。
        还有一个坑点：我们构造的$S_0$集合是不可选的，在计算最小答案时，要注意$S_0$的状态不可改变。
        本题实现起来细节较多。

#include <bits/stdc++.h>
#define N 300005
using namespace std;
char op[N];
int n, k, fa[N], v[N], num[N], sz[N], ans, gx[N];
vector<int> vec[N];
int ff(int x)
{
    if (fa[x] == x) return x;
    int f = ff(fa[x]);
    v[x] ^= v[fa[x]];
    return fa[x] = f;
}
inline void merge(int x, int y, int p)
{
    if (ff(x) == ff(y)) return;
    int fx = ff(x), fy = ff(y);
    if (fx == 0) swap(fx, fy);
    v[fx] = p ^ v[x] ^ v[y];
    sz[fy] += sz[fx];
    num[fy] += v[fx] ? sz[fx] - num[fx] : num[fx];
    ans -= gx[fy] + gx[fx];
    if (fy == 0)
        gx[fy] = num[fy];
    else
        gx[fy] = min(sz[fy] - num[fy], num[fy]);
    ans += gx[fy], fa[fx] = fy;
}
int main()
{
    scanf("%d%d%s", &n, &k, op + 1);
    for (int i = 0; i <= k; i++) fa[i] = i, sz[i] = 1;
    for (int i = 1, c, x; i <= k; i++) {
        scanf("%d", &c);
        while (c--) scanf("%d", &x), vec[x].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (vec[i].size() == 1) vec[i].push_back(0);
    }
    for (int i = 1; i <= n; i++) {
        if (!vec[i].empty()) merge(vec[i][0], vec[i][1], op[i] == '0');
        printf("%d\n", ans);
    }
    return 0;
}

F. Coffee Varieties

        暂且只说easy版的。
        将$k$减半（如果$k$是1，就不用减了）。这样可以把整个区间划分为$\frac {2n}{k}$块，我们枚举这些块中的每一对，$reset$一次然后遍历，删去那些回答为$Y$的部分。可以证明每一个重复的都会用这种方法被删去。
        一共询问的次数：

$\frac {(\frac {2n}{k})(\frac {2n}{k}-1)}{2}k=\frac {2n^2}{k}-n$

最后数一数哪些没被删即可。

#include <bits/stdc++.h>
using namespace std;
int vis[5000], n, k, p;
char e;
int main()
{
    cin >> n >> k;
    p = k == 1 ? 1 : k >> 1;
    for (int i = 1; i <= n / p; i++) {
        for (int j = i + 1; j <= n / p; j++) {
            cout << "R" << endl;
            for (int z = 1 + (i - 1) * p; z <= i * p; z++) {
                cout << "? " << z << endl;
                cin >> e;
                if (e == 'Y') vis[z] = 1;
            }
            for (int z = 1 + (j - 1) * p; z <= j * p; z++) {
                cout << "? " << z << endl;
                cin >> e;
                if (e == 'Y') vis[z] = 1;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) ++ans;
    }
    cout << "! " << ans << endl;
    // PAUSE;
    return 0;
}