NOIP 提高组 题解聚合((伪)完结撒花!)

/ 0评 / 12

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 经过一番乱搞数学探究之后可以发现几个性质:xb_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]=0F[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,考虑到抛物线一定经过原点,则两个点可以确定一条抛物线,枚举 maski,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...

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://old.skywt.cn/posts/noip-s-solution/


评论已关闭。