在文章《题解：P14381 【MX-S9-T4】「LAOI-16」顽疾》发表评论：

前面这个计数手法怎么出自 xyd 模拟赛啊/xk

**贡献延后计算**。什么意思？分析一下这个过程，设未被招聘上的人数为 $cnt$，若当前 $s_i=0$ 大家都一样，否则 $s_i=1$ 则 $c_i\le cnt$ 都一样；而且 $cnt$ 是不降的。如此，我们在 dp 的时候将所有数划分为 $\le cnt$ 和 $> cnt$ 的两集合 $(S_0,S_1)…

帅爆了这个题。 二分答案，初始有 $x$ 的钱，转换为判定性问题。不妨先考虑链的情况，一个结论是，每次将里程换成钱时要么全部换完，要么换到的钱能恰好使用到下一次兑换；否则考虑调整，设两次相邻的兑换分别在 $x,y$，且在 $x$ 处既没有把里程用尽，到 $y$ 时钱也没有用完，则必然可以取一个 $\varepsilon…

在讨论《举报 lsj2009》回复：

收到

一个比官方题解好理解得多的做法！！！ 需要一定线性代数/生成函数基础。 问题其实就是给定线性空间 $R,B$ 求 $\dim(R+B)$（注意这里是和而非并）。使用线性代数维数公式，得 $\dim(R+B)=\dim(R)+\dim(B)-\dim(R\cap B)$。 ::::info[Proof] 设 $\dim(…

题解要么是倒着扫、要么是选择删数，但其实不断加数也能做！！ 容易注意到，第 $k=k_0+1$ 的答案肯定是在 $k=k_0$ 的基础上新加入了一个物品。这个物品需要满足，其和在其之后的所有被选择物品 $a_i$ 之和，需小于所有在其之前的未被选择物品的 $a_i$。记 $b_i$ 为 $a_i$ 减去所有 $j\ge…

给定 $T$ 如何求出 $S$？ 1. 选取尽可能多（设选了 $k$ 个）的 `()` 直至无解（具体的，不断选取接下来的首个 `(` 或 `)`）。这显然是最优的。删去最后一个 `()` 之前得所有未在 `()` 之中的括号。 2. 从前往后扫一遍 $T$，没有匹配上的括号在 $S$ 中不优：以 `)` 为例，若其在…

在 $\ell$ 确定时如何求出最小惩罚分？可以直接构建出费用流模型（其实并不完全是，因为这里要优先最大化费用，但其实后面也说明了，在本题中流量最大化和费用最大化是一致的）！更进一步的，可以模拟费用流（贪心）：从小大扫时间，攻击当前可以攻击的 $P_i$ 最大怪兽。这个模拟费用流过程不涉及任何反悔（也就是能匹配的必然不…

首先曼哈顿转切比雪夫，每次可以走到一个正方形边框上。有解的一个必要条件是 $\sum D_i\ge 2\max{D_i}$，否则走一次 $\max{D_i}$ 长的步永远都回不到原点；其实这也是充分的，我们先给出一个重要引理： - 若 $\max{a_i}\le r$ 且 $\sum a_i\ge r$，则必然可以通过…

对于每个分割排列，钦定在其分断点的必须构成逆序（不满足该条件的分割排列直接对应唯一的排列 $p$，暴力 check 即可），其余地方顺序。枚举第一个排列的分段点，变成两条链，不妨先假设对于其余所有分割排列 $p^{-1}_{q_{i-1}} // #define int long long #define ll lon…

首先判断合法性。如果存在 $L\le i p_j>p_k$ 则不合法；找到 $\max\limits_{p_i>p_j}{p_j}$，如果存在 $x p_j>x$，不合法。上面两者均容易在 $\mathcal{O}((n+q)\log{n})$ 复杂度内判断。 对于有解的询问，找到 $v=\max\limits_{L\…

将三目运算符刻画成，每次选取一个长为 $3$ 的子串变成 $0/1$；令函数 $f(s,t)$ 返回 $s$ 能否进行如上操作后变成 $t$。当 $t$ 固定时，构建自动机 $A_t$，若字符串 $s_1,s_2$ 满足对于任意 $01$ 串 $s$ 有 $f(s_1+s,t)=f(s_2+s,t)$，则显然可以把 $…

注意到小段长度 $>1$ 肯定不优，直接记 $f_i$ 为 $[i,i]$ 是一个小段，在 $\le i$ 的前缀划分的最大段数，暴力是 $\mathcal{O}(n^2)$ 的，可以发现转移来的 $f_j$ 是一个前缀再加上 $\mathcal{O}(\log{V})$ 个零散点（证明和后文的一个结论一致，这里略去）…

逐点牛顿迭代。 对 $G$ 求关于 $x_n$ 的偏导得： $$ \begin{aligned} \frac{\partial}{\partial{x_n}}G&=\frac{\partial}{\partial{x_n}}\ln{F}\\ &=\frac{1}{F}\times\left(\frac{\partial…

第一想法是逐位确定，但是位与位之间的割裂难以提出复杂度优秀的做法。转换视角：从大往小考虑所有数 $x$，找到一个字典序最小的下标集合 $S$，然后将 $i\in S$ 的 $b_i$ 赋成 $x$ 并满足存在解。判断性问题即区间选点问题，判断最少选择点数（记为 $c$）是否不大于 $x$ 在 $a$ 中出现次数（记为…

$x=0$ 怎么做？即 $n$ 个向量全部线性无关，每加入一个向量 $\dim$ 加一，则答案即为 $\prod\limits_{1\le i\le n}\left(2^k-2^{i-1}\right)$，因为前 $i-1$ 个向量张成空间有 $2^{i-1}$ 个元素。 否则，可以发现 $x$ 取任何值答案一样，否则…

$A$ 中非 $c$ 位置较少，将其分解为 $B$ 与全 $c$ 矩阵 $C$ 之和，则 $$ B_{i,j}=\begin{cases} 1-c & i=j\\ -c & i\ne j\wedge i\mid j\\ 0 & \text{otherwise} \end{cases} $$ 将 $\det{A}$ 展开…

写出答案式子： $$ \sum\limits_P \sum\limits_Q [f(P)=f(Q)][P\cap Q=\emptyset]\prod\limits_{i\in P\cup Q} a_i $$ 对 $[f(P)=f(Q)]$ 限制进行容斥：即对于每一位 $x$ 应有 $[x\in f(P)]=[x\in…

默认树的先序遍历是优美的。将 dfs 序改为：对于每个节点可以选择是否翻转其左右儿子（称为翻转一个节点），最终得到的树的先序遍历。dfs 序总数为 $2^{2n-1}$ 次。 提出很强势的结论： - 记子树 $u$ 的权值是所有在 $u$ 子树内出现恰好一次的颜色构成的集合。 - 我们称对于 $u$ 子树的翻转操作是同…

考虑答案形式，一次操作 $(i,i+1)$ 若 $a_i\ge a_{i+1}$ 则在 $i+1$ 上放一个 $\leftarrow$，若 $a_{i+1}\ge a_i$ 则在 $i$ 上放一个 $\rightarrow$。则操作情况形如若干个 $\rightarrow\rightarrow\rightarrow\l…

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

水哥/ll

在文章《题解：P12543 嘟嘟嘟》发表评论：

一样的做法！

## Preface 场上提出了 $\mathcal{O}(\sqrt{n\log{n}})$ 的做法，但是 system test 荣获 25pts/xk ## Description 存在一个初始固定的正整数 $n$，可以进行若干次对交互库的询问，每次询问可以花费 $|a|$ 的代价给出一个序列 $a$，交互库会返…