上了大学的做题记录【2022.10】

sanaka87 · 2022-10-01 15:39:26 · 个人记录

累死我了。

这个月的做题记录居然是上个月的 1/3，颓狗实锤了。 主要是因为校内训了 8 场。

一些题解：

gym 100026 C

咕咕咕。

自闭几何题。有非常非常简单不用特判的写法呢。

gym 100026 E

咕咕咕。

自闭签到题。

gym 100026 H

咕咕咕。

gym 101470 G

咕咕咕。

赵大哥牛逼！

gym 101385 G

咕咕咕。

队友写的构造。补一下。

gym 101385 I

咕咕咕。

gym 101371 D

先把 c 用逆元变成 1。直接枚举不行选中的概率小，上原根，迭代 sqrt 次就退出。

gym 101371 E

md，给时间限制骗了。

我们只考虑 x_i< x_j,y_i< y_j，等于的特判，然后反过来的话全体 y 坐标取个反再做一次。

然后按 x 坐标排序，考虑分治，左边对右边有一个贡献。然后经典单调栈删点，左右都变成一个单调下降阶梯型形状。归并一下时间复杂度 O(n\log n)。

所以 tmd petr 出 10s 怕不是发电了？

gym 101191 H

矩阵！但是复杂度炸了，所以用前缀和优化和全局加法标记来算出矩阵（特殊性质，快速矩阵乘法），然后矩阵快速幂即可。

gym 101380 G

卡空间的状压 dp。思考折半 = 死路。

状态记录左端点的匹配是否成功的情况。

卡空间：

• 滚动数组。

• 四进制存储字符串。

• 第一个字母可以手算，空间 / 2。

卡进 131 MB。

gym 101380 H

好玩的构造题，发现可以构造出 [2A,2B] 的小区间元。那么跑一个背包一样的东西就好了。复杂度不行，用性质优化，每次至少少 2A。

gym 101470 B

后缀数组好题。答案一定是能最多最大串就最多最大串。先二分最后答案，然后能匹配就匹配，贪心+倍增判断。时间复杂度 O(n\log^2n)。

gym 101470 C

线段树上二分模拟即可。非常恶心。但是 1 A ！

gym 101470 F

分块，这题暴露了我写代码的能力有多低，不知道为啥写错这么多次。

二分过不了，但是区间加一只会给答案 1 的贡献，所以直接暴力 check 复杂度就是对的，还少个 \log。

gym 103964 F

发现每次是一个地方造兵，然后拖动到一个可以容兵的地方，这就是一个多源最短路。

gym 103964 I

麻将自动机魔改版，每次要记录有没有浪费排。这样打出来的状态是 40000 个左右。

gym 100402 B

后缀数组做两次，一次做行，一次做列，然后就好了。

gym 100402 D

python + 并查集 + 容斥。不会写 Python 浪费了好多时间。

gym 100402 F

降智打击签到题，我是一个大傻逼。我们从左到右考虑，相当于放前面或者放后面，然后贪心就好了。

gym 100402 J

坑 dp 题，多记录几个状态，记录方案就好了，需要好看的写法。

gym 101385 D

有趣的 dp 套 dp。考虑如何判断一个串能否生成——状态压缩判断当前第一个串匹配到 i 是否可以。那么暴力就好了。复杂度 O(能过)。

10.31

CF 1628E

被剧透过然后就会了，发现如果想不到 kruskal 重构树就 g 了 吧...

虚树最大边权居然 tm 可以 kruskal 重构树...

顺便复习了一下 Mdoi 的 Treequery（换根 lca 和 dfn 结论，分类讨论）。集合 lca 是最大最小 dfn 的 lca。于是线段树维护区间 dfn 最大最小即可。

CF 1062E

看题解区看到的。

发现直接分类讨论，注意到删除一定是删除 dfn 最小的或者最大的，

CF 1422F

直接 sqrt 分治是傻逼题，考虑不用它。

离线，右移 r 端点考虑对答案的影响。发现每一个质数开一个单调栈维护幂次个值就可以计算贡献了。

套上主席树就强制在线了。时间复杂度 O((n+q)\log\max a\log n)。

10.30

埋了。

咕咕咕。啥都没干，准备十一月屯个大的（比如把 10 月集训的题目补一补）。

前几天出模拟赛，不知道在干些什么。

CSP 题解待补。

P7561

二分解决曼哈顿距离。

10.27

好颓废啊。和 zls 闲聊着时间就不见了。

10.25

水帖子看到的题

因为是修改，所以肯定不能直接从分治 bfs 角度考虑。

相邻状态是可以合并的。假设确定的位状态是 a_i，显然有 a_i \ \texttt{xor}\ a_j=0。然后对着交界处一顿分析就好了。用线段树维护合并，时间复杂度 O(n\log n\log A)。

在看以前的单位根反演，搞模板。

10.24

昨天口胡了 2 题，今天写。

CF 1270F

根号分治好题，退役前口胡过，当时想了好久，现在也想了好久。。。

枚举什么？枚举什么？枚举什么？枚举倍数就可以用 -k+1, 1 的前缀和来统计答案了。

实现细节很多。

• 哈希表可以直接开 nsqrt n 的数组。

CF 1276F

开始写字符串重工业了。

现在就是要算 S*T 的个数。我们枚举 S 在正串 SAM 的节点（防止算重复），然后看看该节点 u 的 endpos 集合里所有 + 2 位置在反串上的 SAM 形成的链并的权值和。根据动态维护虚树的经典操作，这个可以用 dfs 序和相邻节点的路径权值和 / 2 来快速维护出。线段树合并即可。用 O(1) LCA 可以做到 O(n\log n)。

写了树剖，4.1k ，但是跑得飞快。

居然傻逼以为 parent 树上叶子结点才是有 endpos 初始值的，我脑子里装了什么...

loj 6789

dsu on tree + SAM 的套路。

轻儿子直接开桶统计贡献，重儿子再用扫描线外面做。

继续数据结构复习。

P5385

居然没写过这题，赶紧复习一下 LCT。突然也发现自己已经 2 年没写主席树了。

LCT 维护（时间）最大生成树+主席树维护强制在线即可。

• LCT 要对边建虚点。

• LCT 0 号点要初始化，不然 pushup 会 g。

• 小心自环。

P7735

DNA 好疼。

• 时间戳的解法如果做过树点涂色还是可以很套路得想出来（我居然想了挺久的，还是在想链分治的时候想到的？？）。

• 一个点最多两个“重”儿子，所以大力树剖也是可以的，但是很恶心。

• 有一个毛毛虫问题的超级通解毛毛虫剖分。

P3591

没写，最水的根号分治。。。如果用长链剖分可以优化。其实我还不会长链剖分，马上去学。

10.22

摆烂。

10.21

都不是很想写。。

CF 1276C

猜上界，枚举短边，然后构造。

CF 1749D

发现一直取第一个就可以，所以答案就是下标除以质数前缀积的乘积。

10.20

CF 1408G

感觉挺简单的，转化一下就是 kruskal 重构树上的反链计数。

我的切入点是这样的：考虑枚举 1 的团的最大边 w，那么一定是遇到小于 w 的就加入，一直扩展，发现就是一个 kruskal 重构树的过程。

不过可能子树不是团，所以这个要对每个子树判断一下。这两个都可以用树上背包经典复杂度做到 O(n^2)。

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

10.19

CF 1743F

白给题，算贡献，然后就是线段树维护 2~n 的矩阵乘法。

CF 1483F

神仙题，原来是 div1 的 F。。

题解不大想写。反正去重的方法有点妙的。

CF 1400F

死去的记忆开始攻击我...

串很少，直接 ac 自动机上 dp。

CF 1202E

枚举断点，然后就是自动机板子咯。

一次过样例，1 A 了。

10.18

P5446

如果长度 > N/2 就是看回文半径，如果 < N/2 递推。manacher就好了。

没清空 wa 飞了。。

P2414

显然是复习。

AC 自动机上查询一个串 x 在另一个 y 上出现多少次：枚举 y 后缀，跳 fail，遇到 x 答案加一。也就是查询 x 子树内有多少 y。我们把 y 的询问挂在 y 点上，遍历自动机的时候算出答案就好了。

CF 765F

没退役的时候就一直咕这题 qwq

调整法考虑哪些是没有必要更新的。权值线段树做 log 次即可。然后用一个树状数组维护后缀 min。

1 A 了。

CF 1726E

排列计数捏。套路。

四元环有两种情况：

10.17

咕咕咕了。

https://www.luogu.com.cn/blog/sanaQWQ/hui-wen-chuan

CF 1736E

乱找性质=WA 4爆炸。

直接 dp 就好了，不要想太多。

10.14

集训司马。

集训队作业。

10.13

CF 700E

口胡。

https://www.luogu.com.cn/blog/user13052/solution-cf700e

证明很妙！这个性质也很妙。。

• 在 parent 树上，若 p 是 q 的祖先，则 substr(p) 中所有字符串在 longest(q)（下记为 s）中出现次数与出现位置相同。

10.12

CF 571D

假了 明天重构。

主要还是这样一个思想：单点查询+清空 -> 答案-最近一次清空的答案。

P4745

也和 cf 那个一样。

最优策略：选择一个阈值然后中了就走。

最短路就可以了。然后过了。

10.11

摆烂。

补 vp 的题。

CF 1693D

这个一直不是很会，然后就不会了。

https://www.luogu.com.cn/problem/solution/CF1693D

结论：对于一个子区间 [l,r]，有解的充要条件是：

不存在 l\le a<b<c<d\le r ,使得 p_b>p_a>p_d>p_c 或 p_b<p_a<p_d<p_c。

CF 1693C

最短路改造的题目做的好少...虽然自己想出来了但感觉好妙。

CF 1693B

为啥我大脑宕机了 10min。。。

树形 dp 一样地倒推 + 贪心。能塞多就塞多。

CF 1693A

直接模拟，先排除无解，然后倒推。

10.10

摆烂。

集训队作业。

10.9

摆烂。

集训队作业。

10.8

啥都不想写。

10.7

越打越烂，谢谢队友！！！

10.6

集训司马了。区域赛再见了！

10.5

集训司马了。

晚上 vp 了一场 cf，感觉自己没有脑子了。

CF 1408D

我是傻逼。为什么疯狂脑瘫啊！？

核心思路：枚举 x 上去多少。然后两个点之间有一个限制。后缀 max 一下就好了。

CF 1408E

如果想到优化建图，建立虚点发现一下子就结束了！

CF 1408F

两个 2 的幂次拼起来，做完了。

10.4

回学校了。数分好难。

Michael Tikhomirov Contest 1 E

https://blog.csdn.net/xyyxyyx/article/details/102090170

注意期望括号内部有条件概率的限制。

CF1672F1

经典模型，补一补。

https://chzhc.blog.luogu.org/solution-cf1672f1

CF1672F2

https://chzhc.blog.luogu.org/solution-cf1672f2

10.3

在家里颓了一天。

感觉状态一日不如一日呢。

P4804

真的不会。找规律结论吧。

Michael Tikhomirov Contest 1 D

放在 ds 复习里了。

集训队作业。

10.2

在家里颓了一天。

集训队作业。

10.1

在家里颓了一天。

集训队作业。