绷，过了七题，我写了六题半。

[A Absolute Difference]

solution

题意：Alice 有 个不相交的闭区间，Bob 有 个不相交的闭区间，它们在自己的实数区间里任意选一个数，问两数之差的绝对值的期望。

做法：只用考虑两两区间的贡献，不交则为中点之差，相交的我们把它们拆出来也就可以算了。注意当有区间时独立点的贡献为零，独立点要有贡献当且仅当全是独立点。时间复杂度 。

[B Binary Substrings]

solution

题意：构造长度为 的 串，使得非空子串的种类最多。

做法：

[C Clamped Sequence]

solution

题意：给出数列 和 ，找到 满足 ，且 ，此时的 。

做法：注意到这实际上是一些常数和一次函数分段的和，断点一共 个，暴力就是 了。

[D DRX vs. T1]

solution

题意：签到。

[E Graph Completing]

solution

题意：给出一张无向连通简单图，问添加边的方式使得变成无向边双联通简单图。

做法：考虑边双联通分量缩点后，一个合法的方案就是将所有树边覆盖了。每条边至少被覆盖一次的计算都是使用容斥的，考虑枚举哪些边没被覆盖，那么就会切割成若干连通块，连通块内的连边是任意的。这些状态容易写进 dp 里，设 表示 的子树以 为最浅点大小为 的连通块的方案数，注意这个方案数直接将容斥系数合进去了，转移是树上背包。时间复杂度 。

具体实现上，我的写法是缩点时预处理出边双连通分量里的情况，那么转移时就是点的权值乘上儿子的连通块大小。

[F Half Mixed]

solution

题意：给出 和 ，要求构造 的 矩阵，使得其纯 子矩阵个数和 混杂子矩阵个数相同。

做法：注意到一个显然的无解条件是 不是偶数时无解。剩下来我们考虑某一个 是偶数，考虑黑白相间的构造，于是等价于要 ，这里我感受了下，写了个暴搜就过了。暴搜就是枚举数从大往小，然后稍微做个全一的剪枝即可。

[G Meet in the Middle]

solution

题意：给出 个点以及两棵连接这 个点的树（有边权），Alice 只能在第一棵树上行走，Bob 只能在第二棵树上行走。现在有 个询问，每次询问 Alice 从 出发，Bob 从 出发，走最短路到达同一个结点，两人共同走过的路程的最大值。

做法：

[H P-P-Palindrome]

solution

题意：给出 个字符串 ，统计 的个数，使得 和 均是某个 的非空子串，且 均为回文串。

做法：

[I Quartz Collection]

solution

题意： 种商品，每种商品只卖两件，价格分别为 和 ，并且买完 才能买 。每个人只能买一种商品的一件。Alice 先买，然后 Alice 和 Bob 轮流买，直到还没买全商品的人买最后一件。问Alice和Bob在最佳策略下买全商品的最小花费。题目有 次永久修改。

做法：容易观察到只需要 分 并排序，分别模 与模 就知道会选哪些了，这些东西全丢到权值线段树上即可。注意下 会影响选值，这要特殊记录一下。时间复杂度 。

[J Referee Without Red]

solution

题意： 行 列矩阵，每个位置有一个值，可以选任意一行或一列按标号 重排，问不同的矩阵数。

做法：

[K Security at Museums]

solution

题意：给出一个多边形，求可以互相看见的顶点集合数量。

做法：

[L Tavern Chess]

solution

题意：告诉你酒馆战棋的机制，问赢输平的概率。

做法：暴搜。

[L Vulpecula]

solution

题意： 个点的树，每个点有一个初始为 的权值，对每个点给出一个操作集合，可以使点权 上给定值，对指定点 的 定义为使与 距离小于等于 的点权都相同的最大点权，对每个点计算 .

做法：