考试LIST [2021.06]

2021.06.06

$\texttt{Location:NOI2021}$

得分：$\texttt{80/300,Rank5}$。

[06.06]-错误

状态很差，明明 $\texttt{T1}$ 和 $\texttt{T3}$ 都是可做题，但是却完全没有想法。之前考过的几乎一样思路的题，却仍然没有从中得到启示。

[06.06]-部分正解

$\texttt{T1}$

考虑类似之前那道最小割的题，每次取出最优解，然后把剩下的解划分为若干类，从中再选择最优解。

因此把序列排序，显然最优解是取第一个。然后每次钦定选择/不选择某一个，然后拿堆维护即可。

$\texttt{T2}$

考虑 $\bmod\ 2$ 的性质。在 $\mathbb{F}_2$ 下有一些很好的性质——例如可以位运算、只有奇偶关系等。

先不考虑颜色的问题，怎么在 $\mathbb{F}_2$ 下算出所有完美匹配？由于给定的是邻接矩阵，因此试着考虑相关的计算方式。考虑矩阵行列式，对于矩阵 $A$，有：

$$ \det A=\sum_{p} (-1)^{c(p)} \prod_{i=1}^n A_{i,p_i} $$

其中 $p$ 是个排列，$c(p)$ 是排列的逆序对数。惊奇地发现，在 $\mathbb{F}_2$ 下，前面 $(-1)^{c(p)}$ 的系数就没有了！因为 $-1\equiv 1\pmod 2$。因此：

$$ \det A=\sum_{p} \prod_{i=1}^n A_{i,p_i} $$

若 $(i,j)$ 有边，则设 $A_{i,j}=1$，否则为 $0$。易于发现，一组完美匹配恰好会使得 $\prod_{i=1}^n A_{i,p_i}=1$！因此邻接矩阵行列式就是答案。

考虑加上颜色的限制怎么办。套路地将一种颜色变成 $+x$，这样就变成一个 $n$ 次多项式的每一项系数了。这样就可以插值了，时间复杂度 $\mathcal{O}(n^4)$，但是无法通过。

考虑 $\text{CRT}$。设置阈值 $B$，选出 $\left\lfloor\dfrac{n}{B}\right\rfloor$ 个 $B$ 次不可约多项式（随便选），把他们看做质数，先预处理在 $\bmod$ 一个不可约多项式意义下多项式的两两乘积，接着对他们分别求矩阵行列式，最后 $\text{CRT}$ 合并即可，后面可能需要一个 $\text{bitset}$ 来进行优化。

加上预处理，复杂度是 $\mathcal{O}(\dfrac{n}{B}\times 2^{2B}\times B^2+\dfrac{n^4}{B})$，实际上 $B$ 取 $9$ 或 $10$ 较好。

$\texttt{T3}$

考虑没有颜色怎么做。选出最小的右端点，然后把所有覆盖这个点的区间去掉，然后接着做。正确性显然。

加上颜色怎么做？每次删除的时候，每个颜色只选择一个区间。如果存在颜色相同且右端点相同的区间，那么将长度较长的区间的右端点向左边移动一位，否则两个区间会占用相同的点，正确性显然。这个东西，可以拿一堆 $\text{set}$ 和 $\text{priority\_queue}$ 来解决，比较繁琐。

时间复杂度 $\mathcal{O}(n\log n)$。

[06.06]-总结

$\texttt{T1}$

对于一类选择前 $k$ 优解的题，有类似的解题思路：求解最优解，然后强制钦定部分操作，然后继续求解局部钦定后的最优解。这个东西一般就可以用堆来维护，将问题转化为求最优解，代价是一个 $\log$ 的时间。

$\texttt{T2}$

行列式经常具有十分神奇的性质，往往可以解决十分多的组合意义题目，以后应该加入思考范围。

同时，本题给我们一个启发：对于类似的可以直接维护多项式的题，可能复杂度不够优秀，此时往往用插值来优化复杂度。当题目具有优秀性质（例如本题的 $\mathbb{F}_2$）时，也可以考虑另一种求解方式——$\text{CRT}$，这恰好体现了插值和 $\text{CRT}$ 的联系。

$\texttt{T3}$

对于限制多的题，先考虑限制少的情形，然后再一步一步加入限制来对原算法进行优化与调整。

2021.06.20

$\texttt{Location:NOI2021}$

得分：$\texttt{N/A}$。

[06.20]-错误

就没在做。

[06.20]-部分正解

$\texttt{T1}$

可以发现一直是 $\texttt{AA????BB????CC????DD}$ 的形式，$\text{dp}$ 三个空的长度即可。

剩下的鸽了。

2021.06.22

$\texttt{Location:NOI2021}$

得分：$\texttt{100/300,Rank8}$。

[06.22]-错误

$\texttt{T3}$ 花费了太长时间，导致没有写完应得的分。
$\texttt{T1}$ 前面的推导花费了过长的时间。
$\texttt{T2}$ 简单题，但竟然根本没开。

[06.22]-部分正解

$\texttt{T1}$

显然答案只和区间长度有关，设 $r-l=n$ 的答案为 $f(n)$。打表发现，$f(n)$ 的最优决策点是 $\text{highbit}(n)$，然后就可以把几个贡献分开考虑，然后算一些通项公式。需要注意的是 $\text{lowbit}(n)$ 需要特殊处理一下。

然后就只和 $1$ 的极长连续段相关了，直接 $\text{set}$ 维护段，加法减法的进位退位即可。

时间复杂度 $\mathcal{O}(m\log n)$。

$\texttt{T2}$

如果串是 $01$ 串，那么可以状压来做到单次 $\mathcal{O}(2^nnm)$。考虑将串转化为 $01$ 串，用 [WC2021] 表达式求值 的方式，算每个位置最后的值 $\ge x$ 的概率即可。那么枚举一个划分 $01$ 的分界点，再做 $\text{dp}$ 就是 $\mathcal{O}(2^nn^2m)$。

事实上，不需要枚举分界点，因为不同的分界点使得 $\text{popcount}$ 不同，所以可以一遍全部算完。复杂度 $\mathcal{O}(2^nnm)$。

$\texttt{T3}$

考虑矩阵乘法。$\min\text{-plus}$ 的矩阵可以很轻松地维护最短路径的情况，发现 $k$ 并不大，所以把矩阵加一维变成 $\text{A}_{i,j,k}$，事实上就表示从 $i$ 到 $j$ 的第 $k$ 短路的长度了。

先不考虑怎么乘法。在统计答案的时候，可以用 [NOI2020] 美食家 的 $\text{trick}$，先预处理 $A^{2^i}$，然后每次拿向量乘矩阵，这样总复杂度就是 $\mathcal{O}(\omega\log a+\dfrac{q\omega\log a}{n})$，其中 $\omega$ 是单次矩阵乘法复杂度。

做乘法的时候，要算 $i,j$ 的答案，首先枚举中转点 $m$，然后就是 $A_{i,m,?}$ 和 $B_{m,j,?}$ 的合并，求出最小的 $k$ 个。这个是简单的，可以拿堆直接先把每个中转点的最优解都放进去，然后不断用最小值扩展。

但是如果直接建堆的话，单次乘法是 $\mathcal{O}(n^3\log n+n^2k\log n)$，无法接受。但是用之前模拟赛的 $\text{trick}$，可以做到 $\mathcal{O}(n)$ 建堆，这样单次乘法复杂度就变成 $\mathcal{O}(n^3+n^2k\log n)$，总复杂度就是 $\mathcal{O}((n^3+n^2k\log n)\log m+(n^2+nk\log n)q\log m)$，可以通过。

$\mathcal{O}(n)$ 建堆：

对于数组 $\{a_n\}$，从后往前将元素依次下沉即可。

2021.06.23

$\texttt{Location:NOI2021}$

得分：$\texttt{210/300,Rank3}$。

[06.23]-错误

$\texttt{T3}$ 没有想任何东西......实际上是可以做的。
前面两题花了太长的时间。

[06.23]-部分正解

鸽

2021.06.24

$\texttt{Location:NOI2021}$

得分：$\texttt{290/300,Rank1}$。

[06.24]-错误

$\texttt{T1}$ 被卡精度了！

[06.24]-部分正解

$\texttt{T1}$

取个 $\ln$ 来比较大小。$\ln(n!)=\sum_{i=1}^n \ln i$，分段打表即可。

$\texttt{T2}$

直接 $\text{wqs}$ 二分。

$\texttt{T3}$

链修改用树剖，查询先建虚树，然后点分治一下，用树状数组维护答案即可。