[TOP] NOIP 提高组 题解聚合

/ 0评 / 2

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

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

Number Name Link Solution
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 大搜索+剪枝,十分恶心。
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 又一道变态的大模拟/大搜索题。
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
1611 玩具谜题 Link
1612 天天爱跑步 Link
1613 换教室 Link
1621 组合数问题 Link
1622 蚯蚓 Link
1623 愤怒的小鸟 Link
1711 小凯的疑惑 Link
1712 时间复杂度 Link
1713 逛公园 Link
1721 奶酪 Link
1722 宝藏 Link
1723 列队 Link
1811 铺设道路 Link 同 1321 积木大赛……
1812 货币系统 Link
1813 赛道修建 Link
1821 旅行 Link
1822 填数游戏 Link
1823 保卫王国 Link

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


发表评论

电子邮件地址不会被公开。 必填项已用*标注