如第一篇题解，感觉非常没有道理，求严谨分析或 hack。

值域范围是 long long 的，两个相乘会越界。需精细实现或开 __int128。

如果莫名其妙 WA/RE，可能是你标记数组忘了开 long long

妙妙题。 *** 先将 B 缩起来（颜色段缩成一个点），判掉颜色集不包含等显然的情况。 接下来处理 $k=1$。我们发现操作只能将颜色向两边推，不能改变顺序。则可行条件是 A 存在一个字串与缩小后 B 串相等。 如果 $k\ge 2$，考虑有连续的三个数 abc，可以通过操作产生 aab，baa。设 c 是无用的，则可…

归并算逆序对的时候不用完全并完，实测能大幅降低归并常数。 ```cpp inline ll cal(const vector &x,const vector &y){ int n=x.size(),m=y.size(),l=0,r=0;ll s=0; while(l<n&&r<m){ if(x[l]<y[r])l++;…

在文章《题解：P14532 [RMI 2018] 颜色 / Colors》发表评论：

启发式合并multiset复杂度包错的啊，因为你还要撤销

先是一个观察：$\gcd (R_x,R_y) = R_{\gcd(x,y)}$，正确性显然。 把 $\operatorname{lcm}$ 反演了： $$ \begin{align*} \operatorname{lcm}(R_{a_1},R_{a_2},\dots ,R_{a_i}) & = \prod_{T \su…

在文章《题解：P14426 [JOISC 2014] 稻草人 / Scarecrows》发表评论：

你要进队了/bx

在文章《题解：P14426 [JOISC 2014] 稻草人 / Scarecrows》发表评论：

大神啊

观察或打表得，题目给出的 FIND 函数返回的是后缀和。于是我们要求出的就是 $a_{l-1}=a_r$ 的概率。特别的，若 $l=0$ 则求的是 $S_{[1,r]} = S_{[r,n]}$ 的概率。后者容易维护，下面考虑如何维护前者。 思考操作对答案的影响。我们建一个二维矩阵 $P_{i,j}$，表示 $a_i=…

算是一种插入 DP 吧。 *** 先考虑一维版本 [AT_dp_t](https://www.luogu.com.cn/problem/AT_dp_t)。我们设 $f_{i,j}$ 表示填完前 $i$ 个数，末尾的数是填的数中第几小的。转移时枚举第 $i+1$ 位置放的数是前 $i+1$ 第几小就行。关于正确性，我们将…

暴力 DP 是平凡的，我们思考如何处理修改操作。 设 $f_{i,j}$ 为从 $(1,1)$ 走到 $(i,j)$ 的不包括点 $(i,j)$ 的权值和，$g_{i,j}$ 为从 $(n,m)$ 走到 $(i,j)$ 的不包括点 $(i,j)$ 的权值和。于是修改一个点对答案的影响就是 $A'_{i,j} \time…

经典的碰撞问题。 每次蚂蚁碰撞后，我们让蚂蚁交换编号，穿过对方继续行走。由于蚂蚁相对位置不变，而最终蚂蚁落在的位置易知，我们只要求出第一只蚂蚁对应 $T$ 时刻序列中第几只蚂蚁。 线上就还是第一只，原上要考虑最后一只蚂蚁走完了一圈的情况。按顺时针编号，蚂蚁每顺时针跨过 $0$ 位置，第一只蚂蚁对应序列中位置就加一，反之…

第一次切 AT *2400，纪念。~~你说的对但是多一只 log 过题不算过题。~~ *** 设 $f_{i,j}$ 表示操作到第 $i$ 位，目前最后一个数是 $j$ 的最大答案，容易得到转移。注意到对于同一个 $i$ 的所有 $[i,j]$ 区间异或起来答案数量只有 $\log V$ 种，我们将这些区间大力二分找出…

考虑一对区间 $(i,j)$ 对答案的贡献，显然： * 若相离，贡献为 $0$； * 若相交但不包含，贡献为 $1$； * 若包含，贡献为 $2 \times [P_{in}>P_{out}]$。 为了最小化答案，我们应该让包含关系的内部区间的 $P_i$ 小。于是从内部区间向外部区间连边，最优方案就是 DAG 的拓扑…

$O(n^2)$ 做法是简单的，难点在于优化。 设 $f_k=\sum_{i=a-k}^{a-1} \binom{n-k}{i}$，由于想要凑出递推式，我们： $$ \begin{align*} 2 f_{k+1} &=2 \sum_{i=a-k-1}^{a-1} \binom{n-k-1}{i} \\ & =\sum…

在文章《别样的T4保龄大战》发表评论：

upd：290

[P4249](https://www.luogu.com.cn/problem/P4249) 对于最小化平方和问题，有一个经典差分建图：从每个点建立流量 $1$，费用 $k$ 的边，前缀和就是平方。 *********** [P3749](https://www.luogu.com.cn/problem/P3749)…

唐题，为什么别的题解写那么长。 *** 先按照 $x$ 排序，然后 CDQ 分治。分治中按照 $y$ 排序，用左边贡献右边。发现左边可以按照 $x$ 坐标维护一个单调栈，右边点能匹配的左边点数量就在单调栈上二分一下。 ```cpp /* 2025.11.11 * Happy Zenith Noises * */ #in…

该复习 KMP 了。 *** 考虑如何判断两个串一样。对于 A 串的小写字母集合，若存在一种映射，将字母通替换后变成 B 串，则 A,B 串一样。而大写字母不能有任何区别。维护每个位置 $i$ 到上一次该字母出现位置的距离 $a_i$ 即可。 匹配的时候要注意，模式串中首次出现的字母，对应主串位置可能并非首次出现。显然…

先转换一波：每轮动完，将每个人都向右移动一格。于是三种移动变为：不动，向右移动一格，向右移两格。 设初始位置 $a_i$，最终位置 $f_i$，容易得到递推： $$ f_i=\max(\: f_{i-1} + D,ai \:) $$ 展开得： $$ f_i=\max_{j=1}^{i}(\:a_j+D \times (…

在讨论《多了13分》回复：

先后分数都打暗广了(doge

若 WA35，请检查你是否： ```cpp #define int long long ``` 这会使 unsgined int 变成 unsigned long long！

非常好差分题。 $ k=1 $ 时就是 [P4211 [LNOI2014] LCA](https://www.luogu.com.cn/problem/P4211)，将询问离线下来并拆成两半，对于贡献点将其到根节点路径上的边都加上 $1$，询问点答案就是其到根节点的边权值和。 思考 $k>1$ 咋做。我们仿照上述方法，…

RT

* 归并排序时避免用二倍空间。 * 结构体内位域压缩。

设 $f_{i,(0,1)} $ 表示第 $i$ 个点的子树，不存在有猫或狗的节点于其相连，所要删除的最少边数。先写出朴素 DP 的矩阵转移方程： $$ f_u= \begin{bmatrix} f_{v,0} & f_{v,1} \end{bmatrix} \times \begin{bmatrix} f'_{u,0…

在讨论《求助，莫名其妙数组越界》回复：

@[ftzx](luogu://user/614672) 对的，clear vector的时候忘记判断了/ll

在文章《别样的T4保龄大战》发表评论：

妈的，T3挂成25分了！！！！CCF数据要是和民间数据一样水我还能苟活

RT。我将 MAXN 设为 2e5 就会越界 WA95，设成 4e5 就 AC 了。球球大佬们帮忙看一眼哪里能越界啊 qwq。 ```cpp /* 2025.11.1 * Happy Zenith Noises * */ #include #define int long long #define pb push_ba…