11月刷题表(；′⌒`)AFO
LRL52
2019-11-01 09:28:53
### #143. 到不了（$30pts$）
> $debug$了一上午，对拍很多组数据都没有问题
> **原因：重新更新$fa$数组后，$> lg[dep[x]]$的位置会残留原来的值，然后在倍增求$LCA$的时候会错误的判断成不相等，导致错误**
### #143. 到不了
> 一上午$debug$一道题
## **结论：在一棵无根树中，求以$root$为根的$LCA(u, v) = LCA(u, v) \oplus LCA(u, root) \oplus LCA(v, root) $**
### P1641 [SCOI2010]生成字符串（Review）
> 复习折线法构造卡特兰数
开栈命令复习（万一考试要用到呢）：`-Wl,--stack=134217728`
$\color{Red}{\text{注意：该命令中间不要有任何空格}}$
$134217728 = 128 \times 1024 \times 1024$
### 牛客CSP-S集训T2 沙漠点列
> 我又$sb$了，其实$lch$的代码可以直接把仙人掌内的所有环找出来，所以把考试代码只保留$Getloop$函数就可以$AC$。。。
### #143. 到不了（LCT在线做法）
> 在线做法，$LCT$求$LCA$
### 约瑟夫问题变形
> 看了很久还是不太懂，，，
> 具体细节是怎么转化的很迷。。。
### P1430 序列取数
> 复习秒切
- ## 11.2
## 【$55pts$】秋令营提高组第三轮
> 什么鬼题目啊，全是字符串
### T106647 拆分单词
> $Hash$姿势不对？？改成无冲突$Hash$就能$AC$
### T106646 表达式求值($65pts$)
> 考场它就是坑害我的罪魁祸首
> 为啥$\Theta(n^2)$可以得$65pts$
### P2831 愤怒的小鸟
> 状压$DP$裸题，注意为了避免等效冗余枚举，只需要找到二进制中第一个为$0$的位置即可
> 注意$a < 0$
### P1850 换教室(Review)
> 其实它利用了期望的线性性的性质：所有路程的期望等于每一条边的期望和
### P3959 宝藏（状压DP）
> 跟着$yxc$大佬写状压$DP$
# 【$220pts$】牛客网CSP赛前集训3
- ## 11.3
### B- 货品分组
> 不懂复杂度。。。
### POJ - 2559 Largest Rectangle in a Histogram
> 单调栈复习打卡，发现其实不用像书上写的方法那样搞，还是求出每个矩形左右第一个比它小的位置即可
### P2114 [NOI2014]起床困难综合症
> 位运算水题一道
### ybt1691：文章评分
> $Hash$表复习
### P5019 铺设道路(Review)
> 其实这道题可以用差分来做，可以说和进阶指南的P21上的例题很相似
### P3078 [USACO13MAR]扑克牌型Poker Hands
> 这竟然是$NOIp$这两年的原题出处
### ZROI#1126. 十一成都B班-铺设道路
> $NOIp2018$铺设道路扩展，还是可以使用差分数组解决
### P4170 [CQOI2007]涂色
> 思路不好想的$DP$
### P3847 [TJOI2007]调整队形
> 和$CQOI2007$ 涂色很像，不太好想的$DP$，关键还要观察到$1, 2$两种操作都可以转换成3操作
### P1030 求先序排列
> 二叉树遍历复习
### P3381 【模板】最小费用最大流
> 费用流复习打卡
### P3383 【模板】线性筛素数
> $Euler$筛复习
### P1516 青蛙的约会
> $exgcd$算法复习，$ax + by = c$方程的通解:
$$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字符串匹配
> $KMP$算法复习打卡
### P3919 【模板】可持久化数组（可持久化线段树/平衡树）
> 可持久化数组，其实就是使用可持久化线段树实现
- ## 11.4
### CSP-S集训3 地形计算
> 四元环统计，$\text{Meet in Middle}$
### CSP-S集训3 货物分组（复杂度正确的正解）
> 这才是复杂度正确的正解
> 考虑维护所有决策集合的$f[j] - sum[j] + \max\{a_k\} - \min\{a_k\}$这个整体的最小值
> 用单调栈来维护$\max\{a_k\}$和$\min\{a_k\}$
> 以$\max\{a_k\}$为例，维护一个下标单递增，数值单调递减的栈，对于新加入的元素，用线段树更新决策点的增量
> 每个线段树的叶子节点$j$存的即是从$j$转移到$i$的$f[j] - sum[j] + \max\{a_k\} - \min\{a_k\}, k \in [j + 1, i]$，其余节点存的是子区间的最小值
> **但是因为细节和边界问题思考了一上午。。。**
# 学习 TG5 部分分训练指导
> 什么部分分啊， 都是毒瘤题
### ybt1787：保龄球
> 单调队列优化$\text{DP}$, 这个设计状态很重要啊
> $f[i][j]$表示考虑了从左到右$1 \sim i$个球，使用了$j$个保龄球，且最后一个保龄球击打的区间是$[i - w + 1, i]$，的得分的最大值
> 注意边界处理，可以左右两边新增加$w - 1$个分值为$0$的球
- ## 11.5
# 【$200pts$】20191105模拟测试
### T1开方
> 一个测试点,$100pts$，得注意细节啊
### T2染色
> 只需要加上一个优化即可：**只枚举原图最小生成树的边**
### T3心情
> 区间$\text{DP}$
> 考场这个$\text{DP}$是有瑕疵的，并且从状态的定义就决定了我永远没法解决这个问题，否则就得多开一维，变成$\Theta(n^4)$
> 神奇的$\text{DP}$, 这状态谁想的到啊
> 但这复杂度有问题吧，怎么都是$\Theta(n^4)$的，只是前面的常数很小罢了
# 【$140pts$】牛客网CSP-S集训4
### 牛客网CSP-S集训4 T1复读数组
> 套路题，考虑每个数对区间的贡献即可
- ## 11.6
# 牛客网CSP-S集训4 T2路径计数机
> 计数万古如长夜啊
> 找出比赛计数的纰漏了，**没有唯一确定一组链的计数条件，导致重复计数**
> 恶心的树形$DP$, 我使用了$11$个$DP$数组终于$AC$了
# 撰写题解牛客网CSP-S集训4 T2路径计数机
> 地址：https://www.luogu.org/blog/lrl/post-ti-xie-niu-ke-wang-csp-s-ji-xun-4-lu-jing-ji-shuo-ji
## 学习了题解和start2003的方法，其实题解也要求我求过的$d, G$数组
> 有些思想还是值得借鉴
> 
> 考虑枚举$(a, b)$，对于合法的$(c, d)$可以做到$\Theta(1)$计算
> 对于已经确定的一条链$(a, b)$，合法的$(c, d)$可以分为两种情况：
> - $\text{LCA(c, d)}$**在**$\text{LCA(a, b)}$的子树内
> - $\text{LCA(c, d)}$**不在**$\text{LCA(a, b)}$的子树内
> 对于第$1$种情况，答案其实就是$\text{LCA(a, b)}$的子树内除开$a \to b$上的$d[][q]$之和
> 对于第$2$种情况，答案其实就是$\text{G[LCA(a, b)][q]}$
> 至于$G$数组如何$\Theta(n^2)$计算我就不清楚了，我的计算实际上是$\Theta(n^2 \times \max(p, q))$的
> **Update:** 根据$wxl$的做法，可以发现其实$d$数组可以通过**暴力枚举路径计算（我总是忘记了这是$n^2$可过的题，可以这样干）**，$h$数组可以通过$n$次$\text{DFS}$ **(又忘记了还可以$n$次$\text{DFS}$)qaq**计算，则$G[x][q] = \sum d[][q] - \sum d[v][q](v \in subtree\ of \ x) - h[x][q]$
> 这样就不需要计算$F, f, g, R$数组了
> $\text{start2003}$采用了**补集转化思想**, 把问题转化文求相交的长度为$p$和长度为$q$的链的个数
> $\color{Red}{\text{引理：树上两条链相交，交点上必然存在至少一个点是其中一条链两端点的LCA}}$
> 证明：举例论证显然无反例
> 于是就有了另一种做法，统计出每个点$x$，满足长度为$p$的路径两端点的$\text{LCA = x}$的个数，记作$c[x]$,对于每一条长度为$q$的路径，把路径上的点的$c$值加起来即可，这些就是满足交点是路径$p$两端点$\text{LCA}$的个数，同理计算交点是路径$q$两端点$\text{LCA}$的个数，此外还要注意交点既是路径$p$的$\text{LCA}$又是路径$q$的$\text{LCA}$的情况，不要重复计算
### P2680 运输计划
> 二分 + 树上(边)差分复习
### P4667 [BalticOI 2011 Day1]Switch the Lamp On
> $\text{0/1 BFS}$复习，像$SPFA$那样写就可以了
### P2704 [NOI2001]炮兵阵地
> 记忆化搜索不好写啊
> 恍惚半天，最后还要$MLE$, 而记搜的拓扑序是乱的，没法滚动压数组
> 以后还是写循环迭代好了
### P1983 车站分级
> 拓扑排序 + 优化建图（新建一个虚拟节点）
### P3805 【模板】manacher算法
> $\text{Manacher}$算法复习
### P3979 遥远的国度
> 换跟树剖复习
- ## 11.7
### 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`输出是两个`%%`
# 【$122pts$】牛客CSP-S提高组赛前集训营5
> 自闭了，考牛客赛做T1总共花了2个小时还在考试结束2min前改了，T3一条链我猜它数据水就打了O(n^2)的贪心走人了，考场我就知道一条链只需要单调栈 + 倍增就解决了，懒得写，躺在床上一想，T2就是个Fake题啊，考场也写了个暴力就走人了，然后继续验证T1的反例却统计不出答案。
- ## 11.8
## A-无形的博弈
> 写了爆搜，但总是会发生循环，稍微大点的数据就跑不出解
> 考试全挂在这题上
### B 十二桥问题
> 垃圾智障$Fake$题
> 考场居然没有写!!!全被$T1$害的
### #154. 送外卖
> 人有多大胆，地有多大产，一发爆搜直接$AC $
### #6177. 「美团 CodeM 初赛 Round B」送外卖2
> 三进制状压$DP$
> 考场真的$zz$了，想不出时间如何压入状态，并把最大投递量作为$DP$的值
> 其实"快递的投递状态" 就可以直接知道投递成功的数量，所以直接以$f[x][S]$为状态，表示在$x$时，投递快递的状态是$S$的最早时间即可
> 把时间这个最不好表示的量作为$DP$的值就可以了
### 旅行问题POI2004（看完了）
> 还没写，逆时针感觉有点烦
- ## 11.9
### #10178. 「一本通 5.5 例 4」旅行问题
> 把信息学奥赛一本通提高篇单调队列的坑填了，当时觉得这题好像讲解有问题
> 现在看了又没有问题了
>前缀和写挂了。。。
# 【$280pts$】秋令营提高组第四轮
> 以为$AK$了，然而$T1$挂了$20pts$，不过竟然才挂$20pts$
## T108117 灯火将熄
> 这道题憋了我一下午，带权并查集捉鸡啊
> 这个带权并查集可以维护每个点到根节点的距离
> 特别是找下一个点细节思考了我很久
### T108118 和光同尘
> $Hash$板子题
### T108119 长夜终尽
> 二维数点 + 扫描线板子
### P1196 [NOI2002]银河英雄传说
> 带权并查集复习
# 【$150pts$】牛客CSP-S提高组赛前集训营6
> 最后一场牛客比赛了，还是zbl，$T2, T3$简直做不来
- ## 11.10
# 【$224pts$】秋令营提高组第五轮
> 平推前$2$题，最后一题自闭
### P4042 [AHOI2014/JSOI2014]骑士游戏
> 神奇的$SPFA$的$DP$, 反复迭代更新
> 改个错，等了一下午才成功提交
### P1156 垃圾陷阱
> 背包$DP$复习，总觉得背包一维写起来更舒服
### P1081 开车旅行
> $\texttt{NOIp}$倍增复习，顺便复习下$set$的使用
> 这题很毒瘤啊，题目信息很多，特别是那些最优值的比较
> $2$次写挂在比较函数上，$1$次写挂在$set$的使用上
- ### 11.11
# 【$190pts$】20191111模拟测试
> 啊$T1$又$zbl$
### P4994 终于结束的起点
> 果真是到$Fake$题，照着题意模拟即可
### P4995 跳跳！
> 永远不会证只会猜的贪心
### UVA10228 A Star not a Tree?
> 经过验证，当年写的**三分套三分求多边形费马点的程序**是正确的
> 时间复杂度$\Theta(n \log n^2)$
> $UVa$格式很$zz$, 喜得$PE$
### P2613 【模板】有理数取余
> 有理数取余复习
> 果真，$\texttt{Dev-c++ 5.6.1}$发出莫名警告
### 洛谷博客复习到剩余 $\color{Red}{11}$ 页
- ## 11.12
### P2758 编辑距离
> 本以为是一道模拟题，结果是到普通的$DP$题
### #10211. 「一本通 6.4 例 3」Sumdiv
> $\text{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$表，真是一举多得
> $BSGS$在$a == 0$的时候要特判，否则会有边界问题
> 数据有问题啊，$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$环
> $Luogu$新添了$1$组$Hack$数据
## 个人洛谷博客复习到剩余 $\color{Red}{7}$ 页
- ## 11.13
### 【$240\sim 250pts$】20191113模拟考试
> 注：应该是$250pts$，但由于教师机测评速度问题就只能$240pts$了
> 最后一次测试了，挺难受的
### 【$240pts / 400pts$】【LGR-065】洛谷11月月赛 III Div.2
> $\color{Red}{\text{最后一次洛谷官方比赛了，最后一次参加洛谷比赛了，也最后一次参加模拟比赛了吧}}$
### P3382 【模板】三分法
> 三分法复习
## 颓废观看了【FMT#8】洛谷 Fan Meeting Live 直播
> 真希望考完还来洛谷哦
### P1776 宝物筛选_NOI导刊2010提高（02）
> 单调队列优化多重背包模板复习
### P3391 【模板】文艺平衡树（Splay）
> 复习平衡树$\texttt{Splay}$, 虽然感觉考场不敢写，但自己还是有一定平衡树水平的
### P3812 【模板】线性基
> 线性基板子复习，我也就只会板子了，什么矩阵，高斯消元早就忘了
### P1967 货车运输
> $Kruskal$重构树复习，同时这道题或者最小瓶颈路也可以使用$Kruskal$重构树解
- ## 11.14
### P4551 最长异或路径
> $Trie$树复习, $Trie$树的经典应用：求异或最大的一对
### 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
> 高精度算法复习，高精度就是爽！！！
### P1939 【模板】矩阵加速（数列）
> 矩阵快速幂板子复习
- # 11.15
$$\color{Red}{\text{最后一天了，加油！}}$$
### P1080 国王游戏
> 高精度(除法)复习
### P3388 【模板】割点（割顶）
> $\texttt{Tarjan}$求割点复习
### P3386 【模板】二分图匹配
> 二分图匹配匈牙利算法复习
### Acwing164. 可达性统计
> $\texttt{bitset}$用法复习
### P5021 赛道修建
> 赛道修建复习，本来想使用$\texttt{vector}$写的，但是失败了
> **为什么贪心是从小到大，为每个最小的配对，而不是从大到小，为每个最大的配对**
> 虽然第一个贪心我找到反例了，但是为什么它也能保证配对最大呢
### P3808 【模板】AC自动机（简单版）
> $\texttt{AC}$自动机复习