NOI2020网络同步赛体验记

比赛

$Day1$

勤勤恳恳的扣了 114 分，取模错误 wa + 字母打错，fst 成 82 分。。。好难受啊

整整 32 分啊。这如果是联赛，谁担的起呢。

$Day2$

勤勤恳恳的抠了 ？分（对我自己都不确定正确性），民间数据还没出（出了也不测 qvq）

出成绩了

108

【此处应有题解】

来补了。

$D1T1. 美食家$

我想到矩阵快速幂了！写出 $5n$ 个点的转移柿子了！甚至想到预处理 $2^i$ 的矩阵、行向量去乘是 $n^2$ 的了！

但我没写出来。。。好吧，不会就是不会，复杂度是 $O((5n)^3 log T + (5n)^2 log T \times K)$。你别看他有 4e8，人家是 O(能过) 耶= =

upd：考场代码分段乘的时候额外贡献加错位置了= = 我哭

$Code$

$D1T2. 命运$

链接

$D1T3. 时代的眼泪$

咕咕

$D2T1. 制作菜品$

先将 $d$ 排序。

发现大数据范围里有 $n - 2 \leq m$，部分分 $m = n - 1$ 似乎很有未来。

考虑部分分 $m = n - 1$，$d_1$ 一定是 $< k$ 的，为什么呢？如果 $d_1 \geq k$, 那么 $\sum d_i \geq n times k > (n - 1) times k = m \times k = \sum d_i$，矛盾。每次削掉第一项，$n$ 转化成 $n - 1$，一定能够构造出来。同时 $d_1 + d_n \neq k$，用反证法也可以证明。

考虑 $m \geq n$ 时，$d_n \geq k$，证明方法同上面类似。于是将 $d_n -= k$，就转化成了 $m = n - 1$ 的问题

最后一步！$m = n - 2$ 怎么搞。。可以证明，$m = n - 2$ 有解的充要条件是可以划分为两个 $m = n - 1$ 的子问题。充分性很好证，必要性就比较妙：考虑一个 n 个点的图，菜品视为边，那么最多只有 n - 2 条边，不会连通，此时必然存在至少两个连通块是树的形态——为什么？如果是环，边就不够用了。

实现的话，设 $S$ 是分出来的集合之一，$sz = |S|$, 那么 $\sum\limits_{i \in S} d_i = (sz - 1) \times k$，$\sum\limits_{i \in S} (d_i - k) = -k$，这是个 dp，$f[i, j]$ 表示前 i 个任意取能否使得总和为 j，bitset 维护, $O(\frac{n \times (n \times k)}{w})$

$Code$

$D2T2. 超现实树$

这题好 AT 的样子，结果是道结论题（脑子不好 死也想不出啊。。

大佬思路

“几乎完备”这种关系可以传递。太妙了吧！！！！！！！！！

$Code$

$D2T3. 翻修道路$

咕咕