NOIP2022模拟赛by Zyq1

wgyhm

2022-08-26

prufer序列, 构造, 贪心

自己的模拟赛/se

T1

CF1310A

考虑一种贪心，对于所有相同当前大小相同的数，除了权值最大的那个以为其余加一。

维护一个大根堆，以及大根堆里所有数的权值之和。加入权值相同的以后，弹出最大的。

T2

CF226C

常见结论，$\gcd(F_{a1},F_{a2},F_{a3},…,F_{an})=F_{\gcd(a1,a2,a3…,an)}$

转化为求 ${\dfrac{r}{x}}-\dfrac{l-1}{x}\ge k$ 的 $x$ 的最大值，用整除分块就好了。

答案就是 $F_x$。

T3

https://dmoj.ca/problem/dmopc21c5p6

考虑用二分图搓暴力，最小字典序.

素数的分布类似于随机，我们发现前面的大多数都是对于一个区间 $[l,r]$，如果 $l+r$ 为质数，将 $[l,r]$ 填为 $r,r-1,r-2,…,l$。最后的一部分数不符合规律，我们可以对后面的进行暴力，暴力的复杂度是 $O(n^3)$ 的，大概设成 $300$ 左右肯定可以了。

证明不太会。/kk

T4

https://dmoj.ca/problem/dmopc21c8p5

先不管多组询问。考虑只有一次询问。

Step 1

根据 prufer 序列，令每个点的度数为 $d_i$ 。

则题目转化为 $\sum d_i=2N-2$，求 $\sum w_{di}$ 的最小值。

不妨设 $a_i=d_i-1,0\le a_i\le K-1,b_i=w_{i+1}-w_1$

这样可以看做容量为 $N-2$，有 $K-1$ 个物品，每个物品的体积是 $a_i$，价值是 $w_{a_i+1}-w_1=b_{ai}$。必须装满，求最小价值。或者可以不管直接 dp。

$f_i=\min f_{i-j}+b_j$

答案为 $N\times w_1+f_{n-2}$

这样做复杂度是 $O(NK)$ 的。

Step 2

考虑优化 $f_i=\min f_{i-j}+b_j$

令 $j$ 满足 $\forall k,1\le k\le K-1,\dfrac{b_j}{j}\le \dfrac{b_k}{k}$

很容易想到对于一个充分大的 $N$ ，总是从状态 $N-j$ 转移过来。

事实上 $n\ge K(K-1)$ 即可。

证明：

反证法。

假设对于任意的 $N\ge K(K-1)$ 从不使用物品 $j$ 。因为所有物品的体积小于等于 $K-1$，所以至少有 $k\ge K>j$ 个可重物品 $u_1,u_2,u_3,…,u_k$ 转移到 $f_n$ 。

设这 $k$ 个可重物品的集合为 $S$。因为 $k>j$ ，所以一定存在 $S$ 的子集满足其和是 $j$ 的倍数。（根据抽屉原理，$k+1$ 个前缀和模 $j$ 必有相同的）。我们可以用多个 $j$ 来替换这个子集，考虑到 $j$ 的定义，答案一定不劣。命题不成立。

将 $\forall 1\le i\le K(K-1)$ 的 $f_i$ 暴力转移。

复杂度 $O(K^3)$

Step 3

考虑扩展上一步的结论。对于 $i$ ，能否只从几个最小的 $\dfrac{b_j}{j}$ 的 $j$ 中转移过来。

可以证明，在保证正确性的情况下，对于状态 $i$ 每次从前 $m$ 小的 $j$ 中转移过来。其中 $m=\left\lceil\dfrac{2K^2}{i}\right\rceil-1$。

证明：

让 $P={j_1,j_2,…,j_m}$ 为前 $m$ 小的 $\dfrac{b_j}{j}$，$u_1,u_2,…,u_k$ 为转移到 $dp_i$ 的可重物品集 $S$。我们的核心思想是找到一个 $S$ 的非空子集可以被 $P$ 的一个子集线性表示出来。

Erdos and Graham (1972) 提出了一个定理：存在任意一个正整数序列满足 $p_1<p_2<…<p_n,\gcd(p_1,p_2,…,p_n)=1$ ，对于大于 $\dfrac{2p_{n-1}p_{n}}{n}-p_n$ 的正整数都可以用 $p$ 线性表示出来。

扩展这个定理，存在任意一个正整数序列满足 $p_1<p_2<…<p_n,g=\gcd(p_1,p_2,…,p_n)\not=1$ ，对于大于 $\dfrac{2p_{n-1}p_{n}}{ng}-p_n$ 的 $g$ 的倍数的正整数都可以用 $p$ 线性表示出来。

考虑应用这个定理，令 $g=\gcd(j_1,j_2,…,j_m)$ ，有 $g\le \dfrac{K-2}{m-1}$

现在我们需要找到 $S$ 的一个子集使得其和是 $g$ 的倍数并且把它用 $P$ 线性表示出来。一个不满足和为 $g$ 的倍数的最大序列和为 $(K-1)(g-1)$，相当于前 $g-1$ 个数放 $K-1$，有 $g$ 个余数不同的前缀和，后面任意前缀和都能找到相同的，所以一个满足和是 $g$ 的倍数的最大子集的和至少是 $i-(K-1)(g-1)$。考虑证明 $i-(K-1)(g-1)>\dfrac{2j_{m-1}j_{m}}{mg}-j_m$ 即可。

$g\le \dfrac{K-1}{m-1}<\dfrac{K}{\frac{2K^2}{i}}=\dfrac{i}{2K}<\dfrac{i}{K-1}\Longrightarrow\dfrac{i}{g}>K-1$

$\Longrightarrow\dfrac{i(g-1)}{g}\ge (K-1)(g-1)\Longrightarrow i-\dfrac{i}{g}\ge(K-1)(g-1)$

$\Longrightarrow i-(K-1)(g-1)\ge \dfrac{i}{g}\ge \dfrac{2K^2}{mg}>\dfrac{2j_(m-1)j_m}{mg}-p_j$

结合 Step2 ，根据调和级数，复杂度 $O(K^2\log K+q)$

Step 2.5

好像有一种做法是每次 $i$ 从 $\left\lfloor\dfrac{i-K}{2}\right\rfloor,\left\lfloor\dfrac{i-K+1}{2}\right\rfloor,\left\lfloor\dfrac{i-K+2}{2}\right\rfloor,…,\left\lceil\dfrac{i+K}{2}\right\rceil$

转移，复杂度是 $O(K^2\log N)$ 或者 $O(K^2\log^2N)$ 的。

~~因为我不会证明，所以说我开了多组询问把它卡掉了~~

我做的对吗！

造数据时的感想

事实上这个上界是跑不满的，所以可能什么乱搞也过了我也管不了。

我是有原则的，我不会打包。(flag)

2022.07.25