2019考前复习记录专帖

· · 个人记录

洛谷题目页剩余页数: \color{Red}{45} \ \ \ 总页数 \color{Red}{81}

算法进阶指南已经复习的页数区间：\color{Red}{1\sim 139}

信息学奥赛一本通·提高篇已复习区间：

个人洛谷博客复习到剩余 \color{Red}{7} 页

洛谷题目\color{Red}{81 \Rightarrow 75}

重要题目：

P1650 田忌赛马（很难想的贪心，也可以DP）

P1120 小木棍 ［数据加强版］（毒瘤搜索，打算以后参见算法进阶复习）

P3386 【模板】二分图匹配（匈牙利算法）

每次清空vis数组

P3958 奶酪（应该使用\text{unsigned long long}）

\color{Red}{\text{LONG\_LONG\_MAX的极限大约是}9.22 \times 10^{18}}

UVA1395 苗条的生成树 Slim Span（最小差值生成树，加强版见P4234 最小差值生成树）

P3690 【模板】Link Cut Tree （动态树）

今天来复习LCT板子，发现连模板都要WA了，结果还是由于我错误的交换了if语句里的判断顺序

洛谷题目\color{Red}{81 \Rightarrow 72}

P1430 序列取数

还记得这是人生第一道紫题，想当时我连普通DP理解的都不够深入，怎么懂得了DP优化

现在自己可以独立秒切了

注意区间DP的两种枚举方式

P2831 愤怒的小鸟

状压DP裸题，注意为了避免等效冗余枚举，只需要找到二进制中第一个为0的位置即可

注意a < 0

P1850 换教室(Review)

其实它利用了期望的线性性的性质：所有路程的期望等于每一条边的期望和

P3959 宝藏（状压DP）

跟着yxc大佬写状压DP

POJ - 2559 Largest Rectangle in a Histogram

单调栈复习打卡，发现其实不用像书上写的方法那样搞，还是求出每个矩形左右第一个比它小的位置即可

ybt1691：文章评分

P5019 铺设道路(Review)

其实这道题可以用差分来做，可以说和进阶指南的P21上的例题很相似

P3078 [USACO13MAR]扑克牌型Poker Hands

这竟然是NOIp这两年的原题出处

ZROI#1126. 十一成都B班-铺设道路

P4170 [CQOI2007]涂色

思路不好想的DP

P3847 [TJOI2007]调整队形

和CQOI2007 涂色很像，不太好想的DP，关键还要观察到1, 2两种操作都可以转换成3操作

P1030 求先序排列

二叉树遍历复习

P3381 【模板】最小费用最大流

费用流复习打卡

P3383 【模板】线性筛素数

P1516 青蛙的约会

x = \dfrac{c}{d} x_0 + k \dfrac{b}{d} y = \dfrac{c}{d} y_0 - k \dfrac{a}{d}

其中 k \in \mathbb{Z}

P3375 【模板】KMP字符串匹配

P3919 【模板】可持久化数组（可持久化线段树/平衡树）

可持久化数组，其实就是使用可持久化线段树实现

ybt1787：保龄球

单调队列优化\text{DP}, 这个设计状态很重要啊

注意边界处理，可以左右两边新增加$w - 1$个分值为$0$的球

P5490 【模板】扫描线

又Wa了一次

P2680 运输计划

二分 + 树上(边)差分复习

P4667 [BalticOI 2011 Day1]Switch the Lamp On

P2704 [NOI2001]炮兵阵地

记忆化搜索不好写啊

恍惚半天，最后还要MLE, 而记搜的拓扑序是乱的，没法滚动压数组

以后还是写循环迭代好了

P1983 车站分级

拓扑排序 + 优化建图（新建一个虚拟节点）

P3805 【模板】manacher算法

P3979 遥远的国度

换跟树剖复习

CF786B Legacy

线段树优化建图复习

注意数组大小开够

P1941 飞扬的小鸟

很显然的DP, 但是这道题的转移需要多加思量，很容易转移漏掉或错误

P2425 小红帽的回文数

分类讨论，> \sqrt x和\le \sqrt x

注意两个性质：

  • 一个数x在x - 1进制下一定是回文数

  • 当进制> \sqrt x时，表示出的数一定只有2位数

P2473 [SCOI2008]奖励关

期望DP + 状压DP + 板子题

P2059 [JLOI2013]卡牌游戏

约瑟夫问题 + 概率DP

设f[i][j]表示i个人围成1圈，顺时针编号从0 \sim n - 1，0号玩家做庄时j号玩家的获胜概率

f[i][j] = \dfrac{1}{m} \sum_{k = 1}^{m} f[i - 1][(j - a[k]) \bmod i]

边界：f[1][0] = 1

%用printf输出是两个%%

10172. 「一本通 5.4 练习 1」涂抹果酱

三进制状压DP复习

一转眼发现都很久没有使用过\color{Red}\text{LOJ}了，欸，以后也没机会用了

P3959 宝藏（70pts）

不加什么剪枝的搜索就有70pts了

对于考试来说足够了

P2024 [NOI2001]食物链

扩展域并查集复习

扩展域并查集维护的实质是双向推导关系, 表示同一集合内的元素可以相互推导

P3373 【模板】线段树 2

乘法加法混合线段树复习，多标记下传问题

这题我们规定任何时刻的标记都表示先乘后加，根据这个条件维护每次修改就可以了，并保持这个性质依然成立

A-无形的博弈

写了爆搜，但总是会发生循环，稍微大点的数据就跑不出解

考试全挂在这题上

B 十二桥问题

垃圾智障Fake题

考场居然没有写!!!全被T1害的

154. 送外卖

人有多大胆，地有多大产，一发爆搜直接AC

6177. 「美团 CodeM 初赛 Round B」送外卖2

三进制状压DP

考场真的zz了，想不出时间如何压入状态，并把最大投递量作为DP的值

其实"快递的投递状态" 就可以直接知道投递成功的数量，所以直接以f[x][S]为状态，表示在x时，投递快递的状态是S的最早时间即可

把时间这个最不好表示的量作为DP的值就可以了

旅行问题POI2004（看完了）

还没写，逆时针感觉有点烦

P1156 垃圾陷阱

背包DP复习，总觉得背包一维写起来更舒服

P1081 开车旅行

这题很毒瘤啊，题目信息很多，特别是那些最优值的比较 $2$次写挂在比较函数上，$1$次写挂在$set$的使用上

UVA10228 A Star not a Tree?

经过验证，当年写的三分套三分求多边形费马点的程序是正确的

时间复杂度\Theta(n \log n^2)

UVa$格式很$zz$, 喜得$PE

P2613 【模板】有理数取余

有理数取余复习

果真，\texttt{Dev-c++ 5.6.1}发出莫名警告

洛谷博客复习到剩余 \color{Red}{11} 页

10211. 「一本通 6.4 例 3」Sumdiv

又去把$\texttt{NOIp2016}$的组合数问题看了下，复习了下组合数递推指数的方法，我觉得自己做未必想得到正解取模统计的方法

经测试，如果一个multiset里有多个相同元素x，it = s.lower_bound(x)后，如果调用++it，找到的元素还是x

P4366&LOJ6354 最短路（非模板）【XOR建图套路】

XOR优化建图的常用技巧，当且仅当\texttt{x xor y}中仅有一位不同时才连边，这样复杂度就降至\Theta(n \log n^2) 已复习OK

P2485 [SDOI2011]计算器

复习了\text{BSGS, exgcd}, 快速幂这些数论板子

顺便用Hash写了BSGS, 复习了Hash表，真是一举多得

数据有问题啊，$P$不满足 $\le 10^9$，而用`std::map`的是不会发现这个问题的

10157. 「一本通 5.2 例 5」皇宫看守

经典树形DP复习

想当时做这道题的时候还对f[x][0]转移所加的cost不理解，现在看了真简单

CH#46A 磁力块

本来想复习分块的，又发现这题不是标准的分块板子，就搁掉了

6279. 数列分块入门 3

分块算法复习

std::vector使用复习

复习了std::vector的常用函数insert(), erase(), resize()以及vector的嵌套

26. 普通平衡树

vector实现普通平衡树复习

P3960 列队（60pts）

本以为vector考场可以水80pts，然而只能水60pts, 感觉vector插入删除变慢了

P3960 列队（80pts）

再加一个平衡树，成功得到80pts

P3953 逛公园

现在重写这道题，要轻松了许多，加上NOIp数据水，考试随便写可以有90pts

这道题千万别写拓扑排序，很难处理"0"环问题

这题记忆化搜索即是正解, 注意判断0环是否在满足到终点的路程 \le K的路径上，这样才判断为0环

个人洛谷博客复习到剩余 \color{Red}{7} 页

P3382 【模板】三分法

三分法复习

P1776 宝物筛选_NOI导刊2010提高（02）

单调队列优化多重背包模板复习

P3391 【模板】文艺平衡树（Splay）

复习平衡树\texttt{Splay}, 虽然感觉考场不敢写，但自己还是有一定平衡树水平的

P3812 【模板】线性基

线性基板子复习，我也就只会板子了，什么矩阵，高斯消元早就忘了

P1967 货车运输

P4551 最长异或路径

CF613D Kingdom and its Cities

虚树复习，感觉还是挺有用的

10105. 「一本通 3.7 例 1」欧拉回路

突然发现自己竟然没有刷过一本通的欧拉回路篇。。。

赶紧补模板

10106. 「一本通 3.7 例 2」单词游戏

欧拉回路信奥一本通的例题2，我居然没有做，现在才来补

建模 + 有向图欧拉回路的判定

POJ2230 Watchcow

相当于有向图欧拉回路模板

\color{Red}{\text{欧拉回路要点：实时更新表头，然后爆搜即可，退出当前点的时候添加答案，倒序输出}}

P2278 [HNOI2003]操作系统

一遍过样例"一遍AC"祭，那个RE不怪我啊，题目又不说总数

这次的程序比上次的程序更加有序有条理了

P4719 【模板】动态 DP

动态DP复习，虽然考试写不出来，也可以顺带复习下其他板子

POJ1737 Connected Graph

高精度算法复习，高精度就是爽！！！

\color{Red}{\text{最后一天了，加油！}}

P1080 国王游戏

高精度(除法)复习

P3388 【模板】割点（割顶）

P3386 【模板】二分图匹配

二分图匹配匈牙利算法复习

Acwing164. 可达性统计

P5021 赛道修建

赛道修建复习，本来想使用\texttt{vector}写的，但是失败了

为什么贪心是从小到大，为每个最小的配对，而不是从大到小，为每个最大的配对

虽然第一个贪心我找到反例了，但是为什么它也能保证配对最大呢

P3808 【模板】AC自动机（简单版）