2023-10-17 10:57 已编辑重庆八中宏帆初级中学校算法工程师

关注

【题解】牛客挑战赛70

A

观察数据范围，我们可以发现 $n \leq 3000, k \leq 10^9$ 指向的是时间复杂度大概率是 $O(n^2)$ 的。又由于是回文串，和回文串相关的 $O(n^2)$ 算法最容易想到的就是枚举对称点暴力扩展。

接着再考虑如何处理操作，如果我们单独有一个回文串，想要扩展它的长度，最优的方法就是在对称点进行操作，这样每次操作后序列依旧回文，如 $\texttt{bab}$ 可以操作为 $\texttt{baab}$ ， $\texttt{bcbbcb}$ 可以操作为 $\texttt{bcbbbcb}$ 。

但是如果不是整个序列为回文串的话，我们直接找最长回文子串然后在对称点进行操作不一定最优，所以需要考虑在两侧进行操作（因为不在回文串两侧一定不是最优），这时候有两种情况，一种是可以通过在一侧进行操作后就能继续匹配，如 $\texttt{bbabc}$ 可以对右侧的 $\texttt{b}$ 操作后扩展回文串长度，回文串由 $\texttt{bab}$ 变为 $\texttt{bbabb}$ 这个时候我们执行这个操作，因为这次操作和在对称点进行操作比一定不劣，如果两端加数都不能继续匹配，如 $\texttt{cbabd}$ ，就停止两侧的扩展，因为此时想要在两侧操作后能扩展，当且仅当同时对两边进行相同次数的操作，这样和在对称点操作比起来一定不优。

最后，如果我们有一段到了序列的首或尾，我们直接选择在中间操作，一直操作到长度等于 $k$ 。

B

从题目最强的限制入手，考虑如何使得每个点恰好处于一个环上？

这是一个很典的 trick，对于任何在环上的点 $p$ ，出入度都为 $1$ ，于是将它拆成两个点，记为 $p_{in}, p_{out}$ 。原图上的一条边 $(u, v)$ 在拆点后的图上就表示为 $(u_{out}, v_{in})$ ，如果要满足限制，当且仅当该图存在完美匹配。

现在加入双边权的限制，这是 0/1 分数规划 的模型，具体地，我们二分答案 $mid$ ，如果有解，则满足 $\frac{\sum_{i \in E} a_i }{\sum_{i \in E} b_i } \ge mid$ ，化一下式子变成 $\sum_{i \in E} a_i - mid \cdot {\sum_{i \in E} b_i } \ge 0$ ，于是重新对每一条边赋权为 $c_i = a_i - mid \cdot b_i$ ，检验是否有解直接跑 KM 即可。

复杂度取决于 KM 的实现方式，较优秀的为 $\Theta(n^3) \log V$ ，其中 $V$ 是 $a_i, b_i$ 的值域。

C

让我们来挖掘一些性质。不妨设 $n=2$ ，它的 $0\sim 2^n-1$ 的序列用二进制表示即为:

\begin{matrix} 00 \\ 01 \\ 10 \\ 11 \\ \end{matrix}

那么当 $n=3$ 时，就相当于是在这个序列前加了一位，这一位可能是 $1$ 也可能是 $0$ ，列出来即为:

\begin{matrix} 0\quad 00 \\ 0\quad 01 \\ 0\quad 10 \\ 0\quad 11 \\ 1\quad 00 \\ 1\quad 01 \\ 1\quad 10 \\ 1\quad 11 \\ \end{matrix}

所以可以发现:

异或值是对称的；
其最中间的数值是 $2^n-1$ 。

我们再对比上面 $n=2$ 与 $n=3$ 的区别，可以发现，题目的问题可以递推求解。

我们设第一个问题是的答案是 $f$ ，第二个问题是 $g$ 。那么有以下式子:

\begin{cases} f_i=2\times f_{i-1} \binom{n}{i} \\ \\ g_i=2\times g_{i-1} i\binom{n}{i} \end{cases}

我们把上面第一个式子化为求和式，即为 $\displaystyle\sum_{i=1}^n2^{n-i}\binom{n}{i}$ ，又因为 $\displaystyle\binom{n}{i}=\binom{n}{n-i}$ ，所以 $\displaystyle=\sum_{i=1}^n2^{n-i}\binom{n}{n-i}\displaystyle=-2^n\times\binom{n}{n} \sum_{i=0}^n2^{n-i}\binom{n}{n-i}$ ，换一下元，即 $\displaystyle-2^n\times\binom{n}{n} \sum_{i=0}^n2^{i}\binom{n}{i}$ ，又通过二项式定理，得到原式即 $(2 1)^n-2^n=3^n-2^n$ ，用快速幂求解即可。

我们把上面第二个式子化为求和式，即为 $\displaystyle\sum_{i=1}^ni\times2^{n-i}(2^i-1)\binom{n}{i}$ 因为加上 $i=0$ 其值不变故可写为 $\displaystyle\sum_{i=0}^ni\times2^{n-i}(2^i-1)\binom{n}{i}$ ，将括号拆开 $\displaystyle\sum_{i=0}^ni2^{n}\binom{n}{i}-\sum_{i=0}^ni2^{n-i}\binom{n}{i}$ 我们将其看作左右两个式子求解，先看左边，即为 $\displaystyle\sum_{i=0}^ni2^{n}\binom{n}{i}$ ，将 $2^n$ 提出，即 $\displaystyle2^{n}\sum_{i=0}^ni\binom{n}{i}=2^{n-1}(\sum_{i=0}^ni\binom{n}{i} \sum_{i=0}^ni\binom{n}{i})$ 再将式子括号右边的求和式通过 $\binom{n}{i}=\binom{n}{n-i}$ 变换一下，即 $\displaystyle 2^{n-1}(\sum_{i=0}^ni\binom{n}{i} \sum_{i=0}^ni\binom{n}{n-i})$ 再换元，即 $\displaystyle2^{n-1}(\sum_{i=0}^ni\binom{n}{i} \sum_{i=0}^n(n-i)\binom{n}{i})$ 再将括号中的数加起来，即 $=2^{n-1}\sum_{i=0}^nn\binom{n}{i}$ ，再将 $n$ 提出，即 $\displaystyle n2^{n-1}\sum_{i=0}^n\binom{n}{i}$ 再用二项式定理，可化为： $n2^{n-1}2^n=n2^{2n-1}$ 。

我们再考虑右边的式子 $\displaystyle-\sum_{i=0}^ni2^{n-i}\binom{n}{i}$ ，给其加上一个 $\displaystyle n\sum_{i=0}^{n}2^{n-i}\binom{n}{i}$ ，再减去，即 $\displaystyle\sum_{i=0}^{n}(n-i)2^{n-i}\binom{n}{i}-n\sum_{i=0}^{n}2^{n-i}\binom{n}{i}$ 右边式子的结果在上面求解第一个问题已经算过，为 $n*3^n$ ，化简即为 $\displaystyle\sum_{i=0}^{n}(n-i)2^{n-i}\binom{n}{i}-n*3^n$ 再换元，即为 $\displaystyle\sum_{i=0}^{n}i2^i\binom{n}{i}-n*3^n$ 再通过组合恒等式 $\displaystyle\binom{n}{m}=n/m*\binom{n-1}{m-1}$ ，可化为 $\displaystyle\sum_{i=0}^{n}n2^i\binom{n-1}{i-1}-n*3^n$ ，提出 $2*n$ ，即为 $\displaystyle 2n\sum_{i=0}^{n}2^{i-1}\binom{n-1}{i-1}-n*3^n$ 再换元，即为 $\displaystyle 2n\sum_{i=0}^{n-1}2^{i}\binom{n-1}{i}-n*3^n$ 再用二项式定理，可化为 $\displaystyle 2n*3^{n-1}-n*3^n=-n*3^{n-1}$ 。

综上所述，第二问答案为 $n2^{2n-1}-n*3^{n-1}$ ，可用快速幂求解。

D

一个结论是任意无向图度数为奇数的点有偶数个。因为一条边会使得度数总和增加 $2$ ，度数总和永远是偶数。

所以如果建一个虚点向所有度数为奇数的点连边，则这个新图存在欧拉回路。

考虑初始图为二分图。然后加上虚点。

考虑从虚点出发，每走一条边，就染成跟上一条边不相同的颜色，即黑白间隔染色。则不被虚点连向的点（度数为偶数），每次进入这个点就会出这个点，边能一一对应。设初始图中 $a_x$ 表示 $x$ 点为端点的边有 $a_x$ 条被染成白色， $b_x$ 表示以 $x$ 为端点的边有 $b_x$ 条被染成黑色，则对于度数为偶数的点 $|a_x-b_x|=0$ 。对于度数为奇数的点，加上虚点连向的边，一样可以做到一进一出一一对应。由于虚点连向的边不产生贡献，所以 $|a_x-b_x|=1$ 。

则二分图 $\sum_x |a_x-b_x|$ 的答案为图中度数为奇数的点的个数。

考虑本题。驿站发件处看做左部点，收件处看做右部点，是一个二分图。所以可以用上述结论。

对于一个询问新加入的点，会对其右上的点的度数产生影响，而新加入点的度数为左下的点数。

首先二维数点求出初始答案，记为 $ans1$ 。然后记录每个点的度数奇偶性。

对于新加入的点分为三个二维数点。

第一个算新加入点的度数，记为 $deg1$ 。

第二个算新加入点右上角的点数，记为 $cnt1$ 。

第三个算新加入点右上角度数为偶数的点数，记为 $cnt2$

新答案为 $ans1 [deg1\%2=1] cnt2-(cnt1-cnt2)$ 。

E

前三种操作维护起来比较简单，这里就略过了，第四种操作只需要注意到「最多操作 $\log_2 n$ 次」的性质即可。

主要来看询问部分。

整个图的形状就是一根「主链」上挂了若干根「副链」，由此可以发现这个图中的最长简单链的长相一定类似如下的图示：

\cdots{\color{black}\bullet\ \bullet\ \bullet\ }\color{black}\bullet\ {\color{black}\bullet\ }{\color{red}{\bullet\ \bullet\ \bullet\ \bullet\ \bullet\ }}{\color{black}\bullet\ }\color{black}\bullet\ {\color{black}\bullet\ \bullet\ \bullet}\cdots\ \\ \cdots{\color{black}\bullet\ \color{red}{\bullet\ }\color{black}\bullet\ \bullet\ \bullet\ \color{red}{\bullet\ }}\color{black}\bullet\cdots \\ \cdots{\color{black}\bullet\ \color{red}{\bullet\ }\color{black}\bullet\ \bullet\ \bullet\ \color{red}{\bullet\ }}\color{black}\bullet\cdots \\ \cdots{\color{black}\bullet\ \color{red}{\bullet\ }\color{black}\bullet\ \bullet\ \bullet\ \color{red}{\bullet\ }}\color{black}\bullet\cdots \\ \vdots

其中红色的点是图中的最长链。那么我们考虑暴力怎么做。我们处理出两个东西，一个是上面那个图的第一层的权值前缀和 $a_i$ ，以及不包含第一层元素的每一条单链的权值和 $b_i$ ，那么答案即 $\max\limits_{1\leqslant i\leqslant j\leqslant n}\{a_j-a_{i-1} b_i b_j\}$ 。此时就可以考虑平衡树套线段树了，平衡树维护第一层的结点，线段树维护每条链除第一层结点外的部分，维护方法参见最大子段和。