若夫日出而林霏开，云归而岩穴暝，晦明变化

cjdst

2026-05-24 01:35:44

发布于：广东

308阅读

0回复

0点赞

置顶秒删帖。

者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴，风霜高洁，水落而石出者，山间之四时也。朝而往暮而归，四时之景不同，而乐亦无穷也。

嗯就是看大家都写了做题记录我也不能闲着，所以搞个口胡题记录。

Week 的划分到周末/节假日结束，嗯对。

Week 1（2026.3.31 - 2026.4.6）

P15654 口胡

link。

ABC452E

Difficulty：4.1 / Easy

题意解析：给定两个长度分别为 $n,m$ 的数组 $A,B$ ，求 $(\sum_{i=1}^n\sum_{j=1}^m A_iB_j(i\bmod j))\bmod 998244353$ 。

枚举 $i$ 没啥前途，考虑枚举 $j$ 。

考虑设置阈值 $l$ ， $j\le l$ 直接 $O(n)$ 暴力。现在考虑 $j\gt l$ 。

注意到第三个乘数一定是 $1,2,3,4,...,j-1,0,1,2,3,...$ 循环，而且循环次数一定不超过 $\frac{n}{j}$ 次。所以考虑前缀和处理 $\sum A_i$ 与 $\sum A_i\times i$ ，然后减一下就行了。

这样就是 $O(nl+\sum_{j=l+1}^m \frac{n}{j})$ 的， $l$ 取 $0$ 时有 $O(\sum_{j=1}^m \frac{n}{j})=O(n\log m)$ 。

record

P6572

Difficulty：4.3 / Template

虚树板子题。

虚树板子题不讲如何建虚树等于废话。

如何建虚树？

首先把关键点按 dfn 排序。然后所有相邻两个的 LCA 一定是这棵虚树的关键点。而且用这些就能描述这一棵虚树了。

::::success[证明]
感性理解不难，说白了懒得证。

那这个和废话没啥区别了（逃
::::

然后再把这些点按 dfn 排序，将每个点与它和上个点的 LCA 相连，就是这一整棵虚树了。

::::info[证明]
上个我都没证，你还想让我证这个？
::::

好了，建完虚树就简单了，套个树上差分板子就行了。

$O(n\log n+\sum s\log s)$ 。

record

不行，写的题还是太多了，再这么搞下去我这个就是做题记录而不是口胡题记录了。

Week 2(4.7 / 4.13上午)

发烧了，写不了题了，那咋办。

没事应该可以加时一天。虽然也写不了什么题就是了。

P16256

场切，爽！

Difficulty: 4.0 / Easy+

考虑每一个 $i$ 的贡献。注意到这个贡献是独立的，不受前面（除 $i-1$ ）贡献情况的影响。因此可以单独计算。

定义 $\text{pre}(A_i)$ 为 $\max_{j=1}^i A_j$ ，显然如果满足 $\text{pre}(B_{i-1})\le \text{pre}(A_{i-1}),\text{pre}(B_i)\gt \text{pre}(A_i)$ 或 $\text{pre}(B_{i-1})\gt \text{pre}(A_{i-1}),\text{pre}(B_i)\le \text{pre}(A_i)$ ，则会产生 $1$ 的贡献。把它们分别计作情况 1，情况 2。

情况 1

显然前 $i-1$ 要在 $[1,\text{pre}(A_{i-1})]$ 之间选， $i$ 要在 $(\text{pre}(A_i),n]$ 之间选，剩下的随便选。总情况数为 ${\text{pre}(A_{i-1})\choose i-1}(i-1)!(n-\text{pre}(A_i))(n-i)!$ 。

情况 2

前 $i-1$ 都要在 $[1,\text{pre}(A_i)]$ 选，但必须至少有一个要大于 $\text{pre}(A_{i-1})$ 。这太难了。

考虑反向统计，总方案数为 ${\text{pre}(A_i)\choose i-1}(i-1)!$ ，不合法的有 ${\text{pre}(A_{i-1})\choose i-1}(i-1)!$ ，所以合法的有 $[{\text{pre}(A_i)\choose i-1}-{\text{pre}(A_{i-1})\choose i-1}](i-1)!$ 。

再用方案 1 同种方法考虑后面的，总贡献数为 $[{\text{pre}(A_i)\choose i-1}-{\text{pre}(A_{i-1})\choose i-1}](i-1)!(\text{pre}(A_i)-i+1)(n-i)!$ 。

时间复杂度： $O(n)$ 。

record

Week 3(4.13下午 / 4.19)

P1084 口胡

恭喜口胡题又添一名大将！

Difficulty：4.7 / Easy

无脑考虑二分答案。

显然跳到儿子节点纯何意味，肯定要一直往根跳。

然后会发现这样还不够，因为可能有一些点可以跨过根去支援其它子树。

所以我们每个子树，如果全移到根已经可以守住就全移到根，否则留一个时间最少的，其它全移到根。

然后到根的所有节点剩余时间和到剩下子树的距离比较，看看能不能匹配。

$O(n\log n\log V)$ ，但 0 个人想写。

P4690 口胡

https://www.acgo.cn/discuss/study/79254

Week 4(4.20 / 4.26)

在线单点改区间数颜色口胡

侵删。可能会假。

CF2222F 口胡

Difficulty：4.8 / Easy+

Tag：缺一分治，Kruskal 重构数

MST 好题，潘子涵快补。

考虑枚举 $\text{mex}$ ，求出不包含边权为 $i$ 的连通情况。

于是考虑缺一分治维护这个。

具体地就是缺的那一个在左半边就把右半边加到集合，否则把左半边加到集合，然后递归，显然每个点最多会被加 $\lceil\log_2 n\rceil$ 次，加上可撤并的一个 $\log$ ，复杂度是 $O(n\log^2 n)$ 的。然后和 Kruskal 重构树一样，合并两个集合的时候加一条为 $\text{mex}$ 的边上去，最后跑一遍 MST 即可。

Week 5(4.27 / 5.5)

CF1381B

Difficulty：4.1 / Easy

Tag：背包 DP

https://www.acgo.cn/discuss/study/80279

P3157

做题用时：1h33min

定义一个下标 $i$ 的价值为三元组 $(t_i,i,A_i)$ ，其中 $t_i$ 为时间戳，保证 $t_i\le n$ 且 $t_i$ 各不相同。

对于 $k=1,2,...,n$ ，求满足 $t_i,t_j\le k,i\lt j,A_i\gt A_j$ 的 $(i,j)$ 个数。

不像标准的三维偏序问题。那 CDQ 分治到底能不能做呢？

我们尝试求出 $t_i\in[1,k-1]\rarr t_j=k$ 的贡献，然后做个前缀和即可。

还能拆，显然可以拆成 $(t_i\in[1,2^{x_1}]\rarr t_j=k)+(t_i\in[2^{x_1}+1,2^{x_1}+2^{x_2}]\rarr t_j=k)+...$ 的形式。注意到这里就可以 CDQ 分治批量求出了。

具体实现方式如下：

给定三个数 $l,\text{mid},r$ ，现在的问题是如何快速求出对于每个 $k\in[\text{mid}+1,r]$ 的 $t_i\in[l,\text{mid}]\rarr t_j=k$ 的贡献。

我们只需要开个数据结构，把 $t_i\in [l,\text{mid}]$ 的信息放进去，然后枚举 $t_i\in[\text{mid}+1,r]$ ，查询满足 $j\lt i$ 且 $A_j\gt A_i$ 或 $j\gt i$ 且 $A_j\lt A_i$ 的 $j$ 数量即可。显然这是个二维偏序，扫描线树状数组即可。

这样，每次批量查询是 $O((r-l)\log (r-l))$ 的，再加上 CDQ 分治，总复杂度是 $O(n\log^2 n)$ 的，瓶颈在于树状数组，跑得飞快。

record：https://www.luogu.com.cn/record/276503077

Bonus：注意到本题的 $m$ 特别小，请尝试以 $O(n\log n+m\log^2 m)$ 的时间复杂度解决这个问题，并抢到最优解。

Week 6(5.6 / 5.10)

~~疑似没做题。~~ 如做。

ABC457

Diffiiculty：4.0 / Easy+

1h40min 没调出来一道绿。我真的是人类吗。

注意到区间 $[s,t]$ 能被覆盖，当且仅当至少满足以下两个条件之一：

存在 $i,j$ 满足 $i\not=j,s=L_i\le R_i\le t,s\le L_j\le R_j=t,R_i+1\ge L_j$ 。形如下图：
::::info[情况 1]

::::
存在 $i,j$ 满足 $i\not= j,s=L_i\le L_j\le R_j\le R_i=t$ 。形如下图：
::::info[情况 2]

::::

我们分类讨论两种情况。

情况 1

$i\not= j$ 有点烦人，考虑去掉这个限制。

我们可以将限制改为 $s=L_i\le R_i\red{\lt} t$ ， $s\le L_j\le R_j=t$ 。这样如果满足限制，那么 $R_i\lt R_j$ ， $i,j$ 一定不相等。

但是这个限制会漏计算 $L_i=L_j=s,R_i=R_j=t$ 的情况。但又注意到满足情况 2，所以不影响。

我们可以开一个数据结构，记录以 $i$ 为左端点，可能的右端点，与以 $i$ 为右端点，可能的左端点。显然这个数据结构可以用 $2m$ 个 set 实现。

查询时，我们只需要找到以 $s$ 为左端点，右端点 $\lt t$ 的最大值，以及以 $t$ 为右端点，左端点 $\ge s$ 的最小值，比较这两个的大小即可。

情况 2

$i\not= j$ 有点烦人，考虑去掉这个限制。

我们可以将这个限制改为两个限制：

存在 $i$ 满足 $s=L_i,R_i=t$ 。
存在至少 $2$ 个 $i$ 满足 $s\le L_i\le R_i\le t$ 。

显然和之前的限制等价。

对于第一个限制，我们开个 set 记录 $L_i,R_i$ ，然后直接查询即可。

对于第二个限制，是一个二维偏序问题，可以将询问离线后扫描线解决。

时间复杂度： $O(n\log n)$ ，假设 $n,m,q$ 同阶。

Week 7(5.11 / 5.17)

ABC454F（口胡）

Difficulty：4.6 / Medium

Tag：铲雪

显然的，将 $A_i$ 减去 $A_{n-i+1}$ 就转化成了一个铲雪问题。

考虑差分法。令 $B_i=A_i-A_{i-1},B_1=A_1,B_{n+1}=-A_n$ 。

如果不算对 $m$ 取模的话，答案是 $\sum |B_i| /2$ 。

现在考虑对 $m$ 取模。注意到这个相当于我们可以将若干个 $A_i$ 预先加上或减去一个 $m$ 。这个转化成差分数组，就是把若干个 $B_i$ 加上或减去 $m$ ，但是加上的个数和减去的个数一定得相同。

所以我们可以把 $B$ 排序，然后取前 $k$ 个和后 $k$ 个进行加 $m$ 减 $m$ 操作，然后取最小值即可。

$O(n\log n)$ 。

P16395

Difficulty：4.8 / Easy+

Tag：主席树

这 trick 神了。

我们将集合内的数排名表示出来，会发现，如果一个数出现的数量大于等于 $k$ ，则其中一个数的排名一定为 $k$ 的倍数。

证明：抽屉原理，假设一个数出现的数量大于等于 $k$ ，设它第一个数的排名对 $k$ 取模为 $x$ ，则它所有排名对 $k$ 取模一定包括 $[x,x+1,...,x+k-1]$ 内每个数对 $k$ 取模组成的集合。显然这个里面一定包含 $0$ 。

所以，对于这个问题，我们可以通过树上差分，主席树找到排名为 $(\lfloor\frac{|S|}{k}\rfloor+1),2(\lfloor\frac{|S|}{k}\rfloor+1),3(\lfloor\frac{|S|}{k}\rfloor+1),...$ 的数，逐个判断它们出现次数是否大于 $\frac{|S|}{k}$ 。

$O(n\log n)$ ，假设 $n,q$ 同阶。

我去，我写这个常数小到爆了，最大点只跑了 140ms（喜）

ABC458E（口胡）

Difficulty：4.0 / Easy+

Tag：数数

找个时间把式子重新推一下。

首先考虑在 $1,2$ 序列中插入 $3$ 。显然 $3$ 只能插在两个 $2$ 之间。所以我们如果知道了一个序列有多少连续个 $2$ ，就能通过隔板法求出有多少种插入 $3$ 的情况了。

直接求总数是困难的，考虑求多少个序列满足 $2$ 的连续段个数为 $i$ ，然后计算。

我们可以分成这四种情况：

$1,2,1,2,1$ ，即 $2$ 被 $1$ 包裹。这样有 $i+1$ 个地方要填 $1$ ， $i$ 个地方要填 $2$ ，这也是个隔板法，就不算了。
$1,2,1,2$ ， $i$ 个地方要填 $1$ ， $i$ 个地方要填 $2$ 。
$2,1,2,1$ ， $i$ 个地方要填 $1$ ， $i$ 个地方要填 $2$ 。
$2,1,2$ ， $i-1$ 个地方要填 $1$ ， $i$ 个地方要填 $2$ 。

预处理组合数即可做到 $O(n)$ 。

ABC458F（口胡）

Difficulty：4.5 / Easy

Tag：AC 自动机上 DP

可惜了哥们只能给你 4.5，要是 AC 自动机一定要 $O(n)$ 实现的话就 4.7 了。

考虑给原串建一个 AC 自动机。

为什么一定要 AC 自动机呢？别的不行吗？

因为 AC 自动机有一个神级性质恰好可以解决这个问题：它可以 $O(\sum |S|)$ 末尾添加字符，求出当前文本串与所有模式串的匹配状态。

而懂得 AC 自动机的都知道，每个节点都对应着一个状态，总状态数不超过 $O(\sum |S|)$ 。

那怎么判断是否被包含呢？我们可以对当前的状态一直跳 fail，如果发现某一个地方能匹配了，就说明不行。

所以就可以根据这个建一个图， $f_{i,j}$ 表示状态 $i$ 是否可以到达 $j$ 。

然后发现就是一次走 $n$ 步合法情况。可以 $O(\text{poly}(\sum |S|)+(\sum |S|)^3\log n)$ 解决。

SYSUCPC E

感谢 zhaobingzheng 大佬的帮助！

Difficulty：4.2 / Easy

Tag：矩阵快速幂

对矩阵快速幂的理解更深了一点。原来能这么做？！

首先有一个显然的 DP：

$dp[i]=\sum_{j=1}^{n} dp[i-A_j]$

不难发现这是一个线性递推形式。由于 $A_i\le 100$ ，所以不难想到可以构造一个 $100\times 100$ 的矩阵，将 $dp$ 转化成矩乘，然后快速幂。

令 $k=100$ 。这样，一次询问是 $O(k^3\log n)$ 的， $m$ 次询问就是 $O(mk^3\log n)$ 的，不能通过。考虑优化。

我的想法

考虑光速幂。预处理出矩阵 $F^1,F^2,F^3,...,F^x,F^{2x},F^{3x},...,F^{x^2},F^{2x^2},...$ ，查询时用这里的矩阵乘即可。可以做到 $O(xk^3\log_x t+mk^3\log_x t)$ ， $x=64$ 时最优。大力卡常即可。

优化

注意到上面查询时矩阵光速幂都是矩阵乘向量。而矩阵乘向量不需要 $O(k^3)$ ，只需要 $O(k^2)$ ！！！

所以我们可以将这个优化成 $O(k^2\log_x t)$ 。

这个时候，发现我们的 $x$ 只需要设置成 $2$ 即可做到 $O(k^3\log t+mk^2\log t)$ ，可以轻松通过，完全不用卡常。

CF2229D

Difficulty：3.7 / Easy

Tag：二分答案

首先，显然 $A_i,B_i$ 任意交换不影响。

然后注意到这玩意相当于删除一个最小值和一个最大值。然后就会想到要让剩下的尽可能大，一定要让整体排名尽量高。所以考虑二分答案。

我们二分 $x$ ，记 $C_i=[A_i\ge x]+[B_i\ge x]$ 。我们需要使最终序列为 $2$ 。

那么合并就有：

若 $C_i=C_{i+1}$ ，则合并后 $C_i$ 不变。
若 $C_i=0,C_{i+1}=1$ ，则合并后 $C_i=0$ 。
若 $C_i=0,C_{i+1}=2$ ，则合并后 $C_i=1$ 。
若 $C_i=1,C_{i+1}=2$ ，则合并后 $C_i=2$ 。
反之亦然。

然后注意到 $[0,1,0]$ ， $[0,1,2]$ ， $[2,1,2]$ 的情况下，无论合并顺序如何最终都与去掉 $1$ 等价。所以中间的 $1$ 可以看做滚木。

删除 $1$ 后序列会变成 $[0,0,2,0,2,0,0,2]$ 之类的情况。我们要尽可能让最终的为 $2$ ，显然就是先把连续的 $0$ 合并，然后一个一个与 $2$ 合并。这样就转化成比较 $0$ 的连续段数量和 $2$ 的数量了。

$O(n\log V)$ 。

赛后记得看一下 G 题解。

有帮助，赞一个

去预览

0/2000

全部评论 20

cjdst
置顶
请不要在这发无意义评论，谢谢配合

2026-04-15 来自广东
2
- ༺ཌༀཉི༒小蓝-同学༒༃ༀད༻
  回复
  cjdst
  https://www.acgo.cn/application/2026532786602811392
  
  2026-04-26 来自广东
  2
- cjdst
  回复
  ༺ཌༀཉི༒小蓝-同学༒༃ༀད༻
  纯啥子来的，留着当乐子吧（
  
  2026-04-26 来自广东
  0
- Eucatastrophe‌
  回复
  ༺ཌༀཉི༒小蓝-同学༒༃ༀད༻
  谁来赔我胰岛素
  
  2026-05-04 来自浙江
  0
༺ཌༀཉི༒皇帝༒༃ༀད༻
好多广东人

2026-04-26 来自河北
1
全站的狗子我嘴最臭(慕温)
厉害

2026-04-22 来自浙江
1
Xylophone
！？神礻？！

2026-04-22 来自广东
1
Xylophone
这就是神

2026-04-22 来自广东
1
Xylophone
置顶秒删帖。

2026-04-14 来自广东
1
- cjdst
  回复
  Xylophone
  置顶秒删帖。
  
  2026-04-14 来自广东
  0
- Stars_Seeker
  回复
  Xylophone
  置顶秒删帖。
  
  2026-04-14 来自重庆
  0
- Eucatastrophe‌
  回复
  Stars_Seeker
  置顶秒删帖。
  
  2026-04-19 来自浙江
  0
Stars_Seeker
者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴
后面忘了

2026-04-06 来自重庆
1
Grapher
者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴，风霜高洁，水落而石出者，山间之四时也。朝而往暮而归，四时之景不同，而乐亦无穷也。

2026-04-05 来自浙江
1
- yanghongzheng
  回复
  Grapher
  还有续写 %%%
  
  2026-05-05 来自北京
  0
天之神_猫七夜
wow~ ⊙o⊙
看不懂
吓哭了

5天前来自广东
0
Xylophone
只有我不知道 ACAM 的性质

5天前来自广东
0
- cjdst
  回复
  Xylophone
  还批
  
  5天前来自广东
  0
- Xylophone
  回复
  cjdst
  这个真不知道（笑哭）先去看看主席树的神性质这个看得懂
  
  5天前来自广东
  0
cjdst
dd

1周前来自广东
0
🥥
%%%ABC452E我分块过的

1周前来自上海
0
- cjdst
  回复
  🥥
  论分块为什么是神
  
  1周前来自广东
  0
Xylophone
最后一题推荐吗

1周前来自广东
0
- KP-kouto
  回复
  Xylophone
  最后一题推荐吗
  
  1周前来自广东
  0
- cjdst
  回复
  Xylophone
  推荐吧，小模拟，但好像有更简单写法
  
  1周前来自广东
  0
- cjdst
  回复
  Xylophone
  set相当于平衡树的级别自然可以代替低级的树状数组扫描线，哎set你赢了
  
  1周前来自广东
  0
Xylophone
妙持

1周前来自广东
0
cjdst
ddd

2026-04-22 来自广东
0
Xylophone
妙啊

2026-04-13 来自广东
0
Xylophone
有点意思，等会试着犭虫立口胡 P1084

2026-04-13 来自广东
0
Xylophone
问一下，写这个东西对于提升实力用处大吗

2026-04-12 来自广东
0
- cjdst
  回复
  Xylophone
  0，只是展示做题情况还有提醒自己有哪些题只口胡了还没做（
  
  2026-04-13 来自广东
  1
- Xylophone
  回复
  cjdst
  T^T
  
  2026-04-13 来自广东
  0
Xylophone
恭喜过虚树

2026-04-06 来自广东
0
Xylophone
者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴，风霜高洁，水落而石出者，山间之四时也。朝而往暮而归，四时之景不同，而乐亦无穷也。

2026-04-05 来自广东
0