CF Round#934 Div.2

发表于 2024-04-22 更新于 2024-06-15 分类于 Codeforces

A. Destroying Bridges

题意：给一张完全图，求删去\(k\)条边后，点1不可到达的编号最大的点。

题解：手玩一下最优解盯着点1的边删就行。

题意：将2个n的排列打乱为等长的两部分，各选出\(k\)个值，使得两边的异或和相同。

题解：构造，如果两个一样的数在一侧直接选，如果还剩就从异侧里面补。

题意：博弈，轮流从数组里面取数，使得Alice得到的数组的mex最大。

题解：发现从0开始，如果有至少两个数，那么一定是不急着拿的，只考虑出现一次的数，第一个可以先手直接拿，第二个就会成为瓶颈。

题意：定义字符串为\(k-good\)，即存在长度为\(k\)的非回文子串，定义字符串的权重为所有\(k-good\)的\(k\)之和，多次区间查询子串的权重。

题解：这个\(good\)是一个非常强的约束，当\(k\)为偶数时，要求字符串完全由一个字符组成，当\(k\)为奇数时，要求字符串由两个字符交替组成，特别地当\(k = len(str)\)时需要特判。因此本题转换为了多次对区间子串求是否为回文串，manacher解决。

题意：定义染色操作，对树的任一节点和任一距离\(d\)，染色所有到该点距离为\(d\)的点，求一棵树的最小染色次数。

题解：很容易想到树的直径，讨论一下链的退化情况，按照链的长度分为：奇数，模4余2，模4余0，共三类情况，并可以给出由中心开始的染色方案。扩展到树的普通情况，基于链的性质，链外的路径一定不会更长，因此从中心开始的染色方案一定可以覆盖直径以外的节点，固可按照直径链的退化情况进行构造。

题意：对于一个数组，可以选择一段长度大于1的子数组进行区间减操作，如果一个数组可以通过若干次操作变为全0数组，则称其为好的。求长度为\(n\)的，初始元素范围在\([0, k]\)中的好数组一共有多少个。

题解：

首先要把这个好的定义转换一下，主要的限制来源于长度要大于1，这意味着需要满足\(a_{i} \leq a_{i-1} + a_{i+1}\)，对于数组两端可以认为\(a_{0}=a_{n+1}=0\)，满足这个条件即为好数组。
然后考虑统计，一个简单的想法是dp，状态一定要有\(k^2\)表示这个约束，时间复杂度太大，那么这种计数问题通常就要往容斥原理的方向考虑，定义\(a_{i} \ge a_{i-1}+a{i+1}\)时，位置\(i\)是坏的。定义\(f(x)\)表示集合\(x\)中所有位置都是坏的的数组个数，那么根据容斥原理好的数组总数为\(\sum (-1)^{|x|}f(x)\)。
接下来考虑怎么求这个容斥，\(f[i][j][0/1]\)表示：\(a_{i}=j\)，考虑\([1, i)\)位置中有至少奇数/偶数个坏位置的方案数，那么转移方程如下：
- 位置\(i-1\)无所谓是不是坏的（容斥原理）：\(f[i][j][l] = \sum f[i-1][j][l]\)
- 位置\(i-1\)一定是坏的：\(f[i][j][l] = \sum f[i-2][j'][l^1] * (k-j'-j)\)
dp式前缀和优化一下就可以得到\(O(n^2)\)的写法。