2021.11.07模拟赛

Brighter than tomorrow and yesterday

2021.11.07 模拟赛

A. 签到题

对比剩下的三道确实蛮签到的（然后看错题浪费一个半小时，最后也没看对 -70 分）

体面很复杂，其实按照题面操作最后会得到一个树形结构，最小公共点就是树上 LCA

所以要支持单点和儿子加，链查

树上前缀和一下变成子树加和单点查，直接树状数组维护即可

注意题目区间的闭 or 开

B. 金币

个人觉得挺好的

构造方案的思路走不下去

按照题解的方式将每次称的方案记成一个矩阵，每行代表每袋金币每次放上去多少个，正数放在右边，负数放在左边

列数是固定的，考虑怎么获取答案，如果把每次称量的结果记成向量，正数表示左边重，负数表示右边重

则如果存在唯一的向量与其线性相关我们就能断定他是假的，因为答案与它的变化成正比

而线性相关具有传递性，所以我们选出的向量不能有两个是线性相关的

同时需要满足每列和为 $0$ ，容易发现这总是可行的，若现在的答案重存在向量 $[x_1,x_2,x_3,\dots]$ 翻转第一个分量变成 $[-x_1,x_2,x_3,\dots]$

如果它存在就忽略，否则就加入，这样显然不会破坏原来的性质，对每一个分量都如此操作即可

所以我们只需要计 长度为 $n$ 值域为 $[-k,k]$ 内的向量在线性相关意义下等价类的个数

先选出代表元，发现线性相关的都成倍数关系，故必然仅存在一个各分量 $\gcd$ 为 $1$ 的向量

莫反计数即可 $1+\sum_{i=1}^k\mu(i)\left(\left(2\lfloor\frac ki\rfloor+1\right)^n-1\right)$

$+1$ 是零向量， $-1$ 是不能选全零向量

C. 线段树

$all_0(n)=all_0(\lfloor\frac n2\rfloor)+all_0(\lceil\frac n2\rceil)+\lceil\frac n2\rceil pre_0(\lfloor\frac n2\rfloor)+\lfloor\frac n2\rfloor suf_0(\lceil\frac n2\rceil)-1$

$pre_0(n)=pre_0(\lfloor\frac n2\rfloor)+pre_0(\lceil\frac n2\rceil)+\lfloor\frac n2\rfloor-1$

$suf_0(n)=suf_0(\lfloor\frac n2\rfloor)+suf_0(\lceil\frac n2\rceil)+\lceil\frac n2\rceil-1$

$all_1(n)=all_0(1)+\sum_{i=1}^{\lfloor\frac n2\rfloor}all_0(2i)+\sum_{i=2}^{\lceil\frac n2\rceil}all_0(2i-1)$

$=1+\sum_{i=1}^{\lfloor\frac n2\rfloor}\left(2all_0(i)+i\cdot pre_0(i)+i\cdot suf_0(i)-1\right)+\sum_{i=2}^{\lceil\frac n2\rceil}\left(all_0(i-1)+all_0(i)+i\cdot pre_0(i-1)+(i-1)\cdot suf_0(i)-1\right)$

$=2all_1(\lfloor\frac n2\rfloor)+\sum_{i=1}^{\lfloor\frac n2\rfloor}\left(i\cdot pre_0(i)+i\cdot suf_0(i)\right)+2all_1(\lceil\frac n2\rceil)-all_0(\lceil\frac n2\rceil)+\sum_{i=1}^{\lceil\frac n2\rceil}\left(i\cdot pre_0(i)+i\cdot suf_0(i)\right)+\sum_{i=1}^{\lceil\frac n2\rceil}pre_0(i)-\sum_{i=1}^{\lceil\frac n2\rceil}suf_0(i)-(\lceil\frac n2\rceil+1)pre_0(\lceil\frac n2\rceil)-n+1$

$pre_1(n)=\sum_{i=1}^npre_0(i),pre_2(n)=\sum_{i=1}^ni\cdot pre_0(i)$
$suf_1(n)=\sum_{i=1}^nsuf_0(i),suf_2(n)=\sum_{i=1}^ni\cdot suf_0(i)$

$pre_1(n)=2pre_1(\lfloor\frac n2\rfloor)+2pre_1(\lceil\frac n2\rceil)-pre_0(\lceil\frac n2\rceil)+\frac 14(n^2-3n-2\lceil\frac n2\rceil)+1$
$suf_1(n)=2suf_1(\lfloor\frac n2\rfloor)+2suf_1(\lceil\frac n2\rceil)-suf_0(\lceil\frac n2\rceil)+\frac 14(n^2-3n+2\lceil\frac n2\rceil)$
$pre_2(n)=4pre_2(\lfloor\frac n2\rfloor)+4pre_2(\lceil\frac n2\rceil)-(2\lceil\frac n2\rceil+1)pre_0({\lceil\frac n2\rceil})+\frac 1{12}(2n^3-3n^2-5n-6\lceil\frac n2\rceil^2)+1$
$suf_2(n)=4suf_2(\lfloor\frac n2\rfloor)+4suf_2(\lceil\frac n2\rceil)-(2\lceil\frac n2\rceil+1)suf_0({\lceil\frac n2\rceil})+\frac 1{12}(2n^3-3n^2-5n+6\lceil\frac n2\rceil^2)$

自行感悟吧

D. 泰拉

最小树形图板子题 Tarjan DMST $O(m+n\log m)$ 或者把可并堆变成 $n^2$ 暴力找会更快 $n^2+m$

但是这东西好像没啥人会去学吧

考虑本题的特殊性质

按 $i \to x_i$ 连边，就会形成基环树森林，如果我们拿了一个环上的链，就可以最小代价拿掉整个基环树

拿一个树点就可以拿掉子树里的点，所以我们一旦拿掉一个点，就要拿完它的子树或基环树的所有点

因为没有 $x_i$ 的情况下编号越大越优，所以最优策略是先拿一些点然后拿到 $n$ 点，然后用 $n$ 拿剩下的环上的点最后拿完

而且拿到 $n$ 之前的点的几个段最大编号必然递增，否则调换顺序就会更优

设 $dp_i$ 表示确定了前若干组，当前最后一组的编号最大值为 $i$

预处理每个子树的代价一类的大力转移