[WP] Codeforces Round 915 (Div. 2)

理论上我现在应该在打强网杯线上赛，但是打的太坐牢了23333感觉crypto没有会做的，于是偷偷溜来打一场cf。

Account: CharmingLakesideJewel
Official Rank: 38
Performance: 2429
Rating Change: 845 → 1395

Passed Tasks: A B C D E

A Constructive Problems

题意是给了一个矩阵的大小 $n\times m$，要求我们选出最少的点涂红，使得某种操作过后所有的点都被涂红。求最少选几个点涂红。

这里“某种操作”指的是：对于一个点 $(x, y)$，若其相邻的上下中&相邻的左右中各至少有一个点被涂红了，那么涂红该点。

感觉不用过多解释，显然可以以对角线为核心去涂，那么答案也就呼之欲出了 $\max(n,m)$

n = int(input())
for _ in range(n):
    print(max(map(int, input().split())))

B Begginer’s Zelda

首先定义只剩下一个节点的状态时，这个节点不被认为是叶子节点。

容易发现，如果我们选取了两个“叶子节点”并合并之间的点，除非这两个叶子节点之间的点有且仅有一条向外连接的边，否则一定会使总叶子节点个数减2。如果我们每次选取一根树的直径去合并，那么除非树只剩下3个叶子节点，否则一定不会出现上述情况。

考虑到：一步操作可以使

$$\begin{cases} countLeaves\rightarrow countLeaves-2 &(countLeaves\geq 3) \\ countLeaves\rightarrow countLeaves-1 &(countLeaves=3) \end{cases}$$

那么总共 $\lfloor\frac{countLeaves+1}{2}\rfloor$ 次就可以使树只剩下一个结点。

const int N = 2e5 + 7;

int T, n;
int deg[N];

signed main() {
    kin >> T;
    while (T--) {
        kin >> n;
        for (int i = 1; i <= n; ++i) deg[i] = 0;
        for (int i = 1, u, v; i < n; ++i) {
            kin >> u >> v;
            ++deg[u], ++deg[v];
        }
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (deg[i] == 1) ++cnt;
        }
        kout << (cnt + 1) / 2 << '\n';
    }
    return 0;
}

C Largest Subsequence

容易发现，当第一次选定“字典序最大的序列”后，后续的操作都是在这个序列的基础上进行的，其他节点不会受到影响。且若干次“cyclic shift”之后，序列将从小到大排序。

那么我们可以首先找到这个序列，然后排序这个子序列，并检查此刻整个序列是否已经有序。若无序则输出 -1

如果有序，那么意味着可以达成最终目标。考虑我们找到的“字典序最大的序列”，若其中含有 $c$ 个字母，且其中有 $d$ 个字母是最大的，那么显然恰好 $c-d$ 次操作后这个子序列会有序（进而整个序列也会有序）。此时输出 $c-d$ 即可。

const int N = 2e3 + 7;
int T, n, k;
int64 a[N];

signed main() {
    kin >> T;
    while (T--) {
        kin >> n >> k;
        for (int i = 1; i <= n; ++i) kin >> a[i];
        sort(a + 1, a + n + 1);
        if (k >= 3) {
            kout << "0\n";
        } else if (k == 1) {
            int64 minimum = a[1];
            for (int i = 1; i < n; ++i) minimum = min(minimum, a[i + 1] - a[i]);
            kout << minimum << '\n';
        } else {
            // most difficult part
            int64 minimum = a[1];
            for (int i = 1; i < n; ++i) minimum = min(minimum, a[i + 1] - a[i]);
            for (int i = 1; i <= n; ++i) {
                for (int j = i + 1; j <= n; ++j) {
                    int64 current = a[j] - a[i];
                    int i = lower_bound(a + 1, a + n + 1, current) - a;
                    if (i <= n) minimum = min(minimum, a[i] - current);
                    if (i > 1) minimum = min(minimum, current - a[i - 1]);
                }
            }
            kout << minimum << '\n';
        }
    }
    return 0;
}

D Cyclic MEX

考虑某一个数对于 MEX 的贡献。

一个数 $x$ 对 MEX 的贡献为：若在位置 $0\sim c$ 中包含了 $0\sim x$ 的所有数，且位置 $0\sim c-1$ 没有此性质，那么我们认为 $x$ 对 $c\sim n-1$ 的位置的 MEX 有贡献。即：贡献为 $n-c$。

初始时求贡献是容易的，这里略去

考虑怎么更新贡献。对于一个数 $x$ 从开头移到末尾时，$x\sim n-1$ 之间的贡献都会变成 $1$ （因为对于这些数，此时仅有最后一个位置会有对 MEX 的贡献），而 $1\sim x-1$ 之间不会受到影响，反而因为位置前移，贡献增加 $1$。

那么这是一个仅有区间加操作和区间赋值的问题，我没有仔细思考有没有更优美的做法，直接用线段树去维护了。

const int N = 1e6 + 7;

int T, n, a[N], tmp[N];

namespace segt {
    struct node {
        int64 setTag, addTag, sum;
    } t[N << 2];
    void push_up(int p) {
        t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    }
    void push_down(int p, int l, int r) {
        if (t[p].setTag) {
            int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
            t[ls].setTag = t[rs].setTag = t[p].setTag;
            t[ls].addTag = t[rs].addTag = t[p].addTag = 0;
            t[ls].sum = (mid - l + 1) * t[p].setTag;
            t[rs].sum = (r - mid) * t[p].setTag;
            t[p].setTag = 0;
        } else if (t[p].addTag) {
            int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
            if (t[ls].setTag) t[ls].setTag += t[p].addTag;
            else t[ls].addTag += t[p].addTag;
            if (t[rs].setTag) t[rs].setTag += t[p].addTag;
            else t[rs].addTag += t[p].addTag;
            t[ls].sum += (mid - l + 1) * t[p].addTag;
            t[rs].sum += (r - mid) * t[p].addTag;
            t[p].addTag = 0;
        }
    }
    void build(int p, int l, int r, int *a) {
        t[p].setTag = t[p].addTag = 0;
        if (l == r) {
            t[p].sum = a[l];
            return;
        }
        int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
        build(ls, l, mid, a);
        build(rs, mid + 1, r, a);
        push_up(p);
    }
    void all_add() {
        if (t[1].setTag) t[1].setTag += 1;
        else t[1].addTag += 1;
        t[1].sum += n;
    }
    void range_set(int p, int l, int r, int L, int R, int val) {
        if (L <= l && r <= R) {
            t[p].setTag = val;
            t[p].addTag = 0;
            t[p].sum = (r - l + 1) * val;
            return;
        }
        push_down(p, l, r);
        int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
        if (L <= mid) range_set(ls, l, mid, L, R, val);
        if (R > mid) range_set(rs, mid + 1, r, L, R, val);
        push_up(p);
    }
}

signed main() {
    kin >> T;
    while (T--) {
        kin >> n;
        for (int i = 0; i < n; ++i) {
            kin >> a[i];
            tmp[a[i]] = i;
        }
        for (int i = 1; i < n; ++i) tmp[i] = max(tmp[i], tmp[i - 1]);
        for (int i = 0; i < n; ++i) tmp[i] = n - tmp[i];

        segt::build(1, 0, n - 1, tmp);
        int64 ans = segt::t[1].sum;
        for (int i = 1; i < n; ++i) {
            segt::all_add();
            segt::range_set(1, 0, n - 1, a[i - 1], n - 1, 1);
            ans = max(ans, segt::t[1].sum);
        }
        kout << ans << '\n';
    }
    return 0;
}

E One-X

这个题也很有意思。

我们考虑一个结点，其作为 LCA 产生的贡献值为 $\text{该节点值} \cdot (2^{左子树区间长度}-1) \cdot (2^{右子树区间长度}-1)$

那么考虑，对于一个子树其内所有节点产生的贡献，其实只跟这个子树的区间长度和子树的根有关，且这个关系（关于子树的根的节点值）是线性的。

那么我们可以直接对于一棵区间长度为 $L$ 的子树，记录一个 $k$ 和 $b$ 表示，当这个子树的根的值为 $x$ 时整个子树的贡献为 $kx+b$。

很有趣的，我们很容易对一个区间长度为 $L$ 的子树，通过其两个子树的 $k$ 和 $b$ 得到其自身的 $k$ 和 $b$。这个过程是简单的数学计算

$$\begin{cases} k = 2k_l+2k_r+(2^{leftInterval}-1)\cdot(2^{rightInterval}-1) \\ b = b_l+b_r+k_l \end{cases}$$

线段树一个很有趣的性质是，若总区间长度为 $n$，对于第 $x$ 层（设根节点为第 $0$ 层），节点的区间长度一定是 $\lfloor\frac{n}{2^x}\rfloor$ 和 $\lceil\frac{n}{2^x}\rceil$ 中的一个。因此可以发现，一个这样的线段树，最多可以产生 $2\log_2 n$ 个不同的 $(k,b)$ 对（这证明了我们时间复杂度的正确性）

加上计算贡献值时需要快速幂，总的时间复杂度是 $O(T\log^2 n)$ 的。

const int P = 998244353;

struct funct {
    int64 k, b;
    funct(int64 _k = 0, int64 _b = 0) : k(_k), b(_b) {}
    int64 operator () (int64 x) { return (k * x + b) % P; }
    funct operator + (funct f) { return funct((k + f.k) % P, (b + f.b) % P); }
};

map<int64, funct> f;

int64 fpow(int64 a, int64 b) {
    b %= P - 1;
    int64 res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}

funct solve(int64 n) {
    if (n == 1) return funct(1, 0);
    if (f.count(n)) return f[n];
    int64 mid = n >> 1;
    funct resl = solve(n - mid), resr = solve(mid);
    int64 k = resl.k * 2 + resr.k * 2 + (fpow(2, n - mid) - 1) * (fpow(2, mid) - 1);
    int64 b = resl.b + resr.b + resr.k;
    return f[n] = funct((k % P + P) % P, b % P);
}

signed main() {
    int T;
    int64 n;
    kin >> T;
    while (T--) {
        kin >> n;
        kout << solve(n)(1) << '\n';
    }
    return 0;
}

后记

很可惜这次倒序开题没有吃到任何分，感觉正序开题分要高很多，果然还是不能对自己的能力太过自信啊。或者下次可以考虑从 C 倒序开题。

这次还有一个问题是，一开始一直在强网杯线上赛那边做题，所以也没注意cf这边，甚至没有提前报名，后来是突然想起来了卡着extraRegisteration报进的，所以确实时间上略吃亏了一点。

但是E做出来了！还是挺令人开心的。（可惜最后排名不是很高233）说起来这次 E 也是那种没什么算法纯凭思维的题，所以做出来了也没那么意外233。后面如果准备再继续加把劲的话估计要狠狠练练算法了。

---

codeforces.profile: CharmingLakesideJewel

关于代码模板：C++ 的代码都略去了代码模板，只保留了核心代码。代码模板即通常的快读快输，kin, kout 可以理解为 cin, cout 的快读快输版本