11月刷题表(；′⌒`)AFO

LRL52 · 2019-11-01 09:28:53 · 个人记录

143. 到不了（30pts）

**原因：重新更新$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：文章评分

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 【模板】可持久化数组（可持久化线段树/平衡树）

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

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}, 这个设计状态很重要啊
注意边界处理，可以左右两边新增加$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)可以分为两种情况：

对于第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数组了
$\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

P2704 [NOI2001]炮兵阵地

记忆化搜索不好写啊

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

以后还是写循环迭代好了

P1983 车站分级

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

P3805 【模板】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 和光同尘

T108119 长夜终尽

二维数点 + 扫描线板子

P1196 [NOI2002]银河英雄传说

带权并查集复习

【150pts】牛客CSP-S提高组赛前集训营6

最后一场牛客比赛了，还是zbl，T2, T3简直做不来

11.10

【224pts】秋令营提高组第五轮

平推前2题，最后一题自闭

P4042 [AHOI2014/JSOI2014]骑士游戏

神奇的SPFA的DP, 反复迭代更新

改个错，等了一下午才成功提交

P1156 垃圾陷阱

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

P1081 开车旅行

这题很毒瘤啊，题目信息很多，特别是那些最优值的比较 $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

又去把$\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} 页

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 货车运输

11.14

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

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

P1939 【模板】矩阵加速（数列）

矩阵快速幂板子复习

11.15

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

P1080 国王游戏

高精度(除法)复习

P3388 【模板】割点（割顶）

P3386 【模板】二分图匹配

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

Acwing164. 可达性统计

P5021 赛道修建

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

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

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