#17. 丁真珍珠和他的小马在做游戏...

Semsue · 2023-06-25 22:53:25 · 题解

A. Tenzing and Tsondu

丁真有 n 匹马，珍珠有 m 匹马，每匹马有参数，两匹马可以决斗，每匹马减去对面的权值。小于等于 0 的马死掉。问最后丁真和珍珠谁能赢。

仔细想一想，类似一个田忌赛马，一个人肯定不会浪费，于是比较两人总和即可。

B. Tenzing and Books

有若干个数，丁真可以从头开始取若干个，得到他们的按位或（\operatorname{or}）。问是否可以构成 x。

把 x 看成一个集合，第 i 个元素有没有看 x 在二进制位 i 是 0 还是 1。条件即为，只能选 x 的子集，求一下并集，最后判断是否是 x 即可。

C. Tenzing and Balls

有 n 个球，选择两个颜色相同的球，删掉这一段。求最多可以删掉几个球。

#### D. Tenzing and His Animal Friends > 有 $n$ 个数，选择若干其子集，集合可以重复，每个集合一个权值 $t_i$。集合一定包含 $1$ 一定不包含 $n$。 > > 要满足 $m$ 个限制，每个限制形如：不包含 $x$ 和不包含 $y$ 的集合的权值和不大于 $v$。 > > $1\le n\le 100$。D. Tenzing and His Animal Friends 比 EF 有趣多了。看到这个数据范围，又把我诈骗到流上去了。思考什么时候是 `inf`。当不存在与 $n$ 连边的时候，显然是。否则就会有一个东西卡下界。自然地想到让那个东西卡满，然后就只用计算不包含其的方案。不断递归下去，复杂度是 $O(n^2\log n)$。 #### E. Tenzing and Triangle > 有一个正方形网格图截了一半，里面有一些点，现在你可以花 $Al$ 的代价，把一个斜边在 $x+y=k$ 上的等腰三角形中的点覆盖，腰长是 $l$。或者花费 $c_k$ 的代价把 $k$ 这个点覆盖。 > > 求覆盖所有点的最小代价。$1\le n,k\le 2\times 10^5$。注意到三角形不交，注意到可以从后往前钦定三角形，注意到可以 dp 来描述这个过程，注意到可以线段树优化。这里 dp 其实是一维的。 #### F. Tenzing and Tree > 给定一棵 $n$ 个点的树，点有两种颜色黑色和白色。定义每一条边的权值为两端黑色点数之差，定义树的权值为每一条边的权值和。对于每个 $k\in [0,n]\cap \mathbb Z$，求出总共有 $k$ 个黑点的树的权值的最大值。 > > $1\le n\le 5000.

一度把边权看成两边黑点数量的乘积，然后就不会做了。

首先怎么看这个黑色的点都应该是一个连通块。根据套路，枚举一个点作为根，然后每个点能被加入的前提是它的祖先都被加入了。

考虑这样一个连通块的贡献，令 sz_i 代表 i 的子树内的黑点个数，那么权值即为 \sum_{i\ne root}|k-sz_i\times 2|，令 root 是重心，把绝对值拆掉：(n-1)k-2\sum_{i\ne root}sz_i。求 \sum_{i\ne root}sz_i 的最小值。那这不就是每个 dep_i 算了一遍吗！直接按照 dep_i 从小到大排序，算贡献即可。

G. Tenzing and Random Operations

给定 n,v,a_1,\dots a_n，进行 m 次操作，每次操作随机一个 i\in [1,n]，然后给 j\in [i,n] 的 a_j 加上 v。求 \prod a_i 的期望。模 10^9 + 7。

首先肯定不能对着式子摁做，拆一下贡献 E(\prod_{i=1}^{n} (a_i+\sum_{j=1}^{m}x_{j,i}))。对于两个不交的事件 E(ab)=E(a)E(b)，那么再根据线性性 E((a+b)(c+d))=E(ac)+E(ad)+E(bc)+E(bd)。

现在要计算有一些位置选 a，有一些位置选 E(x_{j,i}) 的乘积。你发现只有 j 最小的那个才有用。其他不同的 j 是独立的。考虑对着个东西动态规划，记 f_{i,j} 代表前 i 个数有 j 个本质不同的 x。转移有三种情况，都是 O(1) 的。

H. Tenzing and Random Real Numbers

给定 n 个在 [0,1] 之间的实数随机变量 x_1,x_2\dots x_n，m 个条件，每个形如 x_i+x_j\le 1 或者 x_i+x_j\ge 1。

求所有条件均满足的概率模 998244353。

首先 x_i=0.5 的概率应该是 0 所以只用考虑 x_i<0.5 或者 x_i>0.5。设前者染成白色，后者染成黑色。则任意两个同色点之间的条件要么一定满足要么一定不满足。对于异色点，记 y_i=\min(x_i,1-x_i)，如果 x_i+x_j\le 1，且 i 是白点 j 是黑点。那么一定有 y_i\le y_j，同理可得 x_i+x_j\ge 1 时一定有 y_j\le y_i。那么这就形成了一个偏序集，合法的概率就是嵌入全序集的概率。

在已知颜色的情况下，有一个经典的 O(n2^n) 的 dp。考虑直接做这个 dp，枚举每一个点可以时什么颜色。通过枚举发现，对于 \le 1 的条件，前者一定是白，\ge 1 的条件，后者一定是黑，直接转移复杂度 O(n2^n)。