在文章《WC2026 游记》发表评论：

希望大家在未来都能有个好的结果

在讨论《哇，我只比nq多了一个log，能拿多少啊？》回复：

我写的区间修区间查线段树，也是 $O(qn\log n)$，但每次询问 $O(n\log n)$ 是跑满的，民间数据也只有 $20$。/ng

考虑第一次获得的有效信息，一定是对于某个 $x\in[1,n)$，得知目标位置在 $[1,x]$ 还是 $(x,n]$，发现可以递归到子问题。 于是，设 $f(i,0/1)$ 表示：得知目标位置在 $[1,i]$ 后，当前棋子在 $1$ 或 $i+1$，的最小答案。 转移有： $$ f(i,0)\gets \min_{…

### [P9753 [CSP-S 2023] 消消乐](https://www.luogu.com.cn/problem/P9753) **做法一**：哈希 + 栈 考虑用栈来刻画合法子串。 枚举起始点，用栈扫一遍，记录出现了几次空栈，即可做到 $O(n^2)$，$50$ pts。 考虑优化，尝试能否只扫一遍就计算出…

在讨论《关于四次方到线性》回复：

我说一下我的想法。写完 $O(n^4)$ 之后，你发现每个点匹配前面的**同色的点**和**异色的偶点**都是随意匹配的，不改变奇偶性。然后对于**异色的奇点**，你只关心选这些点的数量的**奇偶性**，因此直接记录存不存在**异色的奇点**用来调节奇偶性即可。

若有 $m$ 个 `()` 形如这样排列：`()()()...`。那么合法括号串数是 $\frac{m(m-1)}{2}$。 如果把 $t$ 个 `()` 形如 `()()()...` 放入上述 $m$ 个 `()` 的最左边那一个里面，即：`(()()()...t)()()...m`。则合法括号串数为 $\frac{…

### [ABC427E Wind Cleaning](https://atcoder.jp/contests/abc427/tasks/abc427_e) 根据相对运动，所有 `#` 一起移动转换为只有 `T` 移动。 看这题的第一眼是状态数为 $O(n^2)$ 的 BFS，但如果直接这样做，相当于 `#` 出界了之…

### [ABC426F Clearance](https://atcoder.jp/contests/abc426/tasks/abc426_f) 因为是在线的区间操作，考虑用线段树维护。 既然每种商品之间是独立的，那我们就单独考虑。假设下一次需要购买某种商品 $K$ 个，那么该商品数量 $A$ 有三种状态： 1.…

## [CF2151 Div.2](https://codeforces.com/contest/2151) ### [A. Incremental Subarray](https://codeforces.com/contest/2151/problem/A) 如果有跨段的情况，答案为 $1$。否则子数组只在一段内，…

## [ARC205 Div.2](https://atcoder.jp/contests/arc205/tasks) ### [A - 2x2 Erasing](https://atcoder.jp/contests/arc205/tasks/arc205_a) 若每次操作都选择左上角的进行反转，容易看出存在一种操作…

## [CF2131 Div.3](https://codeforces.com/contest/2131) ### [D. Arboris Contractio](https://codeforces.com/contest/2131/problem/D) 缩成直径最小的时候就是菊花图。 考虑固定菊花图的中心，把该中…

总结：位运算最优化问题考虑**按位贪心**。 ### [P13552 鱼类考古学](https://www.luogu.com.cn/problem/P13552) 因为 $(a+b)\otimes c\le c\le (a\otimes b)+c$，因此我们一定是先 $\otimes$ 再 $+$。 因此问题转化为，…

## [LGR236 Div.2](https://www.luogu.com.cn/contest/232936#problems) ### [T1. 传奇模数](https://www.luogu.com.cn/problem/P13679) 简单题。 [Code](https://www.luogu.com.cn…

## [CF2127](https://codeforces.com/contest/2127) ### A 如果 $a_i$ 为 $0$，等价于要求 $\mathrm{mex}=\max$，无解。 否则，等价于要求 $\max=\min$，则所有数都要相等才有解。 ### B 容易发现只朝一个方向走最优。 ### C…

## 提供一个瓶颈是基数排序的做法 首先对原数组排序，方便考虑。 考虑先枚举 Bessie 堆的大小 $m$， 如果 $a_n$ 是助手堆的，那么答案就是 $a_n$；否则答案是 $\frac{m\cdot(m+1)}{2}$。因此强制让 $a_n$ 放入 Bessie 堆。 那么现在的问题就是 check $m$ 是…

### [Walking in Manhattan](https://www.luogu.com.cn/problem/P10137) 首先发现一个显然但重要的性质， 考虑把题目中的直线互相划分，形成一个网格图，然后我们以每个格子的边为单位，进行移动， 发现从一个**格点**开始走，当且仅当走**过**一段奇数长度的段…

## [CF2130 Div.2](https://codeforces.com/contest/2130) ### A 把所有 $0$ 全部用 $\mathrm{mex}$，剩下全部用 $\mathrm{sum}$ 即可。 ### B 分讨题。 首先每个格子会走至少一遍，那么先累加上，记为 $x$。判掉 $x>s$…

考虑利用 $1\le j using namespace std; using LL = long long; using UI = unsigned int; using ULL = unsigned long long; using DB = double; using LDB = long double; usi…

在文章《矩阵加速图上问题学习笔记》发表评论：

orz。引入题的常数真不是 $8^3$ 的吗 /yun

在文章《相逢是问候，分手是祝愿——NOI2025 游记》发表评论：

相逢是问候，分手是祝愿

在文章《NOI2025 游记》发表评论：

orz

设第 $i$ 个人向左边转移了 $K_i$ 件物品（第一个人向第 $n$ 个转移）（负数代表往右转移），$A$ 是原数组，$x_A$ 表示 $A$ 的平均数，可以列出如下方程， $\begin{cases} A_1 - K_1 + K_2 = x_A \\ A_2 - K_2 + K_3 = x_A \\ \dots…

这是一个有向图博弈，直接考虑 SG 函数。 先设最终状态，即 $\mathrm{SG}(0)=\mathrm{SG}(1)=0$， 那么 $\mathrm{SG}(i) = \mathrm{mex}_{j=1}^{\lfloor\frac{i}{2}\rfloor} \mathrm{SG}(i-j)$， 赛时可以通过暴…

在文章《APIO2025 游寄》发表评论：

真是太牛了! ! ! 我对您的景仰如高山流水般连绵不绝 , 您的光芒万丈荡去了我内心的黑暗 , 您是我偶像啊! ! ! !

[P7801 [COCI 2015/2016 #6] KRUMPIRKO](https://www.luogu.com.cn/problem/P7801) Tag：DP 考虑能不能直接 DP，发现不好计算。 发现答案是分数的形式，考虑 01分数规划，但分子分母并不是关于 $a_i$ 和 $c_i$ 的一次多项式，因此也…

[P7800 [COCI 2015/2016 #6] PAROVI](https://www.luogu.com.cn/problem/P7800) Tag：DP 把问题转换为：选取一些 $[1,n]$ 的子区间，它们的端点编号互质，且这些区间覆盖 $[1, n]$ 的方案数（区间 $[l,k]$ 和 $[k+1,r]…

考虑所有的操作，一定覆盖了这个森林中的若干子连通块，显然每个子连通块也可以看作一棵有根树。 由于这些子连通块的操作互不影响（因为可以把其他连通块的全部忘掉再操作），我们可以单独考虑。 考虑计算以 $u$ 为根的某个连通块至少需要的记忆容量，设 $u$ 的儿子为 $v$， 定义以 $u$ 为根的连通块 $k$ 合法，当且…

我们把 $[a_i,h_i]$ 看做区间，发现任意两个区间的交 $\le 1$，也就是要么交一个要么不相交，然后根据这个进行 DP。 设 $f(i,j)$ 表示考虑了前 $i$ 个区间，$c_{h_i}=j$ 的方案数， 设当前区间为 $[l,r]$，上一个区间的右端点为 $k$， > 计算一个长度为 $x$ 的序列数…

由于是线性基专题，于是直接对整个序列套线性基想了半天，发现不可做。 于是还是要从简单的情况想起。 考虑已经进行完了 $n-1$ 次操作，当前的数是 $x$， 1. 若 $s_n=1$，$1$ 必胜。 2. 若 $s_n=0$，当且仅当 $x=0$ 或 $x=a_n$，$0$ 必胜。 我们发现维护 $0$ 的必胜集合似乎…

Tag：思维题。 把 "相撞后反转" 看成 "直接穿过去"。 对于初始向右的节点，可以直接计入该颜色的贡献； 对于初始向左的节点，暴力枚举前面向右的点，复杂度 $O(n^2)$，考虑优化。 "两个点以速度 $1$ 相对而行，右边点的行驶距离" 等价于 "左边点不动，右边点速度为 $2$，右边点的行驶距离的一半"， 那么…