2021 年牛客 NOIP 赛前集训营(第二场) 考试总结

· · 个人记录

期望得分：100 + 0 + 50 + 5 = 155

实际得分：100 + 0 + 40 + 5 = 145

T1 串串串

题意：

你有两个长度分别为 n , m 的 01 串 S ,T。

有 Q 次询问，每次询问给出 l_1 , r_1 , l_2 , r_2 ，其中 r_1 - l_1 + 1 = r_2 - l_2 + 1 ，令 a = S[l_1 ... r_1] , b = T[l_2 ... r_2] ，你需要求出 a_i \not = b_i的位置个数对 2 取模的结果。

对于 100\% 的数据， 1 ≤ n, m, q ≤ 2 × 10^5， 1 ≤ l_1 ≤ r_1 ≤ n，1 ≤ l_2 ≤ r_2 ≤ m。

思路：

乍一看似乎不可做，但是有一个 对 2 取模 的性质，于是可以发现，交换 a 中任意两个位置，答案都是不变的，交换 b 中任意两个位置也一样。

那么我们可以将 a , b 中的 0 放在前面， 1 放在后面，答案即为 a 中 1 的个数和 b 中 1 的个数之差对 2 取模的结果。

时间复杂度 O(n + m + q) 。

小结：

好题。注意性质便可以推出。

T2 方格计数

题意：

在左下角是 (0,0) ，右上角是 (W,H) 的网格上，有 (W + 1) × (H + 1) 个格点。 现在要在格点上找 N 个不同的点，使得这些点在一条直线上。并且在这条直线上， 相邻点之间的距离不小于 D 。求方案数模 10^9 + 7 。

对于 100\% 的数据，1 ≤ N ≤ 50，1 ≤ W,H,D ≤ 500，1 ≤ T ≤ 20。（T 为数据组数）

思路：

网格图上，一条直线上的两个点， \gcd(|x_1-x_2|,|y_1-y_2|)-1 就是直线上两点间点的数目。

证明：

令 x=x_1-x_2 ， y=y_1-y_2 ， d=\gcd(x,y)

设 p ， q ，满足： x=pd,y=qd

令直线上某一点为 (a,h)

由相似三角形可得：

\dfrac{a}{x}=\dfrac{h}{y}

则：

a=\dfrac{hx}{y}=\dfrac{hpd}{qd}=\dfrac{hp}{q}

那么 ans 也就是对于 1≤h≤y 来说，有多少个 a \in Z 。

即：

ans=\displaystyle\sum_{i=1}^{y}(ip\equiv0\mod q)

显然 \gcd(p,q) =1 ， 则：

\begin{aligned}ans &=\displaystyle\sum_{i=1}^{y}(i\equiv0\mod q)\\ &= \displaystyle\sum_{i=1}^{qd}(i\equiv0\mod q)\\ &=\displaystyle\sum_{i=1}^{d}1\\ &= d \\ &= \gcd(x,y)\end{aligned}

至此，证毕。

又有：

任意两个元素间隔大于等于 k 的组合数，在 A 中选 B 个位置，要求每相邻位置要隔出至少 C 个空位置的方案。

相邻的有 B-1 对，所以空 (B-1)C 个，去掉这些位置就变成普通的选位置了，答案就是

\dbinom{A-(B-1)C}{B}

于是考虑枚举两个端点，强制两个端点选，令 a 为两个端点之间 x 轴上的距离，b 为两个端点 y 轴上的距离，那么这里面可以选择的点的个数有 g=\gcd(a,b) 个。我们要求 N-2 个小球（强制两个端点选），需要放到 g 个盒子里，相邻两个小球的盒子编号差至少为 k，方案数为

\dbinom{N-2}{g+1-2k-(N-3)(k-1)}

时间复杂度 O(TW^2H^2)

考虑如何优化。发现对于相同的 a ，b 方案数也是相同的，考虑枚举 a ，b ，最后再乘个 (W-a+1)×(H-b+1) 就好了。

时间复杂度 O(TWH) 。

小结：

对于计算几何的题，我一概是难以想出来的，即使是想出来，也难写出来，回头看些博客。

考试时想打暴力发现没时间了，因为 T3 花了很久时间，中途题意还理解错了。

T3 树数树

题意：

牛牛有一棵 n 个点的有根树，根为 1 。

我们称一个长度为 m 的序列 a 是好的，当且仅当：

  1. 对于任意 i\in (1,m]， a_i为 a_{i-1} 的祖先或 a_{i-1} 是 a_i 的祖先；

  2. 对于任意 1 ≤ i < j ≤ m , a_i ≠ a_j 。

你需要帮助牛牛求出最长的序列长度。

数据满足：

对于 10\% 的数据，n≤10 。

对于 20\% 的数据，n≤2000 。

对于 20\% 的数据，给出的树为链，其中 1 号点的度数为 1。

对于 10\% 的数据，给出的树为菊花，其中 1 号点的度数为 n - 1。

对于 10\% 的数据，给出的树为完全二叉树。

对于 100\% 的数据，1 ≤ T ≤ 5，2 ≤ n ≤ 10^5，1 ≤ u, v ≤ n，u ≠ v，输入保证是一棵树。

思路：

可以发现，一个节点 u 可以将子树中的两个序列拼成一个序列，且我们在处理完 u 的父亲的时候 u 的状态已经不用管了，我们可以用堆维护出 u 和 u 的子树中的点能组成的序列，转移相当于是将所有子树的堆合并成一个，然后取出其中最大的两个合并成一个。

可以用启发式合并或者可并堆维护这个过程。

时间复杂度 O(n\log^2n)∼O(n\log n)

小结：

根据考试时的大样例推出了三个特殊性质的答案，然后理解了题意之后暴搜写挂了，但是性质的分数拿到了，还算可以。

T4 序列

题意：

定义一个数的 se 序列为其一个数位和为 10 的子段。

举个例子，1145141919810900 的所有 se 序列为

定义一个数是 ll 数，当且仅当它的每一个数位都在至少一个 se 序列中。

举个例子，1145141919810900 不是 ll 数，因为第一个 1 和 8 不在任何一个 se 序列中，而 23541901 是一个 ll 数。

现在牛牛想随机生成一个 [0,10^n) 范围内的数送给牛妹。具体地说，每一位上的数字为 i 的概率为 a_i，且保证 \displaystyle\sum_{i=0}^{9}a_i=1 。

现在牛牛想知道这个数为 ll 数的概率。

数据满足：

对于 5\% 的数据，n=1；

对于 5\% 的数据，n=100；

对于 20\% 的数据，n=3000；

对于另 30\% 的数据，n≤10^{18}，且保证任意 i\in [0,9],a_i=\dfrac{1}{10}

对于 100\% 的数据，1≤n≤10^{18}，任意 i\in [0,9],0≤b_i<10^9+7

思路：

朴素的数位 DP 的复杂度为 O(n) 。

从前往后添加数字。考虑到某一个时刻，如果存在一个位置不在任何一个 se 序列中，且其后数位和 (包括这一位) ≥ 10，则这个数字就是不合法的，因为继续添加数字不可能影响到这一位。那么状态中不妨记录最长的数位和 ≤ 9 的后缀以及不在任何一个 se 序列中的数字位数 (显然这些数字组成一个后缀)。

先不考虑数字 0。根据隔板法，数位和 ≤ 9 的数字并不多。观察到不在任何一个 se 序列中的数字位数首先不会大于最长的数位和 ≤ 9 的后缀的位数，所以状态数只有区区 2816。

至于转移，枚举在末尾添加的数，暴力判断是否合法以及转移到的状态即可。

考虑数字 0。如果把 0 记进状态中，状态数就会爆炸。发现 0 不会被任何一个 se 序列覆盖，当且仅当其左右两个数都不会被任何一个 se 序列覆盖。换言之，如果转移时发现存在一个 0 不合法，那么也必定存在一个非零的数不合法。即我们在状态中可以完全不考虑 0，通过加 0 转移到下一位时不改变状态。

我认为我只需要掌握这30分即可，正解的算法还没学到。

小结

想到数位 DP ，但是不会维护状态，也忘了模板怎么打，只能说是非常愚蠢了。回去要把 DP 的板子稍微复习一下。

平凡的起起落落

漂浮的因果对错

都可以向风诉说