NOIP 提高组题解聚合（（伪）完结撒花！）

This blog post is only available in Simplified Chinse.

2019.11.07 Upd：其实不是真的完结了，有些题目实在搞不动 QwQ 还有太多薄弱的地方要补了，这个项目就先到此为止吧。今年联赛比完可能就要退役了，那些 To be continued 的格子可能不会 be continued 了更多伤感的话还是在退役总结里写吧……

争取 CSP 之前把这个坑填完毕竟以后没有 NOIP 了（大雾

题目编号示意： 2010 及以前 XY0Z 代表 20XY 年 NOIP tZ； 2011 及以后 XYZW 代表 20XY 年 NOIP dayZ tW。

~~题目名加粗表示此题为毒瘤，带感叹号表示为大毒瘤~~

Number	Name	Link	Solution
0901	潜伏者	Link	模拟。
0902	Hankson 的趣味题	Link	经过一番乱搞数学探究之后可以发现几个性质： $x$ 是 $b_1$ 的因数并且是 $a_1$ 的倍数，并且满足 $\gcd(\frac x {a_1},\frac {a_0} {a_1})=1,\gcd(\frac {b_1} x,\frac {b_1} {b_0})=1$ 。所以只需要进行 $\sqrt{b_1}$ 的枚举并 check 即可。理论上应该带个 $\log$ 的亚子……
0903	最优贸易	Link	先反建边反向 DFS 刷出哪些点能走到终点，然后乱写个 SPFA 求 1 到 $i$ 路径上最小值，就过了……
0904	靶形数独	Link	非常重要的一个优化是：先填 0 的数量少的行，因为 0 的数量越少，满足的分支就会越少。然后直接 DFS 填数字就好啦。我以为还要进行一番精致的剪枝，没想到直接这么写就过了，还跑得很快……Code
1001	机器翻译	Link	队列模拟。
1002	乌龟棋	Link	DP，`F[i][j][k][t]` 表示使用四种卡片数量的最大得分。
1003	引水入城	Link	先 DFS 检查是否满足；如果满足：预处理，记 `pii F[i][j]` 为 (i,j) 格有水，最后一行会有水的区间，然后直接 DP。
1004	关押罪犯	Link	二分枚举答案，并查集 check。
1111	铺地毯	Link	模拟/暴力。
1112	选择客栈	Link	直接预处理几个数组，暴力枚举。
1113	！Mayan 游戏	Link	大搜索+剪枝，十分恶心。To be continued...
1121	计算系数	Link	直接求杨辉三角。
1122	聪明的质监员	Link	两次二分，二分枚举参数 W，用前缀和 check。
1123	观光公交	Link	#60：DP。 #100： $\Theta(N\ast K)$ 的贪心，每次求出每条边加速对答案贡献，取最大，做 k 次（如果写得不好可能被卡常……）。
1211	Vigenère 密码	Link	模拟/暴力。
1212	国王游戏	Link	推出一个小结论：按 $a_i\ast b_i$ 排序处理即可。要写高精度。
1213	开车旅行	Link	思维难度略大，预处理难想。排序，双向链表预处理出最小点和次小点。然后倍增：`F[i][j]` 表示从 i 城市出发，每人驾驶 $2^j$ 次后到达的城市，`A[i][j]` 和 `B[i][j]` 分别表示 A/B 行驶的路程。Code
1221	同余方程	Link	拓展欧几里得。
1222	借教室	Link	二分枚举从开头开始有多少订单可以满足即可。
1223	疫情控制	Link	二分答案，check 时可以发现对于每个军队，在时间允许的情况下尽量往上移可以覆盖到更多的叶结点，那么如果能移到根就「闲置」在根节点，否则就停留在能移动到的深度最小的点。剩下在根节点待命的军队则全部驻扎在根节点的儿子为最优，那么可以贪心匹配需要驻扎的根的儿子。代码略复杂。推荐题解
1311	转圈游戏	Link	快速幂取模。
1312	火柴排队	Link	不难发现上下排序后对应火柴就是最优答案（证明： $(x+y)^2>x^2+y^2$ ），假设只安排第二个序列，则构造出第 i 个元素安排后的位置序列，求逆序对即可。
1313	货车运输	Link	LCA 求路径上最短边。
1321	积木大赛	Link	求递减部分累积高度就是（最少）区间右端点个数。
1322	花匠	Link	最长波动序列，递推求解。
1323	华容道	Link	#60：记空白格子和指定格子的位置为一个状态，记为四元组 `(x1,y1,x2,y2)`，暴力乱移白格子，记搜，时间复杂度 $\Theta((n\ast m)^2\ast q)$ （强行优化是不可以的）。 #100：可以发现有用的状态只有空白格子在指定格子周围的状态，即每个指定格子的坐标有 4 种有用状态，则一个状态表示为 `(x,y,0/1/2/3)`，可以将状态抽离、连边，转化为图论问题，跑 SPFA 就行啦。代码很麻烦。Code
1411	生活大爆炸版石头剪刀布	Link	直接模拟。
1412	联合权值	Link	在给出的树上对于每个点分别考虑其儿子和父亲、儿子和儿子的联合权值。
1413	飞扬的小鸟	Link	DP，`F[i][j]` 表示横坐标为 i，高度为 j 的最小点击次数。向上跳就完全背包，向下降就直接转移。
1421	无线网络发射器选址	Link	暴力枚举。
1422	寻找道路	Link	反建边 BFS 找可用点，然后将可用的点重新构图跑最短路。
1423	解方程	Link	#50：枚举 $x$ ，每次高精度 $\Theta(N\ast len^2)$ 地检查。 #70+：秦九韶算法： $a_0+a_1x+a_2x^2+\dots+a_nx^n=(\dots((a_nx+a_{n-1})x+a_{n-2})x\dots+a_1)x+a_0$ 。不用写高精度，直接多取几个质数（2～4 个）取模验证。（洛谷上此做法可 AC……） #100：当模数为 $tt$ 时， $f(x)=f(x+k\ast tt)$ 。根据此性质优化 #70 算法可达满分。
1511	神奇的幻方	Link	题目太直白了，直接按照题目描述做……
1512	信息传递	Link	找图中最小环，拓扑排序后直接并查集找最大联通块。
1513	！斗地主	Link	又一道变态的大模拟/大搜索题。To be continued...
1521	跳石头	Link	二分。
1522	子串	Link	#70：`F[i][j][k]` 表示 A 串走到 i 位，B 串匹配到 j 位，已经选择 k 个子串的方案数，则状态转移为：`F[i][j][k] <- F[i-len][j-len][k-1], F[i-t][j][k]`，条件 `A[i-len][i] = B[j-len][j]`。可以用字符串哈希判断条件，滚动数组，时间复杂度 $\Theta(N\ast M\ast K)$ 。 #100：改变一下 DP 的定义，`F[i][j][k][0/1]`，增加一维表示 `A[i]` 是否参与匹配，这样就不用枚举后缀去字符串哈希比较了，可以通过上一状态传递，省去一个 $\Theta(M)$ 的枚举。转移方程：1）`A[i]=B[j]` 时：`F[i][j][k][1] <- F[i-1][j-1][k-1][0/1] + F[i-1][j-1][k][1]`，`F[i][j][k][0] <- F[i-1][j][k][0/1]`；2）`A[i]!=B[j]` 时：`F[i][j][k][1]=0`，`F[i][j][k][0]` 同上。
1523	运输计划	Link	#50～60：暴力枚举边清零， $\Theta(m^2\log n)$ 。 #100：首先在树剖中可以把边权化为点权；另外可以发现一个性质：由于答案由最长路径决定，要清零的边必然在最长路径上。进一步可以发现，清除一条边 $e$ 后可能的最大路径只有两种情况：（1）之前的最长路径减去 $w_e$ ；（2）不包含 $e$ 的最长路径。对于后者可以进行预处理：设 $mx(e)$ 为不经过 $e$ 这条边的最长路径长度。对于一条路径考虑，设其包含边集 $E$ ，那么 $E$ 中的边更新后这条路径也会更新，也就是说应该用这条路径长度去修正 $E$ 的补集的 $mx$ 。对于这条路径（树剖后查找）对应线段树上的若干区间（即代表了集合 $E$ ），存储、排序，取补集修正即可。最后，枚举清零的边，在两种情况中取最大值修正答案。时间复杂度 $\Theta(n+m\log n)$ 。Code ~~也就 200+ 行，不多不多……~~ 似乎会被极限卡常，开 O2 才过……（然而 UOJ 上就是怎么编译优化都过不去的 QwQ）应该还有更优做法。
1611	玩具谜题	Link	模拟。
1612	！天天爱跑步	Link	#40： $\Theta(n^2)$ 暴力，树退化成链的情况可以用线段树，用一种类似差分的写法。 #100：To be continued...
1613	换教室	Link	DP，`F[i][j][0/1]` 表示上完了前 i 节课，已经申请 j 次，最后一次有/没有提交申请，耗费的体力值期望最小值。状态转移需要考虑上一状态申请通过的概率。Code
1621	组合数问题	Link	先预处理出组合数和前缀和，然后暴力累计。
1622	蚯蚓	Link	#85：`std::priority_queue`， $\Theta(m\log(n+m))$ ，会 T 飞。 #100：每次选出一个最大的，可以看成将其长度减去 q 再分成两半（这样第 i 次过后就可以长度统一增加 `i*q`，即忽略长度随时间的增长），可以发现每次选出要切割的最长的蚯蚓长度递减，则维护三个队列，分别表示初始蚯蚓、切出的第一段、切出的第二段，每次取三个队列首最长的切割即可。
1623	愤怒的小鸟	Link	状压 DP，`F[mask]` 表示消灭的猪集合是 `mask`，考虑到抛物线一定经过原点，则两个点可以确定一条抛物线，枚举 `mask` 和 `i,j`，预处理这条抛物线能「顺便」消灭多少猪。时间复杂度 $\Theta(2^nn^2)$ 。
1711	小凯的疑惑	Link	#60：完全背包。 #100：~~找规律~~发现答案就是 $a\ast b-a-b$ 。推荐证明。
1712	时间复杂度	Link	小模拟，只要细心一点就好了。
1713	逛公园	Link	#30： $K=0$ 的数据，就是最短路计数，还保证没有 0 边。DP 即可。 #70：考虑到 $K$ 只有 50，可以定义 `F[i][j]` 表示走到第 i 个点，路径长度比最短路多了 j 的方案数。先预处理一遍最短路，然后跑这个 DP 即可，`F[u][j] <- F[v][j+(dist[u]+w(u,v)-dist[v])]`，要先按 `dist` 排个序（所以有 0 环的就做不了）。时间复杂度 $\Theta(k\ast m)$ 。 #100：先反建边跑最短路，然后在 #70 的基础上记忆化搜索，搜索的时候记录哪些点在递归栈里，可以实现对 0 环的判断。
1721	奶酪	Link	$\Theta(n^2)$ 枚举+并查集。
1722	宝藏	Link	$n\le 12$ ，显然可以用状压，枚举起点， $F(mask)$ 表示打通状态为 $mask$ 的最小代价。 $n$ 太小了，好像怎么搞都可以……（这题好像在 ZS 那里就做过了 =_=）
1723	！列队	Link	To be continued...
1811	铺设道路	Link	同 1321 积木大赛……
1812	货币系统	Link	排序+完全背包。
1813	赛道修建	Link	先二分赛道最小长度，然后 DFS，每个点搞个 `std::set` 上传即可。
1821	旅行	Link	#60：从 1 开始每次走序号最小点。 #100：对于基环树，直接枚举一条边删除再重新求答案，取最终字典序最小的答案。非常变态的一点，这题数据极限卡常，洛谷评测机又很玄学，交了十几发，每次评出来结果都不一样，TLE 的点还各不一样……还好有个东西叫做评测鸭，还我公道 :new_moon_with_face:
1822	填数游戏	Link	#65：对于 $n\le 3$ 的情况，每种 $n$ 都可以单独写个 DP 解决。（其实 $n=2$ 的情况答案就是 $4\ast 3^{n-1}$ ……） #100：其实是个找规律题……有一个非常重要的性质：如果 $(x-1,y)$ 和 $(x,y-1)$ 格子填的数字一样，那么以 $x,y$ 为左上角的右下角子矩阵对角线上填的数字都要相同。~~根据这个性质可以较为轻松地疯狂手模找规律啦~~ $Ans(n,n)=\frac{83\ast 8^n+5\ast2^{n+7}}{384},Ans(n,m+1)=3\ast Ans(n,m)$ 。证明很麻烦。推荐这篇题解
1823	！保卫王国	Link	To be continued...

11/7/2019

NOIP 提高组题解聚合（（伪）完结撒花！）

Post a New Comment

11/7/2019

NOIP 提高组 题解聚合（（伪）完结撒花！）

Post a New Comment

NOIP 提高组题解聚合（（伪）完结撒花！）