NOIP 前杂题

· · 个人记录

I don't love Eason2009

Eason2009 说得对。我要开卷了。

祝愿我和 Eason2009 都可以在 NOIP2024 中考到理想的成绩。

对一题质量的评价是一个 [0,10] 中的可以表示成 0.5p 的浮点数，p 是自然数。难度以洛谷为准。

CF1712E

E1

绿。7.5

想一想，大多数时候 \text{lcm}(i,j,k) 是 ijk 级别的。所以大多数数对都是好的。我们尝试计算坏的数对，即 \text{lcm}(i,j,k)<i+j+k。

也就是 \text{lcm}(i,j,k)<3k。而 \text{lcm} 一定是 k 的倍数。也就是 \text{lcm} 要么是 k 要么是 2k。

先考虑是 k 的情况，则 j,k 都是它的因数，可以简单地 O(n\log n) 计算。

如果是 2k 的情况，打表发现一定是 (3,4,6) 或者是 (6,10,15) 的倍数，直接计算即可。 时间复杂度是 O(Tn\log n) 的。

E2

紫。7.5。

上一题的复杂度已经不可以接受了。考虑 2k 的情况，设 i=3l,j=4l,k=6l，那么 l\in [\lceil \frac l 3 \rceil,\lfloor\frac r 6 \rfloor]。取值和 (i,j,k) 双射。所以这里一共有 \max(0,\lfloor \frac r 6 \rfloor-\lceil \frac l 3 \rceil+1) 种。 (6,10,15) 同理。

另外一种是比较难计算的。考虑 c_i 表示 [l,r] 中 i 的约数的数量，答案就是 \sum^r_{i=l} C^2_{c_i}。

我们让约数贡献给原来的数，这样的话一定是小的贡献给大的。也就是说对于一个区间 [l,r]，从 r 开始一路往下，到 l 的时候统计的答案就是我们需要的东西。

将所有问询一起离线模仿莫队（扫描线？）维护即可。

P2566

紫。8

看到 d\le 9,n,m\le 10 不难想到状压。这类题目的一贯套路就是 nm2^d 种状态跑 dp/最短路。

考虑怎么刻画 ”在多边形内“ 这一条件。根据射线定理（此处不论证明，可以简单地用数学归纳法证明），从一点向右作射线交多边形奇数次则在多边形内。这是充分必要条件。如果射线与边相交则一个交点也不计。

考虑 2^d 的状态记录什么。记录每个关键点右侧的交点个数奇偶性。

考虑 S\to S' 的转移是怎样的。考虑什么时候点右侧会多一个交点。

假设从 (x,y)\to (x',y')，关键点是 (X,Y)，有以下的条件

则会多一个交点。不难计算 S\to S' 的过程。本质是一个最短路。考虑走回起点状态是 S 最短路是 dis_S，则答案就是

\max_S \sum_{s\in S} a_s - dis_S

枚举起点跑 spfa 即可。

时间复杂度类似 O(n^2m^22^d) 之类的，反正咋写都能过。

code

CF53E

紫。8

这个数据范围格外的小，n\le 10。本质要维护两个集合：已经加入树的结点集合，叶子节点集合。

后者是前者的子集，一共有 3^n 种状态，考虑如何状压转移。

每次转移时，以边为媒介转移。假设有一条边 (i,j)，i 已经在集合内，j 不在集合内。则可以将 j 加入树节点集合。

至于叶子节点集合。考虑 j 一定不与前面集合内的点有边，度数一定为 1，但 i 一定不会再是叶子节点（前面把 i 加入的节点和这条边，至少有两条）

所以 f_{S,s} 用边 (i,j) 可以转移到 f_{S\cup j,S\setminus i\cup j}。

直接转移即可。答案是 \sum_{popcount(s)=k} f_{2^n-1,k}。

code

P7984

紫。8。

首先考虑这道题的约束如何转化。

从 i 走到 1 和走到 n 的最短路分别是好求的。但是两条最短路合在一起并不是题目所求，因为会有算重的部分。去重也是不对的，因为这样的话不一定优。

我们考虑从 i 走到 1 后走到 n，先将所有算重的路都走完了，最后走到一个点 j，这个时候就是两条最短路合在一起了。这是一个最短路维护 dp 的形式。

本质上来说，假设 i 的答案是 f_i，则从 i 先走到 j，再从 j 分别走最短路是 f_j。那么更新的形式就是 f_i\leftarrow val(i\to j)+f_j。

直接更新即可。

时间复杂度是 \mathcal O(n^2) 的。

剩下是套路的，点和区间之间连边可以用线段树优化。时间复杂度 \mathcal O(n\log^2n)。别忘了线段树上也要反图。

code

P7986

蓝（虚低？）。8。

很喜欢一句话。看到蓝紫黑代码只有 500b 的时候有一种智商被侮辱了的感觉。

显然是 dp 题。考虑我们需要什么信息。算到第 i 个位置，剩余 j 个能被猜到的 \le x 的值和 k 个能被猜到的 >x 的值，上一次是 lo/hi。

hilo 的期望次数就是 j=x,k=n-x，上次是 hi 对应的状态。

设 dp_{j,k,0/1} 表示剩余 j 个能被猜到的 \le x 的值和 k 个能被猜到的 >x 的值，上一次是 lo/hi 的期望次数。

我们已经将无效的数排除在外，下一个有效的数在 j+k 种里任取。概率均为 \frac 1{j+k}。

看考虑能被猜到的 \le x 有 j 个，那能被猜到的一定是一个连续区间 [x-j+1,x]。而新猜一个数，一定是将区间左端点右移。假设新猜的这个数是 f(f\le x)，将会剩下 x-f+1 个可以选的数，而右侧的不变。

另外一边同理。用前缀和优化这个 dp 转移即可。空间卡的比较紧。

code

P8277

蓝。7。

这题本质上是 LIS 和 LDS 胡一起的一道题。

考虑硬拼接这两种做法。LIS 和 LDS 有一个做法是树状数组优化 dp。

那么，（以 LIS 为例） $$ dp_i=\max_{a_j<a_i} dp_j+1 $$ 用两棵权值树状数组做即可。 那有没有一种可能，就是说一个子序列不是最长，但是更有利于后面的转移，即不满足最优子结构性质。其实这是不可能的。我们不可能为了后面的转移而牺牲一的代价。 [code](https://www.luogu.com.cn/record/187422506) ## P2481 紫。8.5。 一个很 tricky 的点，把单调不降转化成加后缀一。 比如说一个数 $11133345556$ 可以被理解成 $11111111111+11111111+11111111+11111+1111+1$。 问题转化成了，将不超过 $9$ 个，不超过 $n$ 位的全 $1$ 十进制串拼接在一起，是 $p$ 的个数。 可是 $n=10^{18}$，任何形式涉及 $\mathcal O(n)$ 的算法都是不可接受的。 考虑转化成 $p$ 进制下的等价类。下文设 $F_x=\sum^{x}_{i=0} 10^i$。 如果有 $F_m=F_n$，我们可以通过组合数区分他们。 设 $G_i$ 表示 $\sum^n_{k=0} [F_k\bmod p=i]$。$G_i$ 可以通过找循环节算出来，是平凡的。 我们只用考虑放了几个 $\bmod p=i$ 的 $F_k$ 即可。假设放了 $s$ 个，则方案数为 $$ \binom{G_i+s-1}{s} $$ 设 $dp_{i,j,m}$ 表示目前考虑到余数为 $i$ 的 $F$（显然 $i<p$），此前已经放了 $j$ 个（显然 $j\le 9$），构成的数字 $\bmod p=s$ （显然 $s<p$）的方案数。 不难发现状态数为 $O(9p^2)$ 的。 转移的时候枚举当前的余数放几个，单次转移的复杂度为 $9$。 时间复杂度 $O(81p^2)$，做完了。 这题最关键的最 Tricky 的点就是转化成后缀 1。 [code](https://www.luogu.com.cn/record/188283940) ## P3188 紫。8。 很典的 trick。问题本身就是 01 背包，而 01 背包的最优复杂度是 $O(nW)$ 的，本题 $W$ 为 $2^{30}$，不可接受。 考虑特殊之处，也就是 $a\times 2^b$，其中 $a$ 很小。考虑把问题转化成 $2$ 的次幂意义下的，然后做分层 dp。 $dp_{i,j}$ 表示目前考虑到 $2^i$ 这一层，在这一层的 dp 中，剩余的空间还有 $j$ 的最大价值。 每一层内都是朴素的背包。在两层之前的转换怎么做？ - 从更高的一层转换过来 上一层剩余空间为 $j$，放到这层就变成了 $2j$。 - $W$ 所带来的 $W$ 这一位如果是 $1$，就自动获得一点空间。 直接做即可。时间复杂度 $O(na\log W)$。 [code](https://www.luogu.com.cn/record/188295290) ## P9129 紫。9。 太高妙了哥们。数位套区间 dp 第一次见。 不考虑 $q$，先只考虑一次问询。 典 Trick 是把 $[L,R]$ 转化成 $[1,R]-[1,L-1]$，我们只要明白怎么求 $[1,t]$，并且对于 $R$ 和 $L-1$ 各做一次就行了。 考虑怎么求 $[1,t]$，设 $dp_{i,j,k,0/1/2}$ 表示目前考虑到 $a_i$，形成的 $r-l+1$ 位整数和 $t$ 的第 $l$ 到 $r$ 位组成的十进制整数的大小关系。 如何转移？ 考虑往后延申一位： - 如果原来是大的，新的（状态）无论（老的状态）大小仍然是大的 - 如果原来是小的，新的无论大小仍然是小的 - 如果原来是一样的，新的与加入的那一位大小一样。 考虑往前延申一位： - 如果加入的数是大的，新的（状态）无论（老的状态）大小都是大的 - 如果加入的数是小的，新的无论大小都是小的 - 如果加入的数一样的，继承老的的大小关系。 从当前位开始：$[i,i]$ 区间可以选择操作一或操作二，就是这一位的大小，记录。 答案是什么呢？如果位数不足 $d$，则大大小小都可以。答案是 $\sum^d_{j=2} \sum^2_{k=0} f_{n,j,d,k}$； 反之，只能是小或等于，答案是 $f_{n,1,d,0}+f_{n,1,d,1}$。 每次问询 dp 一遍，时间复杂度 $O(qn\log^2B)$，本来就常数大，难以接受。 不难发现，最后的问询是稠密的（甚至一共只有 $4.5\times 10^4$ 个本质不同的问询，但有 $5\times 10^4$ 次问询），不难猜测应该直接把所有答案算出来）推 dp 数组的过程中已经指定了前缀，只要枚举一下后缀即可。最后直接前缀和即可。 时间复杂度是 $O(n^2\log^2B)$。 [code](https://www.luogu.com.cn/record/188304788) ## P6669 紫。8。 很典的题啊。我怎么没做过。 考虑 Lucas 定理。 $$ \binom n m=\binom{\lfloor \frac n k \rfloor}{\lfloor \frac m k \rfloor}\times \binom{n\bmod k}{m\bmod k} \pmod k $$ 类似于下取整的东西自然想到进制。本质上也就是 $n,m$ 进制意义下的每一位的组合数乘起来。 假设 $n=(\overline{a_1 a_2 a_3 a_4 \cdots a_f})_k$，$m=(\overline{b_1 b_2 b_3 b_4 \cdots b_f})_k$，则 $$ \binom{n}{m}=\prod^f_{i=1} \binom{a_i}{b_i}\pmod k $$ 考虑 $\binom n m \equiv 0\pmod k$ 的充要条件即为，存在 $i$ 满足 $\binom{a_i}{b_i} \equiv 0 \pmod k$。 而 $k>a_i,b_i\geq0$，$k$ 又是素数，一定无法被分解出来。所以要求就是 $b_i>a_i$。 有了上面这些转换，就可以转化这道题了： > 求数对 $(i,j)$ 满足以下条件： > > - $0\le i \le n
  • 0\le j \le \min(i,m)

直接数位 dp 即可。目前考虑到 k 进制下第 p 位，是否存在 i 比 j 大，i 是否前面都与 n 一样，j 是否前面都与 i 一样，j 是否前面都与 m 一样。

直接记忆化实现即可。状态一共有 2^4\times \log_k n 个。每一位转移的复杂度是 O(k^2) 的，总复杂度即为 O(T2^4 \log_k n k^2) 。

code

ARC107D

蓝。8.5。

考虑最小的 2^{-i} 是 2^{-f}。

不难发现，想让 2^{-f} 变成正整数的一部分，必须是 2^{-f}+2^{-f}+2^{-f+1}+\cdots +2^{-1}=1。

这至少需要 f+1 个数。所以我们用到的最小的 2^{-f} 不可能小于 2^{-n+1}。

从小往大考虑，假设我们有 a_0 个 1，a_1 个 2^{-1}，a_2 个 2^{-2}，以此类推。

我们可以理解为：加 a_{n-1} 个 1，全局除以 2，再加 a_{n-1} 个 1，全局除以 2，……，全局除以 2，加 a_{0} 个 1。

这时候就做完了啊。考虑目前加了 i 个数，和为 j 的方案数。dp_{i,j} 可以通过加一个 1，也就是 dp_{i,j-1} 转移而来，也可以通过全局除以 2，也就是 dp_{i,j\times 2} 转移而来。

考虑最后的集合和操作序列一一对应。根据上文分析，操作序列长度不超过 n 组（最长的时候就是一次加一次除一次加一次除，这种情况也能在 n 次 dp 转移中计算完），这么做不重不漏。

code

P3643

紫。8。

考虑一个朴素的 dp。dp_{i,j} 表示考虑到第 i 所学校，且第 i 所学校选 j 个人的方案数。

显然 j\in [L_i,R_i] 时，dp_{i,j} 会从所有 k\le i,f\le j 的 dp_{k,f} 转移过来。

但是 j 的值域是 10^9 的，不可接受。

考虑离散化。很明显，这个离散化不是无损的。将所有端点处理出来之后，整个值域被分成了 O(n) 个更小的子区间。例如 [1,4],[2,5],[4,6] 可以被分成 [1,2],[2,4],[4,5],[5,6]。[1,4] 等价于 [1,2]\cup[2,4]。

dp 状态相应改变。设 dp_{i,j} 表示考虑到第 i 所学校，第 i 所学校是最后一个选第 j 个区间的。

考虑上一个选最后一个区间的是谁，假设是 dp_{k,f}，则从 [k+1,i] 这一部分，要么都选这个区间，且不大于 dp_{i,j}，要么为 0。

引理是：值域 [0,L] 选 n 个数，非 0 部分单调递增的方案数是 \binom{L+n}{n}。

这个东西是容易证明的，只需要把选数过程揪出来考虑，考虑一个操作序列即可。

然后这个 dp 就迎刃而解了。