本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 18:56:06

这个循环右移相当不常规吧，所以也很难用常规的状态去描述它。一般的状态没法描述循环右移导致的改变。

我们考虑类似 $f_{ij}$ 的状态，表示匹配到 $s$ 前 $i$ 个字符，$t$ 的前 $j$ 个，所需要的最少的操作数量。

首先有朴素的转移 $f_{i-1j-1} + 1$，当 $s_i = t_j$。

然后，我们可以不让 $i$ 和 $j$ 匹配，而是把 $i$ 塞到前头和某个位置匹配，即 $f_{i-1j} + 1$。

同时，对应着“往前塞”的转移，我们可以也必须有一个“往后放”的转移。不这样的化，往前塞的转移是转移不到 $f_{00}$ 的。这条转移是 $f_{ij} = f_{ij-1}$。

我们想一想这个为啥是正确的。也就是：每一个往前塞的转移，是否都对应前面一个往后放的转移。

这是必须的。因为我们只能从 $(0, 0)$ 出发转移，且只有第一种转移是 $x, y$ 同时加一的；往前塞的转移，会让 $y$ 相对 $x$ 往前移动一步，往后放的转移会让 $y$ 相对 $x$ 往后走一步。如果不是两两对应，还能是什么呢？

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 19:41:38

本来不想打 ABC，unr 看了题，很快啊，一眼序列分治！刚好这几天写了一车序列分治板子，于是就整活写了。

题意是：对于所有子区间，求它的区间和模 $P$ 的加和。只对区间和取模，答案不取模。

首先有简单性质：对于两个小于 $P$ 的数，加起来也小于 $2P$。换句话说，把两个模后的数加起来，再取模，最多就减少一个 $P$。

考虑序列分治，那么区间和由在中点左边的后缀和和中点右边的前缀和组成。不妨把所有在中点右边的前缀和存起来，放到 vector 里并排序，然后枚举左端点确定后缀和。

由于刚才提到的性质，那么后缀和和前缀和凑成的区间和，要么已经小于 $P$，不再需要取模，要么最多只需要取模一次，也就是减掉一个 $P$。我们二分出第一个需要减去 $P$ 的位置，其左边的直接加起来，右边的加起来，然后减去右边的数量个 $P$。

复杂度 $O(n\log^2n)$。

p.s. 序列分治写起来比树状数组顺手，因此抢了个自己榜上首 A。整活成功。

submission

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-04 18:43:48

SD-S00524

这位选手，开场 9min，T1 便过了。很好啊！非常好的开局。

快看！这位选手，把 T2 秒了！我去，他大样例挂了！我去，他上厕所了！我去，他上完厕所，冷静思考的结果是写了一个分数类！我去，他写完了分数类，开始调式子了！我去，他大样例过了！我去，怎么已经五点了！我去，不着急，200pts 稳稳一等了。我们接着看 T3。

T3 20pts，很一眼啊！先上个厕所。T3，50pts，很简单啊！先吃个士力架，好吃！我去，大样例调出来过了！我靠，怎么拍挂了！我靠，初值错了！我草，拍过了！拍过了！两千组！这玩意儿好像很好优化，但是不管了！没什么时间了！快写 T4！

T4，先吃个士力架。诶我草真好吃。这是什么鬼题，我去，他怎么连 12pts 暴搜都不会？？我去，他把性质 A 切了！我草，怎么已经六点十五了？？？不急，检查一下。嗯，很没问题啊！继续吃士力架，好吃。

出场！哎呀我去，258，虽然不高，这不是稳稳的一等吗！蓝勾勾有了！

奥，T2 没 #include <vector>，爆零了！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-06 20:38:49

candies

较小值和较大值，可以看成独立。因为两个极值相等后，就再也不会变化了。那么，我们考虑二分出这 $K$ 次操作能让较小的数全增至 $L$，较大的数减至 $R$。$L\le R$ 时，答案即 $R - L$；否则，只有整个序列的总和是 $n$ 的倍数时极差为零，否则为一。

复杂度 $O(n\log V)$

rcomb

先考虑 $80$ 分的部分分。设 $f(n, i)$ 表示还剩 $n$ 张试卷，第 $i$ 张试卷的期望贡献次数。

那么有转移

$$ \begin{aligned} & f(n, 1) = \frac 1 {n-1} + f(n-1,1) \ & f(n, n) = \frac 1 {n-1} + f(n - 1, n - 1) \ & f(n, i) = \frac 2 {n-1} + \frac{i-1}{n-1} f(n-1,i-1) + \frac{n-i}{n-1} f(n-1,i) \end{aligned} $$

这个复杂度是平方的，能通过 $80$ 分。

对于这个部分分，还有一种思考方向，是设 $f(i, j)$ 表示合并完 $[i, j]$ 区间的期望代价。那么 $$f(i, j) = \sum\limits_{k=i}^j a_k + \frac{1}{j-i} \sum\limits_{k=i}^{j-1} f(i, k) + f(k + 1, j)$$

利用前缀和优化，也可以做到平方。

对于 $100$ 分的数据，考虑拆贡献。每个数到答案的贡献，是上面这个式子转移中的第一个 $\sum$。我们需要知道每个数被包含在了长度为多少的区间。

第 $k$ 个数对答案的贡献，可以考虑它往左边合并的概率。当左边有 $k - 1$ 个数时，有 $k - 1$ 种合并的可能，合并到它的概率是 $\dfrac 1 {k-1}$。右边同理，合并到它的概率是 $\dfrac 1 {n-k}$。当左右操作了一轮后，合并到它的概率增加到 $\dfrac 1 {k-2}$。我们对这个求和，就可以了。

最终的复杂度是 $O(n)$。

game

考虑一个暴力。不妨令 $x_1$ 属于 $A$，我们枚举它和哪个 $y$ 对应，就知道 $A$ 的命令。然后去掉所有可以满足 $A$ 命令的人，看看剩下的人是不是合法。这个可以做到 $O(nV)$。

然后利用 bitset 压位优化。复杂度 $O(\dfrac {nV} w)$

p.s. 这玩意儿假了

tree

我们发现用传统的 dfn 序似乎很难做这个东西。因此考虑相对不常用的欧拉序。

欧拉序上一段区间，是树上的一段路径。同时，两个端点的 LCA，就是这段路径上深度最小的点。在此题里，我们可以维护每个点到根的路径长度。那么由于边权非负，LCA 就是到根最近的那个点。

然后，操作一可以转化为子树的修改，因为修改这条边会让子树内到根的路径加上边权增量。

操作二就是查询 $u \in [s_x, e_x]$ 和 $v \in [s_y, e_y]$ 的 $dis_u + dis_v - 2dis_{c}$ 的最大值，其中 $c$ 是 $u, v$ 的 LCA。由刚才的讨论，我们知道 $c$ 就是 $u, v$ 欧拉序区间内的 $\rgmin dis$。

然后考虑操作三。注意到一个性质，即我们只会取两个端点之一。可以考虑如果不取到端点，调整到其中一个端点，路径长度不减。因此，我们就转化为子树到某个点的最远距离。这和操作二可以用相同的方法。

这个东西看起来还是有点吓人。令 $l, m, r$ 分别代表 $dis_u, dis_c, dis_v$，那么我们用线段树维护区间内 $l, m, r, l + m, m + r, l + m + r$ 的最值。这个是经典的。

然后我们考虑 $[s_x, e_x]$ 和 $[s_y, e_y]$ 的交集情况，讨论 $m$ 在左边还是右边即可。复杂度 $O(n\log n)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-07 14:31:12

我们设 $f(x, y, S)$ 表示当前在 $(x, y)$，包含了的宝藏是 $S$，最少的移动步数。那么答案是 $\max val_S - f(x, y, S)$。

考虑转移。前两维的转移是简单的。由于转移顺序不确定，可以最短路。后面的 $S$ 怎么动态维护？

计算几何中的射线法，可以用来判断某个点是否在某个多边形中。具体的方法是：从这个点做一条直线，看其经过这个多边形的多少条边。如果经过奇数条即是在内，否则在外。我们可以沿用相同的方法，每次转移时从每个宝藏平行向右做一条直线，看是否和新扩展出的点交。若交了，则其在 $S$ 中取异或。

这样用最短路转移即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-11 12:39:34

本题有一个非常好的性质：没强制在线。所以我们可以离线下来搞。

具体怎么做呢？本题的核心就是点修、区间第 $k$ 大、区间求排名。我们知道，CDQ 分治和整体二分分别可以很方便并且快速地解决区间排名以及区间第 $k$ 大问题。那么我们分别用这两种算法做不同的操作就可以了。

还剩下前驱和后继，怎么处理？某个数的前驱，可以先算出严格小于这个数的数量 $k$，然后求第 $k$ 大。某个数的后继，可以算出小于等于这个数的数量 $k$，然后求第 $k + 1$ 大。

这时我们发现，我们需要将这两个操作组合起来。我们可以把询问拆开，先跑 CDQ 分治，得到 $k$，然后再跑整体二分，得到最后的结果。

实现起来细节不特别多，主要是主函数中拼接操作的部分不怎么好写。

但是跑起来飞快，没怎么卡常就跑到最优解第二页。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-18 10:46:01

$nk^2$ 显然。考虑优化。

转移有两种，一种是 $r_k \lt l_i$ 的，转移是 dp[k][j - i + k + 1] + r[i] - l[i]。

另一种是 $r_k \ge l_i$ 的，转移是 dp[k][j - i + k + 1] - r[k] + r[i]。

由于我们把包含的区间删掉了，因此 $l$ 随 $r$ 增。因此，我们可以用单调队列维护第二种转移的最大值。从队头弹的时候，我们知道这个点会变成第一种转移，维护一个最大值就好了。

但是，我们状态的第二维怎么处理？第二维是 $j - i + 1 + k$，因此我们可以对于每一个 $j - i + 1$，维护出 dp[k][k + t] 的最大值，放到 $n$ 个单调队列中即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-18 17:26:40

贪心是显然的，按照右端点排序，同时维护一个堆存放每间教室的最后一场活动结束时间。每次看能不能放进去，能放就尽量放。这个贪心是经典的。

只有所有的教室都占用了，我们才会开新教室用。因此，我们可以二分出来 $mn_i$，表示 $i$ 一定会用的最少教室数量。显然算出 $mn$ 我们就做完了。

单次二分的过程，是我们模拟这个贪心过程，看看这个位置会不会选到。考虑整体二分。

整体二分到值域区间 $[L, R]$ 区间时，我们要看哪些点的 $mn$ 小于等于 $mid$。可以通过线段树区间加，看区间最大值是否小于 $mid$。

好牛逼的题

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-21 10:06:09

KM 算法解决的是二分图带权最大完美匹配问题。

权均为一的时候，贪心地尽量匹配是最优的，因为只要匹配了，带来的收益都一样。但如果权不同，就无法简单贪心了。

我们引入顶标的概念。每个点有一个顶标，记为 $d_x$。一组可行顶标，需要满足 $d_x + d_y \ge w_{xy}$。我们再定义，一个顶标生成一张相等子图，其中包含所有点，以及满足 $d_x + d_y = w_{xy}$ 的所有边。

顶标有什么用？有一个性质，即：如果一组可行顶标生成的相等子图中有一个完美匹配，那么这就是原图的最大权完美匹配。

这是因为相等子图中的边都是使得 $d_x + d_y = w_{xy}$ 的，而原图的边是 $d_x + d_y \ge w_{xy}$。只要相等子图中有完美匹配，其权一定是最大的。

那么，我们现在的问题就是，选择一组合适的可行顶标，使得其生成的相等子图中有最大匹配。我们不妨先构造任意的顶标，随后调整它。

先让最开始每个右部点的顶标为零，每个左部点的顶标，为它所连的边的最大权。这样，最开始的相等子图就是最大权的那些边。在这张相等子图中跑匈牙利算法，看可否得到完美匹配。

如果得不到，我们就要调整顶标。可以将左部点顶标增加 $d = \min \{d_x + d_y - w_{xy}, d_x + d_y \gt w_{xy}\}$，右部点减少这个量。这样，我们保证了增加至少一条边，同时原来的边保存，而且增量也尽可能小。然后我们重复跑最大匹配，直到找到完美匹配。

这个复杂度最差是 $O(n^4)$。考虑优化。我们发现，每次加边时，原来的交错树依旧可用。可以改用 BFS，每次扩展新点时候只是入队，不从头增广。复杂度是 $O(n^3)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-23 16:49:12

要求

$${n\choose m} \bmod p$$

其中 $2 \le p \le 10^6$，$1 \le n, m \le 10^{18}$。$p$ 不一定是质数。

如果 $p$ 是质数，我们可以直接用卢卡斯定理求解。

考虑将 $p$ 分解，然后解出 $n\choose m$ 模 $p$ 的某个质因子次幂的值，最后用 CRT 合并。

那么问题转化为求 ${n\choose m} \bmod p^k$。

拆组合数定义，即 $\dfrac {n!}{m!(n-m)!}$。由于逆元不一定存在，不能直接计算。

考虑计算 $\dfrac {n!} {p^k}$，其中 $k$ 是最大的整数使得 $p^k \mid n!$。然后得到原式为 $\dfrac {n!p^{k1-k2-k3}}{m!(n-m)!} \bmod p^k$。把指数拆出来，就可以求逆元了。

现在的问题是，求 $\dfrac {n!} {p^k}$，也就是把 $1$ 到 $n$ 中 $p$ 的倍数全部抛除，计算剩下的数的乘积。

$p$ 的倍数的乘积是 $\lfloor \dfrac n p\rfloor p^{\lfloor \frac n p\rfloor}$。

不是 $p$ 的倍数的部分，由于 $p^k \le 10^6$，可以按照 $p^k$ 分成许多块，每一块的乘积都是 $\prod\limits_{i=1,(i,p)=1}^{p^k} i$。最后剩下的散块，可以直接暴力。

然后可以根据逆元计算模 $p^k$ 的组合数，之后用 CRT 合并解。