Codeforces Round#715 div.2 回顾

补题链接：https://codeforces.com/contest/1509

记录

其实本来今天晚上是有一个 Codeforces Round #716 (Div.2) 的；但是因为我盲目确信它的开始时间是传统艺能 22:35，而忽略了它的开始时间和往常不同，所以最后没有打成== 但是也因此，本懒狗可以好好地补完上一场拉跨的不行的 Div2 了。

这一场可以说非常的拉跨，ABC 选手都没有当成；明明才 1700 分的我都能直接俯冲 100 分，只能说使得本菜鸡本就不高的 rating 雪上加霜（）话虽这么说，补完了发现只是自己傻逼……这是不是有点似曾相识？

题解

A - Average Height

没什么好说的，偶数和奇数分别放在一起就完事了（

const int N = 2050;
int a[N];

signed main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif

    int T = scanner.nextInt();
    while (T --) {
        int n = scanner.nextInt();
        for (int i = 1; i <= n; ++ i)
            a[i] = scanner.nextInt();
        vector<int> ans;
        for (int i = 1; i <= n; ++ i)
            if (a[i] % 2) ans.push_back(a[i]);
        for (int i = 1; i <= n; ++ i)
            if (a[i] % 2 == 0) ans.push_back(a[i]);
        for (auto ii : ans)
            print(ii, ' ');
        println();
    }

    return 0;
}

B - TMT Document

也没啥难度，总的来说只要时刻保证前缀的 T 比 M 多，并且保证最后 T 和 M 的比例正确，且每一个 M 的后面都一定出现了一个 T 就可以保证合法性。

const int N = 1e5 + 4;
char s[N];

signed main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt(), n;
    while (T --) {
        scanner(n, s + 1);
        if (n % 3) {
            println("NO");
            continue;
        }
        int cntT = 0, cntM = 0, close = 0;
        bool ok = true;
        for (int i = 1; i <= n; ++ i) {
            if (s[i] == 'T') {
                ++ cntT;
                if (close < cntM) ++ close;
            }
            else ++ cntM;
            if (cntM > cntT) ok = false;
        }
        if (cntM * 2 != cntT || close < cntM)
            ok = false;
        println(ok ? "YES" : "NO");
    }

    return 0;
}

说是这么说，可是我还是因为没有长手所以白给一发~~残疾人竟是我自己~~（

C - The Sports Festival

给一个长度为 $n < 2000$ 的数组，现在要求你对这个数组进行重排序，使得下列式子的值最小：
$\sum_{i=1}^n\max_{j=1}^i a_j - \min_{j=1}^i a_j$
要求输出上面式子的最小值。

这个题做的过程可以说是十分丑陋了（）尽显本人菜逼本质 == 本弱鸡甚至能在考虑出了 $\mathcal{O}(n^2)$ 的贪心的假做法的情况下不自知，甚至还迷之自信的交了一二三四发，只能说是十分地滑稽可笑了。

当然，本题的正确做法也是 $\mathcal{O}(n^2)$ 的，只不过是比贪心更加合理的多的 DP；

首先，就像我的假做法考虑到的那样：首先对于这个数组排序，然后答案的构造方法一定是从中间的某个位置向两侧发散；考虑 $dp_{l..r}$ 表示当前已经扩散到了区间 $[l, r]$ 时，上面的式子的最小值；那么它只有两种转移来源——要不是加入了新的最小值 $a_l$ ，又或者是加入了新的最大值 $a_r$ ；所以不难得到下面的转移关系：

dp_{l..r} = (a_r - a_l) + \min(dp_{l+1..r}, dp_{l..r-1})

那么就可以写出代码通过此题了；

const int N = 2060;
longs dp[N][N], s[N], n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    $(n).nextArray(s + 1, s + 1 + n);
    sort(s + 1, s + 1 + n);
    for (int k = 1; k < n; ++ k)
        for (int l = 1; l <= n; ++ l)
            if (l + k > n) break;
            else {
                int r = l + k;
                dp[l][r] = s[r] - s[l] + min(dp[l + 1][r], dp[l][r - 1]);
            }
    output, dp[1][n], endl;

    return 0;
}

当初辅导某学长机试时，我苦口婆心地说“找到递推关系就是动态规划”的神态还历历在目，结果自己却深陷这样一个简单的 DP 而不自知，为自己的 $\mathcal{O}(n^2)$ 贪心假做法而沾沾自喜，属实是个小丑（

D - Binary Literature

给你一个长度 $n \leq 10^5$ ，以及三个长度为 $2n$ 的 01 字符串；现在你要构造一个 01 字符串，要求它至少以子序列的方式包含提供的三个字符串中的两个，且长度不能超过 $3n$ ；保证这种构造一定是成立的。

首先，考虑两个长度为 $2n$ 的字符串；我们一定可以构造出长度为 $4n - L$ 的满足子序列包含它们的串；其中 $L$ 的含义是这两个字符串的最长公共子串（LCS）。构造方法也非常的简单：对于 LCS 中的 $L$ 个字符，只插入构造的串中一次，其他的字符按照正确的顺序全部插入结果串即可。

但是众所周知，求 LCS 的算法的复杂度是 $\mathcal{O}(n^2)$ 的，而这个题目显然不允许这样的复杂度；但是因为题目中的字符串是 01 串，所以我们可以利用它的性质来考虑：

01 串中不是 0 就是 1，所以长度为 $2n$ 的 01 串中至少有一个字符出现的次数大于等于 $n$
因为我们有三个这样的 01 串，所以至少有两个字符串中的某个相同的字符出现次数大于等于 $n$

综上所述，我们找到这样的两个字符串；将这个字符出现的位置作为 LCS 的字符；然后使用上面的构造方法，就可以构造出长度为 $4n - L \leq 3n$ ，其中 $L \geq n$ 的目标串了。

在这种思想的基础上，我们还有一种更加优雅的构造方法：首先，维护三个指针，分别指向三个字符串，并且最开始都初始化为指向串首；然后，对于每一个位置，都选择较多的字符加入答案串，并推进对应的指针；这样，当一个字符串已经完全被加入答案串之后，我们假设答案串的长度为 $k$ ：

因为有一个长度为 $2n$ 的字符串被完全推入了，所以 $k \geq 2n$ ；
因为每次推入字符都要求了至少两个字符串当前位置为该字符，所以至少消耗了 $2k$ 个字符；
这样，三个字符串总共有 $6n$ 个字符，现在最多剩下 $6n - 2k$ 个字符，分配在两个串中；
这样，其中剩余较少的那个串最多包含 $3n - k$ 个字符；

综上所述，如果我们将那个剩余最少的字符串完全推入答案串，那么答案串至少会包含这两个已经压入的字符串作为子序列，并且答案串的长度最大为 $k + 3n - k = 3n$ ，符合题意；

const int N = 1e5 + 5;

char a[N * 2], b[N * 2], c[N * 2];
char ans[N * 3];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int T = $.nextInt(), n, p;
    const auto concat = [&](char *aa, char *bb) {
        const auto na = strlen(aa), nb = strlen(bb);
        strcpy(ans + p, na < nb ? aa : bb);
    };
    while (T --) {
        $(n, a, b, c);
        const int n2 = n * 2;
        auto ae = a + n2, be = b + n2, ce = c + n2;
        auto pa = a, pb = b, pc = c;
        p = 0;
        while (pa != ae && pb != be && pc != ce) {
            int cnt1 = *pa + *pb + *pc - '0' * 3;
            int ch = (cnt1 >= 2) + '0';
            pa += (ch == *pa), pb += (ch == *pb), pc += (ch == *pc);
            ans[p ++] = (char) ch;
        }
        if (pa == ae) concat(pb, pc);
        else if (pb == be) concat(pa, pc);
        else concat(pa, pb);
        $.println(ans);
    }

    return 0;
}

其实真要说的话，我觉得在知道 LCS 是哪些位置的情况下构造这样一个串还挺……不好写的；至少写出来大概都不会太好看；更何况还要使用那个 $\mathcal{O}(n^2)$ 的 DP 求出 LCS 的位置；实际上的写法只能说是很高妙了（

E - Almost Sorted

现在定义差不多有序的排序指对于任意下标 $i$ ，都满足 $p_{i+1} \geq p_i - 1$ ；现在给长度为 $n$ 的初始排列（即字典序最小的排列 $1\dots n$ ，要求求出字典序第 $k$ 小的差不多有序的排序；

这题我从最开始就没往正确的地儿想；我最开始想要打表找规律，但是实际上我想找的那个规律可以说是显然的，但是更高级的规律可以说打表什么也看不出来…… zcysky 提示我要画树我也没领会他的意思，盲目地漫无目的地思考了一会就缴械投降了，看到题解才发现是真的高：

首先，我们要正确的理解题目的定义：差不多有序的排序，如果出现了下降的情况，定义只允许步长为 1 的递减；所以，一个差不多有序的序列可以被表示为多个公差为 1 的递减区块；而且，我们可以用反证法证明——一旦确定了序列的递减区块的划分方法，那么这个序列是唯一的——且是初始排列按照这个划分方式划分之后，将每一个区间都翻转得到的序列。

那么接下来我们考虑 $k$ -大问题：因为每个区块都是由初始排序倒转区块得到的，所以我们可以贪心的考虑，第一个区块的大小越小，那么处理后得到的序列最小；同时，再确定了第一个区块的长度之后，我们将它从原排序中移除，那么就得到了一个长度缩小的子问题；我们可以递归地处理这个问题。

然后，我们考虑对于长度为 $n$ 的排序，差不多有序的序列数量：假设我们现在有一个和这个排序等长的 01 序列，且初始它的每一位都已经置零；对于每一个划分后的区块 $[l, r]$ ，我们将 $l$ 位置为 1；那么可以看到除了第 0 位必须为 1，其他的每一位都可以为 1/0；因此，一共有 $2^{n-1}$ 种不同的差不多有序的序列。

至此，我们已经可以使用上面说的递归的方法来求解本题了；但是实际上还有一种更加优秀的构造方法：

考虑上面说的标记 01 序列的方法：首先我们将上面的 01 序列看作一个二进制数；并且翻转下标的对应关系——让更小的下标对应更高的位；然后改为标记右边界，即区块中最低的位；然后翻转标记方法：即初值为 1，标记的位为 0；这样就可以得到满足上面所有约束；第 $k$ 小的排列就是 $k-1$ 的二进制表示左移 1 位（最低位始终为 0）对应的二进制表示所代表的划分方式；我们根据它构造答案即可。

const int N = 1e5 + 5;
int a[N], tmp[N];
lll fact[N];
bitset<N> x;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    longs T = $.nextInt(), n, k;
    while (T --) {
        input, n, k;
        if (n < 128) {
            lll cnt = 1;
            cnt <<= uint(n - 1);
            if (k > cnt) {
                output, -1, endl;
                continue;
            }
        } else x.reset();
        x = k - 1, x <<= 1;
        iota(a, a + n, 1);
        reverse(a, a + n);
        for (int i = 0; i < n; ++ i)
            if (!x.test(i)) {
                int j = i + 1;
                while (j < n && x.test(j)) ++ j;
                reverse(a + i, a + j);
                i = j - 1;
            }
        reverse(a, a + n);
        $.putArray(a, a + n);
    }

    return 0;
}

非常地巧妙；不管是证明了划分和排列的对应性还是划分和二进制表示的对应性都非常的巧妙（）这不比你最开始考虑的先映射 $k$ 和排序的关系，再用康托展开要阳间多了？更何况康托展开是 $\mathcal{O}(n^2)$ 的呢！

F - Complete the MST

现在给你一个有 $n \leq 2 \cdot 10^5$ 的节点的无向完全图；其中有 $m$ 条连边已经有权值（保证这部分的边的数量不超过 $2 \cdot 10^5$ ），部分边没有权值（保证至少有一条边没有权值）；现在要求你为这些没有权值的边赋非负值的权值，并且整张图所有边的权值异或和为 $0$ ，且图的 MST 的权值和最少。

看起来麻烦的一匹~~实际上也麻烦的一匹~~，首先进行一些思考：首先，我们一定最多只给一条边赋非零值——因为把它拆分给多条边完全没有任何好处；然后，MST 肯定是尽可能的用没有权值的边——因为如果条件允许，我们可以把我们选作 MST 的边全部赋值为 0；其次，我们赋值的那条边的权值，一定是所有有权值的边的权值的异或和。

那么，我们可以通过下面的过程来求解：

首先，考虑在空边构成的图上 DFS，以求出仅使用空边可以维系的连通块；
- 如果在选出这些边之后仍有未使用的空边，那么我们可以把异或和赋给它：这样对权值和无贡献；
- 否则，我们先暂记异或和，作为将要赋给某条空边的值；
然后，我们考虑使用 MST 算法，使用实边将第一步求出的连通块连成一个生成树；
如果一条实边不能被选入 MST，但是它连接了两个本需要依靠空边连接的连通块，那么：
- 如果这条边的权值比将要赋值给空边的权值要少，那么我们可以将空边赋给这条边，并取代它；
- 否则，那么还是维持原判，忽略这条边；
实际上，这个取代的过程可以通过缩小这个待赋值空边权值代销来实现。

这样，我们就可以使用我们的思考，构造出这个题目的答案~~虽然有些过程显得非常玄学就是了~~：

const int N = 2e5 + 5;

set<int> disc, adj[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n, m, u, v, w;
    input, n, m;
    auto res = (longs) n * (n - 1) / 2 - m;
    for (int i = 1; i <= n; ++i) disc.insert(i);
    ya_dsu all(n + 1), real(n + 1);
    vector<tuple<int, int, int>> edge;
    const function<void(int)> dfs = [&](int u) {
        disc.erase(u);
        for (int v = 0;;) {
            auto it = disc.lower_bound(v);
            if (it == disc.end()) return;
            else v = *it;
            if (!adj[u].count(v)) {
                all.connect(u, v);
                dfs(v), --res;
            }
            ++v;
        }
    };
    uint xs = 0;
    while (m--) {
        input, u, v, w;
        adj[u].insert(v), adj[v].insert(u);
        edge.emplace_back(w, u, v);
        xs ^= (uint) w;
    }
    for (int i = 1; i <= n; ++i)
        if (disc.count(i)) dfs(i);
    if (res > 0) xs = 0;
    sort(edge.begin(), edge.end());
    longs ans = 0;
    for (auto[w, u, v] : edge) {
        if (all.connect(u, v)) {
            ans += w;
            real.connect(u, v);
        } else if (real.connect(u, v))
            minimize(xs, (uint)w);
    }
    output, ans + xs, endl;
    return 0;
}

这个 DFS 就显得尤其离谱……在 $n = \sqrt{N}$ 的准完全图里，它最坏的情况下会跑掉 $\mathcal{\Theta}(n^2\log n)$ ，在其他的情况下我甚至都无法分析它的复杂度（算法设计课全还给院长了），但是就是可以过，所以…… 等我会证明它的复杂度的时候再补充说明把（

此外还值得一提的就是它的标程提供了一种优雅的路径压缩+按秩合并的并查集实现：

class ya_dsu {
    vector<int> fa;

    void join(int u, int v) {
        if (fa[u] > fa[v]) swap(u, v);
        fa[u] += fa[v], fa[v] = u;
    }

public:

    explicit ya_dsu(int n) : fa(n, -1) {}

    void clear() { fill(fa.begin(), fa.end(), -1); }

    int id(int u) { return fa[u] < 0 ? u : fa[u] = id(fa[u]); }

    bool connect(int u, int v) {
        u = id(u), v = id(v);
        if (u == v) return false;
        else return join(u, v), true;
    }

    int size(int u) { return -fa[id(u)]; }
};

简单的说就是那个数组非根节点记录根节点的编号，而根节点为负数，且绝对值等于连通块的大小；比起我之前的经典实现节约了一个 siz 数组的大小，本彩笔惊为天人，高，实在是高（

后记

这周，准确地说应该是上周，因为各种各样的事情——比如博客的花里胡哨啊等等——导致了我在考研复习和训练上投入的时间大幅减少；这是一个危险的信号，这周需要尽量避免。

欲辩已忘言，，明明在开始写这篇文章的时候还是感觉有好多的废话想要说的，，但是现在却对着窗口发呆，一句话也说不出来…… 唉，四点了，今天的墨墨背单词的卡又打不成了（）……因为实在是太晚了所以就不再多说些啥了，早点休息力 ==

最后送给自己一句话： 自分の光になれ！ 没有任何的典故，只是想对自己这么说而已——