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

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

2019 年 11 月 7 日 10:16

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

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

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

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

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

暂无评论

发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等，否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie，并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。（提交一次评论后，本提示将不再展示）