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经过一番乱搞数学探究之后可以发现几个性质：$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乌龟棋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：$\Theta(N\ast K)$ 的贪心，每次求出每条边加速对答案贡献，取最大，做 k 次（如果写得不好可能被卡常……）。
1211Vigenè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货车运输LinkLCA 求路径上最短边。
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飞扬的小鸟LinkDP，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换教室LinkDP，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！列队LinkTo be continued...
1811铺设道路Link同 1321 积木大赛……
1812货币系统Link排序+完全背包。
1813赛道修建Link先二分赛道最小长度，然后 DFS，每个点搞个 std::set 上传即可。
1821旅行Link#60：从 1 开始每次走序号最小点。
#100：对于基环树，直接枚举一条边删除再重新求答案，取最终字典序最小的答案。非常变态的一点，这题数据极限卡常，洛谷评测机又很玄学，交了十几发，每次评出来结果都不一样，TLE 的点还各不一样……还好有个东西叫做评测鸭，还我公道 🌚
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！保卫王国LinkTo be continued...