$$ 泣かないで、泣かないで\\ 梅雨が明ければ、ここにいる\\ またおいで、またおいで\\ 立葵の香を、たよりに\\ $$ $$ 不要哭泣、不要哭泣\\ 梅雨季过后、我就会在这里\\ 请再来吧、请再来吧\\ 以蜀葵之香、作为指引你的凭依\\ $$ --- # 前言 只是一只杂鱼的流水账故事罢了，如果不想看的话，就可以…

可能场切了吧……就当我场切了吧。 手摸一下，发现不合法的充要条件为，存在一个 $w=2$ 的数 $x$，选到他之前的时候恰好花费了 $m-1$，并且在其之前有一个 $w=1$ 的数价值为 $y<x$，在其之后还有一个 $w=1$ 的数价值小于 $x-y$ 或者在其之后全都是 $w=2$ 的。 考虑枚举这个 $x$，然后…

在文章《双射之美——卡特兰数/反射容斥/格路计数》发表评论：

这么优秀！

在文章《题解：P10241 [THUSC 2021] 白兰地厅的西瓜》发表评论：

加一个简单快读跑到了当前最优解，好耶！

# Sol 怎么没人写长剖。 考虑在 LCA 处合并链，那么我们应当对每个节点存储子树内到其的 LIS 和 LDS 信息。通常来说我们考虑对每个终末值存储其子序列长度，这样借助点分治或者 DSU on Tree 之类的可以做到 $O(n\log^2n)$。 考虑换维，对每个长度存储其可能的最小、最大终末值，这样一个点有…

# Sol 首先这类网格问题考虑经典地转化为二分图。具体地，左侧点代表各行，右侧点代表各列，把存在的点转化为连接其行列代表点的一条边。 考虑现在变成了一个什么问题，每个点都可以选一条临边并得到边权，每条边只能被选一次。那么选出来之后必然形如基环树森林，同时任一生成基环树森林也都可以找到相应方案。故而直接贪心地找最大权基…

在文章《题解：AT_arc157_e [ARC157E] XXYX Binary Tree》发表评论：

fixed & fixed qwq

在文章《题解：AT_arc157_e [ARC157E] XXYX Binary Tree》发表评论：

没绷住，想必是 O(n^2) 吧 QAQ

# Sol 不难想到，对于一条路径，表演操作必然形如，在路径上 $w$ 各个前缀最大值处进行若干次使得恰好可以到达下一个前缀最大值处。这么贪心显然是不劣的。 然后就不知道怎么做了。观察数据范围，发现 $n\le 800$，于是考虑暴力。直接拆点，把每个位置的每种可能的前缀 $w$ 最大值状态都拆出来，形成 $O(n^2…

# Sol 不难想到 $k$ 轮一组按组处理。可以用 set 存下一组结束后每个点能走到的位置，由于只是进行了 $k$ 次互换，因此总数据量是 $O(n+k)$ 的。容易发现，每个点向一组结束之后这个点所在位置连边，将会形成若干个环，因为每个点入度与出度要么均为零（也就是未曾交换）要么均为一（总有一个别的数来填这个位置…

# Sol 不难想到如何判定一个点是不是好点，只要以其为根的 DFS 树上只有树上边和返祖边即可。 但这么判还是太慢了。事实上，当找出一个好点以及相应 DFS 树时，就已经可以找到所有好点了。有结论，除了根节点外，一个点为好点当且仅当其子树中有且仅有一条返祖边指向其祖先，且指向的祖先为好点。这是因为当前已经没有前向边与…

# Sol 奶龙题，区间异或等价转化为前缀和的两个点异或，由于异或操作很好的性质直接带权并查集一下，能判断区间和当且仅当前缀和对应端点在同一连通块，直接查到根的异或和异或一下即可。 详细解释一部分： * 不难发现，原先应当在并查集上查二者的路径的异或和，但是直接全部查到根也无妨，重合的部分会抵消掉。 * 使用并查集的正…

在文章《题解：P10197 [USACO24FEB] Minimum Sum of Maximums P》发表评论：

注：本文中的 sz 是集合中包含的所有区间长度之和，忘了给出了/kel

# Sol 首先有一个 trick 就是 $\max(a,b)$ 可以表示为 $\frac{a+b+|a-b|}{2}$。故而我们只需要最小化 $\sum\limits_{i=1}^{N-1}|a_i-a_{i+1}|$。 然后考虑 $K$ 个固定的瓷砖，可以视作他们把原序列分成了若干段。 观察，不难想到各段内部显然是…

# Sol 刻画一下合法图的状态，不难想到可以视作 $1\rightarrow n$ 的一条简单路径，每个节点外挂一个联通块，各个节点外挂的联通块互不相交。 图状压，$f(S,i)$ 表示已经考虑了 $S$ 中的点，路径最后一点为 $i$ 的最大边权和，转移就枚举连通块即可，块是否连通以及块内边权和可以预处理得出。直接…

在文章《压力之下》发表评论：

愿逝者安息，愿生者向阳。

# Sol 其实可以分别处理每个位置值的最优变化序列。不难证明总能将他们合并在一起。 考虑如何快速处理每个位置值的最优变化序列，考虑维护一个值域上的序列，序列各位维护这个数在当前位置左右两侧的出现情况共四种状态，位置移动时只需要单点修改，单次变化可以视作跳到左侧最近的为相应状态的位置，上线段树维护进出区间最小代价即可，…

# Sol 关键在于转化题意，题意等价于选定根为一端的一条路径，不计代价地选择路径上每个点各一个苹果，然后在剩下的苹果中满足依赖性质地选择至多 $k$ 个，求最大价值。 然后不难想到这条路径在叶子结尾显然不劣。于是我们可以把树分为三部分：路径左侧的点，路径右侧的点，以及路径上的点。先序后序各遍历一遍做树上依赖性背包即可…

# Sol 存在显然 DP 状态 $f(i,0/1)$ 表示考虑前 $i$ 个点分段，最后一段是不是倍数的方案数。显然可以 $O(n^2)$ 转移。 假如 $\gcd(d,10)=1$，我们可以开桶前缀和做到 $O(n)$，具体的，$s_r-10^{r-l}s_l\equiv0\pmod d\Rightarrow 10…

# Sol 一个暴力做法是，对于每个点，将其向其可以触发的点连有向边，最后答案就是入度为零的 SCC 数。 考虑优化建图，发现每次连边都是给一个距离前缀连边的形式，因此想到前缀和优化建图，然而图上并不方便直接找到与每个点距离前缀的链。 考虑点分治，每个分治块中所有点按分支中心距离升序排序得到一条虚链，然后对分治块中每个…

# Sol 首先容易想到，每个点与两侧最近的不小于他的点连边，然后跑最短路即可得到答案。考虑最短路径的形式，必然是从等级小的点，走到一个等级最大的点，然后再走向等级更小的点，这样一个峰状。因此我们可以视作是两边同时向峰巅汇集。 考虑分讨三种情况： * 若最大点在二者中间，那么二者会在各自一侧最少步数走到这一点； * 若…

# 思路 ## 单次影响与维护信息 首先考虑每一种修改操作单次对信息的影响，特殊地，将统计历史信息也视作一次操作。比如，区间加，统计区间历史信息和两种操作可以表示成： $$ sum\gets sum+v\cdot len\\ ans\gets ans+sum $$ 同时，我们可以知道要维护三个信息：$len,sum,a…

## sol 是一个 $O(3^{2n})$ 的做法。 考虑霍尔定理，完美匹配要求任意左部点集合 $S$ 满足 $|S|\le |N(S)|$，$N(S)$ 为与 $S$ 相连的右部点集合。 考虑容斥。考虑对每个不合法状态都设计一个唯一的代表元，以方便容斥。设 $f(S,T)$ 表示 $S,T$ 可以完美匹配的概率，那…

# [F2. Marek and Matching (hard version)](https://codeforces.com/problemset/problem/1210/F2) ## sol 是一个 $O(3^{2n})$ 的做法。 考虑霍尔定理，完美匹配要求任意左部点集合 $S$ 满足 $|S|\le |N(…

在讨论《求问 unordered_map》回复：

@[E_M_T](luogu://user/1397028)哦好的qwq

在讨论《求问 unordered_map》回复：

@[MornStar](luogu://user/760824)map 套 pair 会很慢吗/jk

# 前言 考前两天，打算动笔游记了。 怎么转眼就是高一老登了，虽然某种意义上我的 OI 生涯一共也没多久吧。 转瞬间，桃花依旧，物是人非。 在那些地方所度过的，当时只道是寻常。再回首，却已然成为永远无从再度涉足的过去。 无论如何，怀揣着缝缝补补的所谓热爱，还是要充满希冀地向前的不是么。 $$ 「愿群星将你我连结、愿此刻…

在讨论《关于 CSP 随机算法的使用》回复：

@[__vector__](luogu://user/507348)真的吗/jk 那 FHQ treap 不是倒闭了

# Sol 首先，由期望的线性性，把贡献拆到单点上，对每一场计算其胜利的概率即可。 首先已知的局可以不管，未知的局，显然只与其两侧最近的已知局有关。后面运用的一些概率表达在题面最下面有提到，就不额外解释了。 记 $L,R$ 分别为两侧已知局与已知状态相同的事件，$X$ 表示当前局获胜的概率，那么我们就是要求：$p(X\…

# Sol 为什么都在找性质啊，这个不是暴力维护一下就行了吗。 前情提要：模拟赛 T3 放这个一眼秒了然后挂大分。 如果我们把图建出来的话，显然只要满足缩点之后查询的点入度为 $0$ 即可，一个强连通分量中的点显然可以钦定任意一点为该联通分量的赢家。 考虑以第一条链为基准，视其为一棵 DFS 生成树，然后对另外两条链，…