SkyWT

我们的征途是星辰大海。

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

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]=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换教室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,考虑到抛物线一定经过原点,则两个点可以确定一条抛物线,枚举 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!列队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...


Related posts

Nginx 通过反向 DNS 查询判断搜索引擎爬虫
发表评论
撰写评论