在讨论《【LGR-267】&UTOI r1 赛后致歉帖（更新获奖情况）》回复：

qp

在讨论《求问》回复：

@[yanghongzheng](luogu://user/1632057) 橙题的题解都比较短，所以要坚持看完，逼自己理解题解的要点，而且要突破这种思维瓶颈，还要多独立思考，而不是思考不出来就直接看题解。

## Ⅰ​.数据结构 #### 1.树状数组 时间复杂度：$O(n\log n)$ 优点：常数小 缺点：可以维护的内容不如线段树 应用：小常数维护前缀和或单点值 ```cpp int tr[200005]; void add(int x,int y){while(x >1; if(tag[p]){ tr[…

我们可以将一个图 $G=(V,E)$ 转化为它的一颗生成树 $T=(V,E')$，那么图中的环必然是由两条树上的链与几条非树边构成的，如下图：  其中粉边即为一个环，但此时这个环是不好求的，因为…

考虑到我们需要对于每次查询 $S$，找到一个集合 $T=\{S_i\in U|S\in pref(S_i)\}$，其中 $pref(S)$ 表示字符串 $S$ 的所有前缀的集合，我们必然可以使用 Trie 树维护，对于每个串 $S$，$S_{|S|-1}$ 在 Trie 树上对应节点 $k$，那么节点 $k$ 的子树即…

在文章《题解：P14362 [CSP-S 2025] 道路修复 / road（民间数据）》发表评论：

在姚期智的论文中，证明了不使用启发式合并、只使用路径压缩，在平均情况下，时间复杂度依然是 $O (m\alpha(m,n))$，详见[OI Wiki](https://oi-wiki.org/ds/dsu/)

我们不难发现这个倒三角其实就是一个倒过来的杨辉三角，第一层的第 $i$ 个数对于底部贡献为 $\binom{n-1}{i-1}$，意味着中间贡献大于两边，所以考虑贪心将大的数放在中间，小的数放在两边即可，由于模数 $mod=10007$ 较小，所以要套上 Lucas 定理计算组合数，时间复杂度为 $(mod \log…

在讨论《求问》回复：

@[JZJR_A_0](luogu://user/1190117) 我的解法应该是单 $\log$ 的，只是维护区间前三大可能比较繁杂一点点

在讨论《求问》回复：

可以将 $(x_1,y_1)(x_2,y_2)$ 改为 $(1,1)(x_2,y_2)-(1,1)(x_1,y_2)-(1,1)(x_2,y_1)+(1,1)(x_1,y_1)$ 然后 cdq 二维数点维护区间前三大即可

在讨论《强烈谴责qn^2可过》回复：

性质 B：可以认为每个字符串对 $(S_1,S_2)$ 就是将字母 B 进行了平移，对于字符串对 $(T_1,T_2)$ 我们只需要二分找到所有与其 B 字母偏移量相同的字符串对 $(S_{i,1},S_{i,2})$，并且求出其中满足 $T_1$ 中 B 的前缀 A 数量大于 $S_{i,1}$ 中 B 的前缀 A…

在讨论《【11 月 20 日截止征新游记】CSP 2025 游记征集！》回复：

已严肃完成：https://www.luogu.com.cn/article/f26dgzhc

在讨论《AC 自动机 60pts TLE 求调》回复：

@[DimStar](luogu://user/755179) 感谢

```cpp #include using namespace std; int n,q; struct node{ int son[27],fail,cnt,sum; }tr[5000005]; int cnt; vector e[5000005],to; string change(string a,string…

### Year -3 我们无缘相见 由于疫情原因，CSP 复赛仅对高中生开放，我错过了我人生中第一次 CSP，后来找关系获得了一个春季测试 2023 的非正式名额，只是成绩不尽人意…… ### Year -2 我常常追忆过去 依旧记得两年前的 CSP 2023，早上入门组发挥失常，导致下午的提高组做题时压力陡增，看见…

在文章《题解：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据）》发表评论：

%%%

考虑到对于 $k$ 个乡镇明显可以状压枚举所有乡镇选择的方案，然后暴力计算目前选择的乡镇与 $n$ 个城市的最小生成树，此时边数时 $O(kn+m)$ 级别的，那么时间复杂度是 $O(2^k(kn+m)\log\ (kn+m))$ 的，这样必然会超时。我们于是考虑减少边的个数，我们不难发现，在最开始只有 $n$ 个城市…

考虑斐波那契数 $fib_i$ 具有性质 $fib_i=fib_{i-1}+fib_{i-2}$，又考虑到相邻块的构成字母不同，所以我们不难想到，对于目前剩余数最大的字母 $x$ 来说，我们应该用 $x$ 来形成现在最大的斐波那契数 $fib_i$，否则非常明显的是，如果不这么干，必然 $fib_i$ 将被拆成 $fi…

我们首先考虑叶节点 $u$，我们必然要向 1 到 $x$ 的链加上一个权值 $c\in[l_u,r_u]$，不难发现，由于对一个链加上的权值从根到叶节点满足 $c_1\le c_2\le c_3\le ...\le c_k$，那么 $c$ 取最大值 $r_u$ 自然不劣。接下来考虑非叶节点 $u$，我们发现所有操作中加…

~~校内模拟赛上场切紫题 *800？~~ --- 我们不妨先考虑从 $u$ 出发直接走到 $v$ 的贡献，此时对于 $\forall i\in[u+1,v]$ 第 $i$ 堆石头数量都会加一。接下来我们考虑在从 $u$ 走到 $v$ 的过程中不是直接走到的，那么走法无非三种： 1. 走到 $u$ 的左侧然后走回 2.…

## 前置知识 ### 积性函数 顾名思义，积性函数是一类满足 $f(ab)=f(a)\times f(b)$ 的函数，当然 $f(ab)=f(a)\times f(b)$ 是有成立条件的，它的成立条件是 $\gcd(a,b)=1$。 ### 线性筛 可以用 $O(n)$ 的时间复杂度筛出积性函数 $f(x),x\in…

我们考虑一个字符串 $s_i$ 与另外 $n-1$ 个字符串均有 $k$ 个字符不同，但一个一个字符串枚举比较的时间复杂度显然是 $O(n^2m)$ 的。所以考虑更优的实现方法，我们发现 $s_i$ 与其它字符串应该一共有 $(n-1)k$ 个字符不同，我们只需要用桶记录每个位置 $4$ 种字符的个数，即可计算 $s_…

一种比较暴力的方法。 考虑 $n\le10,a_i\le10$ 所以陷阱的状态仅 $n$ 种，而且每 $\operatorname{lcm}(a_0,a_1,...,a_{n-1})$ 个格子就是一个陷阱状态的周期，我们不妨记 $l=\operatorname{lcm}(a_0,a_1,...,a_{n-1})$，我们…

## 题目描述 有一颗 $n$ 个节点的树，树上的每一个点有一个爆炸半径 $r_i$，每条边 $(a_i,b_i)$ 有一个长度 $c_i$，一个炸弹 $i$ 能引爆另一个炸弹 $j$ 当且仅当 $dis(i,j)\le r_i$。 ## 问题分析 我们可以建一个有向图 $G$，对于 $\forall i,j\ dis…

# [列队春游] 题解 ## 题意 给定整数序列 $a$，对于随机排列 $p$，求 $\sum f_i$ 的期望。 对于位置 $i$，$f_i$ 定义为最小的 $x$，满足对于任意位置 $j,1 \leq x \leq j \leq i$，均有 $a_{p_j} \leq a_{p_i}$。 数据范围：$a_i, n…

我们不妨先维护出按照题目要求插入数据后的数列 $a$，很明显，每次将 $i$ 插入 第 $p$ 位就是要找到数列 $a$ 中的第 $p-1$ 号元素，然后将 $i$ 插入到 $p-1$ 号元素与 $p$ 号元素之间，这可以非常轻松的用平衡树维护，具体来说就是将排名小于等于 $p-1$ 与大于 $p$ 的两棵子树分裂，然…

在文章《题解：P14172 【MX-X23-T2】括号串》发表评论：

%%%orz

在文章《题解：P14173 【MX-X23-T3】猜拳游戏》发表评论：

%%%orz

我们不妨先寻找 Alice 的出招序列 $a$ 中的 $a_i$ 与 Bob 的出招序列 $b$ 中的 $b_j$ 在什么时候会在同一局中出现，考虑 Alice 与 Bob 会进行 $10^{100}$ 局游戏，所以可以认为是无限局游戏，那么只要 $nx+i=by+j$ 存在一对非负整数解 $(x,y)$，$a_i$…

在文章《题解：CF1787C Remove the Bracket》发表评论：

%%% Orz