赛时花费 $3\text{h}+$ 通过大样例，自造数据 $1.07\text{s}$，希望别死。 设确定 $w$ 后，从大到小排序后的 $\frac{a_i}{w_i}$ 数组为 $b$，不妨设 $b_i$ 对应的就是 $a_i,w_i$。 观察一个不合法的情况，形如取了一个前缀到 $b_x$ 之后，还剩 $1$ 块…

在文章《[ABC430G] Range Set Modifying Query 题解》发表评论：

取块长为 B=sqrt(mn) 似乎可以做到 O(qm*sqrt(nm)) 的更优复杂度？

实际上只需要模拟整个流程即可。 先尝试 $S\to T$，可能会有阻碍，于是 $S\to L_1$，其中 $\displaystyle L_1=\displaystyle\min_{b_i\isin[S,T]}a_i$，拿到通过 $S\to T$ 所有门的钥匙。然后尝试 $S\to L_1$，可能会有阻碍，于是 $S\…

先考虑套路地按位确定，对于一个 $l$，操作 $(l,r)$ 有三种可能：使字典序减小、不变或增大，不妨将这三种情况对应的 $r$ 集合设为 $C_l,E_l,D_l$，则 $C_l=\{r\mid a_l>a_r,r>l\},E_l=\{r\mid a_l=a_r,r>l\},D_l=\{r\mid a_l l\}$…

一条 $(1,1)\to (2,n)$ 的路径形如先在第一行走一个前缀，然后往下走一格，然后在第二行走一个后缀。 枚举往下走一格的位置 $x$，则可以通过预处理前后缀最大最小值得到一个限制 $[L,R]$，表示能够走出 $(1,1)\to(1,x)\to(2,x)\to(2,n)$ 时 $f(l,r)$ 需要满足 $l…

考虑 $a_i$ 均为偶数的情况，此时 Bob 可以通过重复 Alice 上一次的操作来最大化自己的分数，此时两人分数均为 $\displaystyle x=\frac{\sum a_i}{2}$，证明：若 Bob 没有重复 Alice 的操作，则 Alice 可以通过重复 Bob 的操作，让自己的分数至少为 $x$。…

从右向左尝试让 $t_i$ 匹配 $s$ 中的一个字符。显然匹配到的 $x_i$ 要先满足 $s_{x_i}=t_i,x_i\le i$。同时为了让已经放好的 $t_i$ 不被其他字符覆盖，$[x_i,i]$ 这个区间不能被其他区间包含，即 $x_i\le x_{i+1}$。直接拿一个指针扫即可。于是得到 $s$ 中每…

每次操作都将位置为 $c$ 的数移动到位置 $\displaystyle f(c)=c-\lfloor\frac cy\rfloor$，注意到 $f(x)$ 值唯一，可以考虑求出其反函数 $g(x)$，然后尝试计算 $g^x(k)$（$g^x$ 表示 $g(g(\ldots g(k)))$，其中 $g$ 有 $x$ 层…

直接考虑整个集合有点困难，考虑从单个元素入手，计数这个元素在多少种情况中在最终集合里面。 我们将这个元素到最小元素的距离称之为这个元素的安全度，则删除最小值后，集合内所有元素的安全度减一；加入 $x$ 时，所有 $>x$ 的元素安全度加一。（元素值相等时,钦定后加的元素比较大） 有了安全度就可以直接对一个元素 $x$…

由于操作完必须形成一个排列，于是每条边必须被操作偶数次，否则这条边左右不能平衡。 进一步发现，每条边最多操作 $2$ 次，考虑一个由操作数不为 $0$ 的边构成的连通块，只需要从左往右依次给每条边操作 $2$ 次就可以将连通块内所有点错位。 于是一条边只有选和不选两种情况，要求不能有连续两条边不选，代价为选的边的边权之…

首先可以直接 dp，先按 $r_{1,i}$ 排序，设 $f_i$ 表示考虑到第 $i$ 个人且选择第 $i$ 个人的最大价值，则转移为 $\displaystyle f_i=p_i+\max_{j r_{k,j}$ 的 $j$ 构成的集合。注意到整个 dp 是 $\mathcal{O}(n^2)$ 的，于是只需要快速…

首先 $a$ 的顺序没啥用，若设 $b$ 为 $a$ 的桶，则我们只关心是否有 $b_x>k$，操作时也只会根据 $b$ 的情况来改变 $b$。 观察一次操作时 $b$ 如何改变，可以看作每个 $b_i$ 都拿出了 $b_i-1$ 这一部分，挪到了 $b_{i+1}$。 这样就很像一个技巧型 dp 了，但是这里介绍一个…

实际上这个绝对值没啥用，先把这个东西去掉，这样对于 $a_i$ 的决策就变成了 $\{0,a_i-p,p-a_i\}$ 选一个。 注意到最终得到的结果实际上是一个关于 $p$ 的一次函数，设为 $kp+b$，则可以根据 $k$ 的正负分类讨论。 若 $k>0$，则求答案时 $p$ 取 $l$，那么现在的问题就是，对于…

翻译一下，$(1,l,r)$ 实际上就是 $a[l,r]$ 中不能有 $[0,k-1]$ 内的数，且必须有 $k$；$(2,l,r)$ 实际上就是 $a[l,r]$ 中必须有 $[0,k-1]$ 中所有数，且不能有 $k$。对于 $>k$ 的数没有限制。 若只有 $c=1$，将 $a_i$ 全部赋值为 $k$ 即可满足…

容易发现，一个方案要合法，其每一行的黑格子必须形成一个区间。证明是取同一行任意两个点 $a,b$，则 $a\to b$ 步数必须为 $|a-b|$，这要求 $[a,b]$ 均被涂黑。 再进一步观察，发现若从上往下看每一行，区间的左端点必然是先减后增，具体证明是，若有先增后减，各取增段和减段任意一行的左端点，这两个点只能…

拆方差式子： $$ \begin{aligned}&\frac{1}{n}\sum_{i=1}^{n}(a_i-\bar{a})^2\\&=\frac 1n\sum_{i=1}^na_i^2+\bar a^2-2a_i\bar a\\&=\left(\frac 1n\sum_{i=1}^na_i^2\right)+\b…

在文章《[P8346] 「Wdoi-6」最澄澈的空与海 题解》发表评论：

我草我当时他妈在写什么，已修改

先计算最大加次大减 $C$，然后变为 $\max_{i,j\in S}[i+j #define pb emplace_back #define mp make_pair #define pob pop_back using namespace std; typedef long long ll; const ll ma…

先考虑 $u$ 在 $S_r$ 内需要满足的条件，首先在选择 LCA 时不能选在 $u$ 子树外的点，否则 LCA 只能为 $u$ 的祖先。接下来可以强制钦定 $u$ 被选择，那么只要接下来选的点都在 $u$ 子树内，LCA 就必然是 $u$。于是需要满足 $k$ 个点能在 $u$ 子树内选完，即 $\text{siz…

若 $c_i$ 的标签能被现有标签替换，则需要满足 $\displaystyle\lceil\frac {c_i}x\rceil=c_j$，进一步可得 $c_i\in[x(c_j-1)+1,xc_j]$。于是枚举 $x$，然后枚举 $x$ 的倍数 $k$，设 $b_i$ 表示满足 $c_j=i$ 的 $j$ 的个数，则…

注意到赛事公告提醒了第三组数据的问题，即任意一对绿色点之间没有黄色和蓝色点。于是绿色点是一个连通块。 然后就有一个很明显的 dp，设 $f_u$ 表示以 $u$ 为根的子树方案数，这里令 $u$ 为绿色。于是转移时每棵儿子的子树独立，并且额外有全涂蓝色或黄色两种情况，于是转移 $f_u=\prod_{v\in\text…

@[Departure_](https://www.luogu.com.cn/user/544520) 这么强！！！！！ 拿样例来研究一下，容易发现这个 $a(u)$ 的钦定实际上可以看作一条边，于是在原图上提出了一个内向基环森林，然后在这个森林上的每一个点在走若干步后一定能到达任意点的邻居。 首先每棵树的环外点深度可…

很诡谲的一道题。 首先特判菊花，答案为 $1$。 不难发现题目要求每次行动都往父亲走，这显然表明父亲边的颜色必须与这个点连的其他边不同，这个条件是必要的。 根据这个条件可以发现，如果树上没有链，即每个点要么是叶子要么有两个儿子，那么可以令 $\text{col}_i=\text{dep}_i\bmod 2+1$，这样一…

在文章《CSP-S 2025 游记》发表评论：

p在哪？p在哪？p在哪？

条件就是在说，前一项最多比后一项大 $D$。 考虑从大到小地填数。设当前填到数值 $i$，$c_i$ 表示序列中有多少个 $i$，那么这些数只能插到当前序列的头部，或者满足 $x\le i+D$ 的 $x$ 后方。设 $s_i=s_{i-1}+c_i$ 即 $c$ 的前缀和，则可以插入的空数量为 $T=s_{i+D}-…

因为整个序列都要被划分，且显然这个区间长度具有单调性，于是考虑一段区间 $[l,r]$ 能做到 $c$ 相同的条件。 显然，$\forall l\le i\le r,c\mid b_i$，于是 $c\mid \operatorname{lcm} b_i$，取最少的限制，即 $c=\operatorname{lcm} b…

字典序最小化的一个一般做法就是按位确定。设 $t_i$ 翻转后对应 $t_{to_i}$，从左到右逐位确定 $t$，若当前确定 $t_i=c$，其中 $c$ 是还剩有的最小字符，为了使 $t$ 翻转后 $t'_i$ 不变为一个更大的字符，需要尽可能使得 $t_{to_i}=c$。 如果能够满足，就向两端填入 $c$。否…

如果拼接后字符串满足最后两个条件，那这个串的长度必然是奇数，于是可以忽略第一个条件。 每个字母出现次数的奇偶性显然可以压成一个 $26$ 位的二进制数，设这个二进制数为 $a_i$。那么本质上是求满足 $a_i\oplus a_j=(2^{26}-1)\oplus 2^x$ 的 $i,j$ 对数，注意到至多存在一个 $…

在文章《[CF2150C] Limited Edition Shop 题解》发表评论：

对称的，所以限制也是倒过来的，于是 dp 也得倒过来

小清新思维题！ 题目加粗了**有解**条件，这是一个关键信息。 注意到有向图形如若干个 SCC 缩点成一个 DAG，显然 SCC 内 $c_i$ 相等，而拓扑序下最大（即没有出度）的 SCC，其 $c$ 值必然是最小的，于是从小到大枚举 $c$，对这些 $c$ 相等的点所在的 SCC，内部可以通过一遍 dfs 直接确定…