每个时间最多只有一个前置事件，那么事件之间的关系可以看做一个森林。题目所求的方案就是这个森林的一个子图，按照回想每个子树的根节点，再沿着树边联想的方式遍历每个关键点。代价就是选中的子图中包含的每个子树的根节点的点权和加上边权和。 还需考虑题中关于脑容量的额外限制。记脑容量为 $K$ 的限制为限制 $K$。对于一个子树，…

设 $dp_{i,x,y}$ 表示考虑 $a_1$ 到 $a_i$，序列最后两位分别为 $x$ 和 $y$ 的方案数。 考虑 $dp_{i-1,x,y}$ 对于 $dp_i$ 的贡献。序列中的每一位都不同，所以一个 $a$ 只能和 $a+1$ 和 $a-1$ 换位，所以序列最后三项只有一下情况： ``` x y a[i…

显然得到的信息越多越容易确定胜利，因此答案具有单调性，考虑二分并检验得到信息的场馆数量 $mid$。 因为我们可以在比赛开始后再安排双方球员的对阵关系，所以不确定性来源于一对对阵取得的收益来自哪个场馆不确定。然后就是经典的田忌赛马策略：将双方球员和场馆按权值升序排列，逐一考虑己方队员，考虑他能战胜的所有对手并分情况讨论…

考虑对于一个 $b_i$，它右侧的数与它交换会减少，所以它由它左侧的 $a_j$ 贡献 $a_j$，右侧的 $a_j$ 最多贡献 $a_j-(j-i)=a_j-j+i$。即 $b_i=\max(0,\min_{k=1}^ia_k,\min_{k=i+1}^na_k-k+i)$。所以 $b_i$ 单调不减。若继续观察 $…

只要随机生成 $\sqrt p$ 个字符串就会出现哈希值相同的字符串（这里涉及一个数学概率论中一个有趣的悖论：[birthday paradox](https://baike.baidu.com/item/%E7%94%9F%E6%97%A5%E6%82%96%E8%AE%BA/2715290)），所以随机生成字符串并…

注意到 $u_i$ 和 $v_i$ 之间存在一条长度为 $1$ 的直接连边，所以这个路径的贡献为 $0$ 或 $1$，故 $\forall f(x)\le 1$，否则无解。 若 $f(x)=1$，则 $a=0$，且 $u_i$ 和 $v_i$ 之间任意其他路径上至少存在一个边权为 $0$。将所有边权为 $0$ 的边删除…

注意到最优区间的长度一定是 $2$ 或 $3$，直接用线段树维护连续 $2$ 格和连续 $3$ 格的和的最大值。 区间加细节较多，要分成区间左侧、区间前半段、和区间右半段共三段维护，还要讨论更新区间的长度，具体见代码。 ```cpp const ll N = 1e6 + 10, inf = 3e15; ll a[N],…

暴力枚举三个分割点跑 DFS 即可，考虑剪枝：定义两个衡量操作价值的数：$v_1=\sum [a_i=a_{i+1}],v_2=\sum[a_i>a_{i+1}]$。显然 $v_1$ 应该尽量大，$v_2$ 应该尽量小。用这两个标准比对修改前后的序列剪枝。 ```cpp const ll N = 20, MAX = 6…

若限定区间内 $0$ 和 $1$ 的个数均多于 $k$ 个，则选 $k$ 个 $0$ 和 $k$ 个 $1$ 得到 $2^k-1$ 显然最优。 否则必然是其中一个多于 $k$ 个，另一个不够。贪心得到最优策略为其中一个序列全选足够的那种数字，在另一个序列中尽可能把不够的那种数字放在高位，最终答案中这些位置上就是 $1$…

先考虑修改前的答案。统计前缀中 `J` 的个数和后缀中 `I` 的个数，每一个 `O` 前后相乘加起来即可。 若添加 `J`，则贪心地加在开头，对于每一个 `O`，贡献即为后缀中 `I` 的数量。添加 `I` 同理。 若添加 `O`，则枚举每个位置插入，贡献计算方法不变。 复杂度线性。 ```cpp const ll…

最优策略下，第一个开始做的任务一定是准时开始的。若我们决定第一个做任务 $i$，那么总用时即为 $s_i-1+\sum_{j=i}^{n}t_j$，答案即为 $\max(s_i-1+\sum_{j=i}^{n}t_j)$。 用一颗线段树维护每一位开始的总和。插入新任务 $(s,t)$ 时，给 $[1,s]$ 加上 $t…

总花费是答案路径上所有相邻边的权值之差，所以由此可以推出部分分的做法：把原图中所有边当做点建一个新图，连接共点边作为新边，权值为原图中边权之差。建一个超级源点和一个超级汇点，跑最短路即可。 优化比较明确：在一个点上改变自身权值多次，只要始末态不变，花费就不变，所以只需要给原图中的点的连边按照边权排序，给排位相邻的边建新…

这题从开始写到通过时间跨度有点大所以现在已经忘记怎么做的了（ 反正只是卡了常就过了？ ```cpp const ll N=2e5+10; ll pren,n,siz,ans,l1[N],r1[N],l2[N],r2[N],pos[N*2],cnt[N*2],cur[N*2],le1[N*2],le2[N*2],gr1[…

- [13](https://generals.io/replays/p1ZGSChDZ?p=Shinku)：13。7（2）。5。3。 - [13](https://generals.io/replays/L0YylQ5VW?p=Shinku)：13。7（1）。4（1）。3。2。 - [13](https://gene…

树剖板子。痛苦卡常。 ```cpp il int read() { int re = 0; char in = getchar(); while (in '9') in = getchar(); while (in >= '0' && in siz[hs[p]]) hs[p] = nxt[i].x; } } } voi…

在讨论《联合省选 ++RP 专贴》回复：

exp壮心不已！

在文章《题解：P11703 [ROIR 2025] 个人 OI 比赛的原则》发表评论：

啊呀终于过审了。。。

01 背包板子+DFS 拼凑目标值。用 `bitset` 可通过。很模板的题，评蓝虚高。 设 $dp_{i,j}=0/1$ 表示考虑前 $i$ 个题目，得到恰好 $j$ 分是否可行。转移：$dp_{i,j}=dp_{i,j-k}\lor dp_{i-1,j-k}$。 ```cpp const ll N = 1e5 +…

首先可以发现选择的牌必须产生贡献（否则只会占用空间不如不选）。其次产生贡献的一对牌之间最多再选择一张牌（否则前一张牌会被扔掉），所以最佳选择方案一定形如 AABB 或 ABAB。 预处理每个 $A_i$ 上次出现的位置 $pre_i$（未出现过则为 $0$）。 考虑 DP。设 $dp_i$ 表示消除 $A_i$ 的最大…

在文章《题解：P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2》发表评论：

《CSP-S 2025》

本题解中称牛为“点”，$D(A,B)$ 表示点 $A$ 与点 $B$ 的曼哈顿距离。 先讲做法再讲成立的理由。 ### 做法  枚举两个连线平行于 $y=x$ 的点（图中黑点），则图中红线范围内…

既然替换后的数是与所选的数的差，那最佳选择肯定是最大值和最小值的平均值。时间复杂度 $O(Qn\log n)$。 ```cpp const ll N = 2e5 + 10, MAX = 40, inf = 3e9; ll Q, n, a[N]; vector ans; int main() { sync_off; ci…

首先贪心。最佳方案中，将原本不在同一位置的多于 $3$ 只河狸移动到一起相比将其两两分组（奇数个则保留一组 $3$ 只）肯定不优，所以只需要考虑一组 $2$ 只或一组 $3$ 只。 其次 DP。将 $a_i$ 升序排列。设 $dp_i$ 表示考虑前 $i$ 只的最小花费，则 $dp_1=+\infty,dp_2=a_2…

设 $dp_{i,j}$ 表示 $\sum_{k=1}^i a_k=j$ 的方案数。转移是平凡的，与背包问题类似。 暴力的做法：假设所有数都是前一个数加一，即构造 $a_i=i-1$，总和就是 $n(n-1)/2$。将 $a_i$ 减 $2$ 会使所有数总和减少 $2(n-i+1)$，所以目标就是用不同的 $(n-i+…

在文章《关于数论分块时间复杂度和算法正确性的详细证明》发表评论：

哦还可以

在文章《关于数论分块时间复杂度和算法正确性的详细证明》发表评论：

还能发评论吗

在讨论《数论分块证明求助》回复：

@[Acerkaio](luogu://user/514850)

在讨论《数论分块证明求助》回复：

数论分块块长结论：对于正整数 $n>p$，$\forall 正整数i\land \lfloor n/p \rfloor=\lfloor n/i \rfloor,i\le\lfloor \frac{n}{\lfloor n/p\rfloor}\rfloor$。 证明：①当 $p\le \sqrt n$ 时： 结论 a：$…

在讨论《数论分块证明求助》回复：

@[Acerkaio](luogu://user/514850) [link](https://www.luogu.com.cn/paste/gwpnvutw)

本蒟蒻尝试证明数论分块算法的正确性，在最后一步遇到困难，求大佬帮助 QAQ [link](https://www.luogu.com.cn/article/lx37xd01)