Yifan and Yifan

Yifan Zhao 和 Yifan Bao 的训练题集.....

第一场

\(A.\) Making Anti-Palindromes

首先如果出现最多的数次数超过一半，显然是无解的。

如果是奇数也必然无解。

否则， 考虑一共有多少对 \(S_{i} = S_{n - i + 1}\) 以及满足这个性质的最多的字母是什么。如果超过了一半， 那么把那个字母全部换掉就行。 否则两两配对。

时间复杂度 \(O(N)\)

\(B\). The Third Letter

带权并查集。每次看一看两个点是否被并起来了，如果否就合并两个点。 否则检查两个点之间的树上权值和是否恰好为 \(D\)

时间复杂度 \(O(MlogN)\)

\(C\). Imbalanced Arrays

考虑绝对值最大那个数

如果这个数是正数， 那么它的 \(a\) 值必然为 \(n\)， 否则为 \(0\)

考虑如何把规模为 \(n\) 的问题转化为规模 \(n - 1\) 的问题

如果绝对值最大的是正数， 那么把所有 \(a\) 值减一，并将该数删去

如果是负数， 那么直接把该数删去

递归地做就行了， 具体实现时维护两个指针即可。

时间复杂度 \(O(N)\)

\(D.\) Professor Higashikata

先考虑不带修改怎么做

显然希望尽可能将前面的字符都填 \(1\)

不难统计出字符串中 \(1\) 的个数 \(K\)。

找出一个最大的前缀区间并， 满足并的大小尽可能接近 \(K\)

把这个并中所有的 \(0\) 换成 \(1\) 即为交换的次数

问题是怎么高效实现上述算法？

先求出字符串每个位置最早被哪个区间覆盖， 这可以用 \(set\) / 链表 / 线段树轻松做到。

用树状数组维护区间并中 \(0\) 的个数， 具体实现比较繁琐

时间复杂度 \(O(QlogM)\)

贴一下代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MN = 2e5 + 5;

int N, M, Q, CNT[MN], val[MN], A[MN], l[MN], r[MN];
char S[MN];
vector < int > ins[MN], del[MN], foo[MN];

struct Fenwick {
    unordered_map< int, int > mp;
    inline void clr() {
        mp.clear();
    }
    inline void add(int x, int val) {
        for (int i = x; i <= N; i += i & -i) mp[i] += val;
        return;
    }
    inline int query(int x) {
        int ret = 0;
        for (int i = x; i; i -= i & -i) ret += mp[i];
        return ret;
    }
} fen, bit[MN];

int main() {

    scanf("%d%d%d%s", &N, &M, &Q, S + 1); int TOT = 0;
    for (int i = 1; i <= N; ++i) A[i] = S[i] - '0';
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d", &l[i], &r[i]);
        ins[l[i]].emplace_back(i);
        del[r[i] + 1].emplace_back(i);
    }
    set < int > s; s.clear();
    for (int i = 1; i <= N; ++i) {
        for (int x : ins[i]) s.insert(x);
        for (int x : del[i]) s.erase(x);
        if (s.size()) val[i] = *s.begin();
        else val[i] = -1;
    }
    for (int i = 1; i <= N; ++i) if (~val[i]) ++CNT[val[i]];
    for (int i = 1; i <= M; ++i) CNT[i] += CNT[i - 1];
    fen.clr();
    for (int i = 1; i <= N; ++i) bit[i].clr();
    for (int i = 1; i <= N; ++i) 
        if (!A[i]) {
            if (~val[i]) 
                fen.add(val[i], 1);
        } else ++TOT;
    for (int i = 1; i <= N; ++i) {
        if (val[i] == -1) continue;
        foo[val[i]].emplace_back(i);
        if (!A[i]) bit[val[i]].add(i, 1);
    }
    while (Q--) {
        int x; scanf("%d", &x);
        if (A[x]) {
            --TOT; 
            if (~val[x]) fen.add(val[x], 1);
            if (~val[x]) bit[val[x]].add(x, 1);
        } else {
            ++TOT;
            if (~val[x]) fen.add(val[x], -1);
            if (~val[x]) bit[val[x]].add(x, -1);
        }
        A[x] ^= 1;
        int l = 1, r = M, Rank = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (CNT[mid] < TOT) Rank = mid, l = mid + 1;
            else r = mid - 1;
        }
        int ans = fen.query(Rank);
        if (Rank < M) {
            ++Rank;
            int P = TOT - CNT[Rank - 1] < foo[Rank].size() ? foo[Rank][TOT - CNT[Rank - 1] - 1] : foo[Rank][foo[Rank].size() - 1];
            ans += bit[Rank].query(P);
        }
        printf("%d\n", ans);
    } 
    return 0;
}

\(E.\) Pairs of Segments

将最少去掉多少线段转化为最多留下多少

首先对于所有 \(i, j\)， 如果第 \(i\) 个区间和第 \(j\) 个区间有交， 那么保留这两条线段的代价为不能保留和 \([min(l_{j}, r_{j}), max(r_{i}, r_{j})]\) 有交的任何其他线段。

那么就很简单了， 贪心解一个类似于最大独立集的问题。

时间复杂度 \(O(N^2)\)

\(F.\) Ball Sorting

考虑没有被移动过的数。

它们显然从左到右单调递增。

根据这个性质动态规划即可。

时间复杂度 \(O(N ^ 2)\)

贴一下代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MN = 555, INF = 1e9;

int N, A[MN], F[MN][MN];

int main() {

    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
        A[N + 1] = INF;
        for (int i = 0; i <= N + 1; ++i) for (int j = 0; j <= N + 1; ++j)
            F[i][j] = INF;
        for (int i = 0; i <= N + 1; ++i) F[0][i] = 0;
        for (int i = 1; i <= N + 1; ++i) {
            for (int j = 0; j <= N; ++j) {
                if (A[i] > A[i - 1])
                    F[i][j] = min(F[i][j], F[i - 1][j]);
                if (!j) continue;
                for (int k = 0; k < i - 1; ++k)
                    if (A[i] > A[k])
                        F[i][j] = min(F[i][j], F[k][j - 1] + i - k - 1);
            }
        }
        for (int i = 1; i <= N; ++i)
            printf("%d ", F[N + 1][i]);
        printf("\n");
    }
    return 0;
}