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

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...|