往年 NOI 做题记录

一个新坑，先把真题都刷一下大概就知道会考什么和难度怎么样了。

2013

向量内积

给定一个 \(n\) 个 \(m\) 维向量，求出一组不同的向量 \(p,q\) 使其内积（点乘）在模 \(k\) 意义下为 \(0\)。

\(k=2,1\le n\le 2\times 10^4, 1\le m\le 100\) 或 \(k=3,1\le n\le 10^5, 1\le m\le 30.\)

*哈希，矩阵，模

神奇套路题。主要思想：随机化哈希判断相等。原理：哈希值相同是真的相同的必要条件。

把向量想象成一个 \(n\times m\) 的矩阵 \(A\)，题目等价于 \(AA^T\) 在非对角线上存在 \(0\) 值。先考虑 \(k=2\) 的情况，只需判断是不是全是 \(1\) 即可。直接做是 \(n^2m\) 的，考虑再乘上一个 \(n\times 1\) 的列向量，可以优化到 \(O(nm)\)。这时只需判断最后的结果是否相同，随几次可以认为是对的。

\(k=3\) 时我们发现 \(1^2\equiv 2^2\equiv 3\pmod 3\)。于是我们把答案的矩阵每个数平方，对应到原来的矩阵即把向量 \(a_1,a_2,...,a_m\to a_1a_1,a_1a_2,...a_1a_m,a_2a_1,a_2a_2,...,a_2a_m,...a_ma_1,a_ma_2,...a_ma_m\)。所以可以 \(O(nm^2)\)。

code

矩阵游戏

*数列，费马小定理

先把单独一行拿出来看，设 \(f_1\) 是这一行的第一个元素，有 \(f_i=f_{i-1}*a+b\)。所以 \(f_m=f_1a^{m-1}+\frac{a^{i-1}-1}{a-1}b\)。如果不会的可以再去补一下高中数学。

然后设 \(g_i\) 是第 \(i\) 行的 \(f_m\)，有 \(g_i=(g_{i-1}c+d)a^{m-1}+\frac{a^{i-1}-1}{a-1}b\)，然后换个元又变成上面的式子，搞一搞就出来了。

但是 \(n,m\) 太大怎么搞？我们有一个费马小定理，\(a^{p-1}=1\pmod p,a<p\)。然后就可以降到 \(p\) 以下了。

坑点：注意 \(a=1\) 时等比数列求和公式不存在，需要特判，而次时又需要模 \(p\) 的 \(n,m\)，所以 \(n,m\) 两个都要模。

树的计数

*概率期望，树的遍历

首先我们发现我们要求的就是树的期望高度，然后根据期望的线性性我们可以把它分成几层。

观察到这个树的编号是无所谓的，我们可以给bfs序重新编号成 \(1\) 到 \(n\)，同时改变dfs序，这样不会有影响。

又发现bfs是按层来搞的，所以我们下一步就是分层，也就是把bfs划分成几个区间，每个区间在一层。

显然这不可能是随便分层，有一些限制。我们用一个数组来表示 \(i\) 和 \(i+1\) 直接有没有分割，如果为 \(0\) 即为不确定。

1，\(1\) 和 \(2\) 之间一定有分隔。这很显然。

2，假设 \(d_i\) 是 \(i\) 在dfs序中的位置。若 \(d_i>d_{i+1}\) 说明dfs的过程中先遍历到 \(i+1\) 再遍历到 \(i\)，而如果他们在同一层中则不可能（因为是按顺序排的），所以它们一定不在同一层中，答案加一。

3，还有这第三个限制，也是比较难想到的。假设 \(dfn_i\) 是dfs序，若 \(dfn_i+1<dfn_{i+1}\)，说明 \(dfn_{i+1}\) 的 深度最多比 \(dfn{i}\) 多1，所以 \(dfn_{i}\) 与 \(dfn_{i+1}\) 之间最多放一个分隔线，而枚举几种情况发现期间必有一条分隔线，所以这一段不得再有其他分隔线。

最后，如果还是可填可不填的答案就加0.5。

快餐店

*基环树，dp

这是一道类似于基环树直径的题。显然答案为直径除以2。

考虑暴力的做法，每次断一条环上边，然后找一下当前的直径，再取一个最小值即可。

优化也很简答，维护四个数组 \(h1,h2,g1,g2\) 分别代表到左端点（环上第一个点）前缀最大值，到右端点（也是环上第一个点（嘿嘿想不到吧，只不过饶了一圈））后缀最大值，以及前缀最大答案和后缀最大答案，不动的看一下图就懂了。

然后我们枚举断边\(i \rightarrow i+1\)，然后拿\(max(h1[i]+h2[i+1],max(g1[i],g2[i+1]))\)来更新答案，别忘了再和不在环上的链取最大。

书法家

*dp

从右往左，\(11\) 个 dp。注意细节就好。