1944(div2)

A. Destroying Bridges

有 $n$ 个岛屿，编号为 $1,2,\dots ,n$ 。最初，每对岛屿都由一座桥连接。因此，一共有 $\frac{n(n-1)}{2}$ 座桥。

Everule 住在 $1$ 岛上，喜欢利用桥梁访问其他岛屿。Dominater 有能力摧毁最多 $k$ 座桥梁，以尽量减少 Everule 可以使用（可能是多座）桥梁到达的岛屿数量。

如果 Dominater 以最佳方式摧毁桥梁，求 Everule 可以访问的岛屿（包括岛屿 $1$ ）的最少数量。

易得：当 $k\ge n-1$ 时，将 1 周边的都切断了，否则只要有一个连着都能遍历到所有节点

void solve() {
    int n, k;cin >> n >> k;
    if (k >= n - 1) {
        cout << 1 << '\n';
    } else {
        cout << n << '\n';
    }
}

B. Equal XOR

给你一个长度为 $2n$ 的数组 $a$ ，它由 $1$ 到 $n$ 的每个整数组成，每个整数包含次。

同时给你一个整数 $k$ ( $1\le k\le \lfloor \frac{n}{2}\rfloor$ )。

你需要找出两个长度分别为 $\mathbf{2}\mathbf{k}$ 的数组 $l$ 和 $r$ ，使得：

• $l$ 是 $[a_1,a_2,\dots a_n]$ 的子集 ${}^{†}$ 。
• $r$ 是 $[a_{n+1},a_{n+2},\dots a_{2n}]$ 的子集
• $l,r$ 满足： $l_1\oplus l_2\oplus \dots \oplus l_{2k}=r_1\oplus r_2\oplus \dots \oplus r_{2k}$ 是 $r$ 的子集。

可以证明，至少有一对 $l$ 和 $r$ 总是存在的。如果有多个解，可以输出其中任意一个。

可以知道，每次输出的 $2\times k$ 序列都是偶数个，因此，先将两个序列中有两个相同数字的数的输出了，再去找都是一个的情况。

void solve() {
    int n, k;cin >> n >> k;k *= 2;
    map<int, int> ma, mb;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;ma[x]++;
    }
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;mb[x]++;
    }
    vector<int> ans1, ans2;
    for (auto [x, y] : ma) {
        if (y == 2) {
            ans1.push_back(x);
            ans1.push_back(x);
        }
        if (ans1.size() == k)break;
    }
    for (auto [x, y] : mb) {
        if (y == 2) {
            ans2.push_back(x);
            ans2.push_back(x);
        }
        if (ans2.size() == k)break;
    }
    if (ans1.size() < k) {
        for (int i = 1;i <= n;i++) {
            if (ma[i] == 1 && mb[i] == 1) {
                ans1.push_back(i);
                ans2.push_back(i);
            }
            if (ans1.size() == k)break;
        }
    }
    for (auto i : ans1)cout << i << " ";cout << "\n";
    for (auto i : ans2)cout << i << " ";cout << "\n";
}

C. MEX Game 1

爱丽丝和鲍勃在大小为 $n$ 的数组 $a$ 上进行另一场博弈。爱丽丝从一个空数组 $c$ 开始。双方轮流下棋，爱丽丝先开始。

轮到爱丽丝时，她从 $a$ 中选取一个元素，将其追加到 $c$ 中，然后从 $a$ 中删除。

轮到鲍勃时，他从 $a$ 中选取一个元素，然后从 $a$ 中删除。

当数组 $a$ 为空时，游戏结束。游戏的分数定义为 $c$ 的 MEX ${}^{†}$ 。爱丽丝希望最大化得分，而鲍勃希望最小化得分。如果双方都以最优方式进行游戏，求游戏的最终得分。

${}^{†}$ 整数数组的 $\mathrm{MEX}$ （最小不等式）定义为数组中不出现的最小非负整数。

可以知道，当数组某个数字没有的数字时，$c$ 数组必然不可能出现这个数字，当出现两个单个数字时，必然有一个会被 Bob 制裁掉，所以这种情况下，答案可能是这两个单个数字较大的一个，当出现同一个数字次数 $\ge 2$ 时，必然可以选到 $c$ 数组中去。

void solve() {
    int n;cin >> n;
    map<int, int> mp;
    for (int i = 0;i < n;i++) {
        int x;cin >> x;mp[x]++;
    }
    int re = 0;
    for (int i = 0;i <= n;i++) {
        re += mp[i] == 1;
        if ((re == 2) || mp[i] == 0) {
            cout << i << '\n';return;
        }
    }
}

D. Non-Palindromic Substring

如果至少存在一个长度为 $k$ 的子串 ${}^{†}$ 不是回文 ${}^{‡}$ ，则称字符串 $t$ 为 $k$ （-good）。让 $f(t)$ 表示所有 $k$ 的值之和，使得字符串 $t$ 是 $k$ -good。

给你一个长度为 $n$ 的字符串 $s$ 。您需要回答以下问题中的 $q$ 个：

• 给定 $l$ 和 $r$ ( $l<r$ ), 求 $f(s_l{s}_{l+1}\dots s_r)$ 的值。

${}^{†}$ 字符串 $z$ 的子串是来自 $z$ 的连续字符段。例如，" $\mathtt{defor}$ "、" $\mathtt{code}$ "和" $\mathtt{o}$ "都是" $\mathtt{codeforces}$ "的子串，而" $\mathtt{codes}$ "和" $\mathtt{aaa}$ "不是。

${}^{‡}$ 回文字符串是指前后读法相同的字符串。例如，字符串" $\mathtt{\text{z}}$ "、" $\mathtt{\text{aa}}$ "和" $\mathtt{\text{tacocat}}$ "是回文字符串，而" $\mathtt{\text{codeforces}}$ "和" $\mathtt{\text{ab}}$ "不是。

Solution

Manacher 算法

待到学习字符串算法时再来

Manacher - OI Wiki

P3805 【模板】manacher - 洛谷

P4555 [国家集训队] 最长双回文串 - 洛谷
看不懂
(待更 $\dots$)