Skip to content

2023牛客暑期多校训练营2

~~（前一天是被恶心到的一天，这次是一维很难其实很简单的一天）~~

好像是道 CTF 的题，留坑

~~（看题的时候没看出来是最大权闭合子图，时候看题解的时候感觉悔死了。。。）~~ 题意：一棵 $n$ 个点的树，给出 $m$ 条路径，每条路径有 $x_i$ 的收入，$y_i$ 的支出，每条树边有 $c_i$ 的

有依赖关系的物品选择，直接最大权闭合子图，负的连源点，正的连汇点，树边向路径建边，为了减少边数可以用树链剖分 + 线段树 + 前缀建边优化，将边数优化为 $O(m\log n)$，直接跑最大流就可以了（由于出题人没有卡，所以只用线段树建边优化没用前缀建边优化也能过，边数 $O(m\log^2 n)$）

C - graph

D - The Game of Eating

题意： 注意到每道菜无论让谁选对于每个人得到的收益都是不变的，所以可以直接从后往前选，考虑后面的人可能会怎么选，前面的人根据这个选就可以（因为自己补选别人也会帮他选的），所以直接贪心即可，复杂度 $O(nm)$

E - Square

题意：给定 $x$ 求 $y \in [0,1e9]_\mathbb Z$ 满足 $\exists k,\lfloor{y^2 \over 10^k}\rfloor=x$ 很明显，在数字足够大的情况下，$y$ 和 $\sqrt{x*10^k}$ 在取整后的误差会越来越小，所以可以直接每次对 $x$ 乘 $10$，对开根后的结果左右尝试一下是否满足条件即可，复杂度 $O(TC\log n)$

二分图博弈的题，等学完再说，先留坑

题意：给出一个串 $S$，求其是否可以拆分成若干中心对称串（$s,o,x,z$ 和自身相等，$(b,q),(p,d),(n,u)$ 对应相等，其他均不等）

中心对称串可以 manacher 魔改后求出 由于只需要判断是否存在划分，所以直接贪心拆最小的即可（在同起点的情况下，更大的一定可以拆成至少 $3$ 个更小的），复杂度 $O(\sum n)$（注意可能会被卡常，因为要卡 $O(\sum n\log n)$ 的做法）

H - 0 and 1 in BIT

题意：给定一个操作序列，$A$ 表示对 $x$ 取反，$B$ 表示 $x=x+1$，每次给定一个操作序列的子区间和起始数字，求操作后的数字，强制在线

注意到在模 $2^{len}$ 的意义下（$len$ 为给定起始数字比特位数），对 $x$ 取反相当于 $x=-x-1$，于是将两种变换变成了两种线性变换，可以用矩阵表示，所以原问题就变成了求区间矩阵积的问题，对于每个询问的 $len$ 不同的问题直接选择 unsigned long long 的自然溢出即可（取模也可以理解为溢出），复杂度 $O(8n\log n)$

也可以选择另一种前缀和预处理的方法，具体如下： - $cnt_{l,r}=[l,r]$ 内 $A$ 的个数 - $f_{l,r}$ 表示 $x$ 经过 $[l,r]$ 的操作后变为 $(-1)^{cnt_{l,r}}x+f_{l,r}$ - $f_{l,r}=\begin{cases}f_{1,r}-f_{1,l-1}&,cnt_{l,r}{\ \rm mod\ }2=0\f_{1,r}+f_{1,l-1}&,cnt_{l,r}{\ \rm mod\ }2=1\end{cases}$

直接求解即可，复杂度 $O(n)$

题意：要求给出一种五子棋的结果，摆满了整个棋盘并且最终为平局

签到题，解法多样，我的解法是摆乌龟壳，正解是另外一种经典解法，如下：（. 任意填即可） xo...xo...xo... ...xo...xo...xo .xo...xo...xo.. o...xo...xo...x

...

J - Smoke

K - Box

题意：有个 $01$ 串，每个 $1$ 可以向左/右/原位置移动，要求一个位置不能有两个 $1$。每个位置有一个代价，要求最小化 $1$ 所在位置的代价和

一眼 dp，定义 $dp_{i,0/1,0/1/2}$，表示第 $i$ 个位置在考虑了前 $i$ 个位置后是否已经有 $1$，该位置的原有数字向左/当前/右移动时的最大权值和，分类讨论转移即可，复杂度 $O(n\log n)$

M - Fundamental Skills in Data Structures