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

A. Common Subsequence

显然，找一个两者都有的数即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int vis[N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int a, b;
        for (int i = 1; i <= 1000; i++) vis[i] = 0;
        scanf("%d%d", &a, &b);
        for (int i = 1, x; i <= a; i++) scanf("%d", &x), vis[x] = 1;
        int flag = 0;
        for (int i = 1, x; i <= b; i++) {
            scanf("%d", &x);
            if (vis[x] == 1 && flag == 0) {
                printf("YES\n1 %d\n", x);
                flag = 1;
            }
        }
        if (flag == 0) printf("NO\n");
        // to:;
    }
    return 0;
}

B. Sequential Nim

对于某一堆石子，它影响后来决策的只有谁拿走了里面的最后一个石子，而至于两人怎么拿的，这不重要。
注意到如果这一堆石子只有一个，那么只能面临这个局面的人拿走所有石子，否则这个人可以选择是谁拿走它。根据这个思考可以写一个$O(n)$的$DP$。

include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
int sg[N][2], a[N], n;
int SG(int x, int y)
{
    if (x == n) return 1;
    if (~sg[x][y]) return sg[x][y];
    if (y == 1) return sg[x][y] = !SG(x + 1, a[x + 1] == 1);
    return sg[x][y] = (SG(x, 1) == 0 || SG(x + 1, a[x + 1] == 1) == 0);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", a + i), sg[i][0] = sg[i][1] = -1;
        int ans = SG(1, a[1] == 1);
        // for (int i = 1; i <= n; i++) cout << SG(i, 0) << " " << SG(i, 1) << endl;
        if (ans) {
            printf("First\n");
        } else {
            printf("Second\n");
        }
    }
    return 0;

C. Prefix Flip

        对于简单版本可以暴力$O(n^2)$。
        困难版本主要是翻转不好处理，头铁的话可以上平衡树解决这个问题。
        事实上有一个优雅的构造解可以避免翻转。我们将第一个串变为全$0$或者全$1$的形式，这样进行$n$次操作，并且可以忽略翻转，然后再考虑将第二个串也变成这样，由于操作是可逆的，所以方法可行。这个构造性解法的巧妙之处在于它也满足了$2n$的限制，但是同时可以忽略翻转操作。
        下面给出一个平衡树的无脑代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
typedef long long ll;
char a[N], b[N], tmp[N];
int n, cnt, root;
vector<int> ans;
struct Node
{
    int l, r, v, key, ctag, rtag, num;
} nd[N];
inline int newNode(int x)
{
    nd[cnt].num = 1, nd[cnt].l = nd[cnt].r = nd[cnt].ctag = nd[cnt].rtag = 0;
    nd[cnt].v = x, nd[cnt].key = rand();
    return cnt++;
}
inline void update(int x)
{
    nd[x].num = nd[nd[x].l].num + nd[nd[x].r].num + 1;
}
inline void pud(int x)
{
    if (nd[x].ctag) {
        nd[nd[x].l].v ^= 1, nd[nd[x].r].v ^= 1, nd[nd[x].l].ctag ^= 1, nd[nd[x].r].ctag ^= 1;
        nd[x].ctag = 0;
    }
    if (nd[x].rtag) {
        nd[nd[x].l].rtag ^= 1, swap(nd[nd[x].l].l, nd[nd[x].l].r);
        nd[nd[x].r].rtag ^= 1, swap(nd[nd[x].r].l, nd[nd[x].r].r);
        nd[x].rtag = 0;
    }
}
void split(int rt, int& a, int& b, int v)
{
    if (rt == 0) {
        a = b = 0;
        return;
    }
    pud(rt);
    if (nd[nd[rt].l].num < v)
        a = rt, split(nd[rt].r, nd[a].r, b, v - nd[nd[rt].l].num - 1);
    else
        b = rt, split(nd[rt].l, a, nd[b].l, v);
    update(rt);
}
void merge(int& rt, int a, int b)
{
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    pud(a), pud(b);
    if (nd[a].key > nd[b].key)
        rt = a, merge(nd[rt].r, nd[a].r, b);
    else
        rt = b, merge(nd[rt].l, a, nd[b].l);
    update(rt);
}
inline void solve(int x)
{
    int a, b;
    split(root, a, b, x);
    // cout << nd[a].v << endl;
    nd[a].v ^= 1, nd[a].ctag ^= 1, swap(nd[a].l, nd[a].r), nd[a].rtag ^= 1;
    merge(root, a, b);
}
inline int get(int x)
{
    int a, b, c, ans;
    split(root, a, c, x), split(a, a, b, x - 1);
    ans = nd[b].v;
    merge(a, a, b), merge(root, a, c);
    // cout << x << " " << ans << endl;
    return ans;
}
 
int main()
{
    srand(time(0));
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%s%s", &n, a + 1, b + 1);
        ans.clear(), cnt = 1, root = 0;
        for (int i = 1; i <= n; i++) {
            merge(root, root, newNode(a[i] - '0'));
        }
        for (int i = n; i >= 1; i--) {
            if (get(i) + '0' == b[i]) continue;
            if (i == 1) {
                ans.push_back(1);
                solve(1);
                continue;
            }
            if (get(1) + '0' != b[i]) {
                ans.push_back(i);
                solve(i);
                continue;
            }
            ans.push_back(1), solve(1);
            ans.push_back(i), solve(i);
            // DFS(root);
            // cout << endl;
        }
        printf("%d", ans.size());
        for (int i : ans) printf(" %d", i);
        printf("\n");
    }
    return 0;
}

D. Unmerge

        注意到如果数$x$在序列$A$中，那么它之后的一系列满足$y < x$的$y$都应该在序列$A$中，否则它会在序列$B$中，这样由于$y < x$，$y$会出现在$x$前面。
        根据以上思考，我们可以从第一位开始，找它后面第一个比它大的数，然后继续向后找，将序列划分为若干个段。
        显然，两个序列都必须由这些段组成的，现在问题转化为给定若干个数，问它们能不能找出其中一些数，相加得到$n$，这是一个经典的$01$背包问题，然后跑一个背包本题就解决了。

#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int p[N], n, dp[N];
vector<int> vec;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        vec.clear(), vec.push_back(0);
        scanf("%d", &n);
        for (int i = 1; i <= (n << 1); i++) scanf("%d", p + i);
        for (int i = 1; i <= (n << 1);) {
            int r = i;
            while (r + 1 <= (n << 1) && p[r + 1] < p[i]) ++r;
            vec.push_back(r - i + 1), i = r + 1;
        }
        for (int i = 0; i <= n; i++) dp[i] = 0;
        for (int i = 1; i < vec.size(); i++) {
            for (int j = n; j >= 0; j--) {
                if (j >= vec[i]) dp[j] = max(dp[j], dp[j - vec[i]] + vec[i]);
            }
        }
        printf("%s\n", dp[n] == n ? "YES" : "NO");
    }
    return 0;
}

E. Mastermind

先考虑这样一个问题：给定一个序列，将其打乱，可以得到的最小匹配数为多少？（第$i$位匹配当且仅当打乱后这一位和之前相同）。
容易发现这个最小匹配数就是$2f-n$，其中$f$是里面出现最多的数出现的次数，$n$是序列长度。这个最小匹配的方案可以通过如下的方法构造性地得到：

对序列重新标号，使得相同的数总是相邻的。
将序列旋转$\lfloor\frac {n}{2}\rfloor$。

        有了上面的思考后，就可以解决本题。
        首先需要找$x$个完全匹配的位，这样会剩下$n-x$位，我们将它们按照上面的思路进行乱序，使得匹配数最少。为了使匹配数最小，我们应该最小化出现最多颜色的数量，于是这里贪心地每次都选出现次数最多的颜色的某一位。这一步可以通过记录每一位在它对应颜色中的排名，排序后完成。
        对于乱序后仍然匹配的位，它们本不应该出现，于是我们需要将这一位换掉。由于颜色有$n+1$个，所以我们可以选一个没有出现的颜色$s$，来替换掉当前的颜色。但是这里需要注意替换的次数不能超过$n-y$，否则就是无解的。
        剩下的都是不能匹配的部分，此时如果$n-y$的次数还没有用完，就将它们对应的部分也换成$s$。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
int b[N], n, x, y, c[N], ans[N];
vector<pair<int, int>> vec;
vector<int> tmp;
int cmp(int x, int y)
{
    return b[x] < b[y];
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int other;
        scanf("%d%d%d", &n, &x, &y), vec.clear();
        for (int i = 1; i <= n + 1; i++) c[i] = 0, ans[i] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", b + i);
            vec.push_back({++c[b[i]], i});
        }
        for (int i = 1; i <= n + 1; i++) {
            if (c[i] == 0) {
                other = i;
                break;
            }
        }
        sort(vec.begin(), vec.end(), greater<pair<int, int>>());
        for (int i = 0; i < x; i++) ans[vec[i].second] = b[vec[i].second];
        tmp.clear();
        for (int i = 1; i <= n; i++) {
            if (ans[i] == 0) tmp.push_back(i);
        }
        sort(tmp.begin(), tmp.end(), cmp);
        int len = (n - x) >> 1, remain = n - y, sz = tmp.size();
        for (int i = 0; i < sz; i++) tmp.push_back(tmp[i]);
        for (int i = 0, j = len; i < sz; i++, j++) {
            if (b[tmp[i]] != b[tmp[j]]) {
                ans[tmp[i]] = -b[tmp[j]];
            } else if (remain) {
                ans[tmp[i]] = other, --remain;
            } else {
                printf("NO\n");
                goto tag;
            }
        }
        for (int i = 1; i <= n && remain; i++) {
            if (ans[i] < 0) ans[i] = other, --remain;
        }
        for (int i = 1; i <= n; i++) {
            if (ans[i] < 0) ans[i] = -ans[i];
        }
        printf("YES\n");
        for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
        printf("\n");
    tag:;
    }
    return 0;
}