2022 HDU 多校 2

Link

A Static Query on Tree

把所有 $A,B,C$ 集合中的点拖出来建虚树，然后在虚树上统计每个子树中 $A,B$ 的点的个数和到根的链上 $C$ 的个数即可。

复杂度 $O((\sum |A|+|B|+|C|)\log n + n\log n)$ 。

Submission

B C++ to Python

去掉 std::make_tuple 即可。

Submission

C Copy

由于所有查询的位置和复制的区间都不超过 $n$ ，暴力复制即可。操作次数为 $20000n$ 。

Submission

D Keychains

只要能求出其中一个圆和另一个圆所在平面的两个交点，就只需要判断是否一个在圆内一个在圆外了。

首先任意求出两个平面的两个交点 $C_1,C_2$ ，然后可以求出交线的向量 $L$ 。

接下来考虑求出 $O_2$ 在直线的投影。令 $V_1,V_2$ 为两平面法向量，则 $F=L\times V_2$ 为第二个圆所在平面上与直线垂直的一个向量。投影为 $O_2 + \frac{F}{|F|} \cdot (\frac{F\cdot (C_2 - O_2)}{|F|})$ 。

然后后面那段其实就是点到直线距离，通过 $\sqrt{R^2 -d^2}$ 可以得到两个交点和投影之间的距离，再数乘 $\frac{L}{|L|}$ 即可得到两个点。

其实最难写的是第一部分，求两个交点。我开始想用三维的叉积解决后面发现有申必情况。于是改用土法炼钢——解二元一次方程组。代码写的很丑。

复杂度 $O(1)$ 。

Submission

E Slayers Come

显然每个技能会干掉一个区间内的人。存下每个位置想要通过连锁反应消灭左右的人需要的最少 $L/R$ 后，这个区间的左右端点都是可以二分（倍增）的。

然后问题就是给定若干区间，求出有多少种选择选择区间的方法使得所有点都被覆盖。

（一个 Edu G 的套路）可以容斥一下，变成钦定一些点，这些点不能被覆盖，求选出若干区间的方法。

用 $dp[i]$ 表示第 $i$ 个位置不能被覆盖，只考虑右端点在 $1 \sim i$ 的区间的值。很显然，对于每个区间，它会使得 $1 \sim l-1$ 区间中的 $dp$ 值对 $r$ 以后的转移的贡献乘 $2$ 。容斥系数是 $-1$ ，即 $dp[i] = -\sum_{j \le i} dp’[j]$ 。

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

Submission

F Bowcraft

自闭题，最后好像乱搞爆标了。

很显然，由于拿到一本书的时候的信息只有当前的等级，所以只要等级固定，决策就是固定的。

我们只要对于每个等级能够判断哪些技能书会被使用即可。

我开始的考虑是对于每个固定的 $0 \le a < A$ ，所有会使用的 $b$ 一定是一个前缀，不妨设这个值是 $t_a$ 。很显然，随着 $a$ 增加，这个值不降。

我先尝试计算 $f_n$ 为从 $n$ 走到 $n+1$ 期望需要买多少次书，即

$$f_n = \frac{AB}{\sum t_i} + \sum_{0 \le i < A} \sum_{0 \le j < t_i} \frac{1}{\sum t_i} \frac{A-i}{A} (f_n + \frac{j}{B} S_{n-1})$$

其中 $S$ 为 $f$ 的前缀和，即按是否成功分类讨论。

推推式子会发现

$$f_n = \frac{A^2 B + \displaystyle \sum_{0 \le i < A} \frac{(A-i)t_i(t_i-1)}{2B}}{\displaystyle \sum_{0 \le i <a} it_i}$$

可以通过 $dp$ 解决问题，设 $dp[i][s]$ 表示考虑了前 $i$ 个 $a$ ，$\sum it_i$ 的和是 $s$ 时的最优分子，复杂度 $O(KA^2B^2)$ 难以通过。

转而考虑什么时候一本书会被使用。可以发现，一本书可以使用当且仅当使用它后到达 $n+1$ 的期望步数小于不使用，即：

$$f_n > \frac{A-a}{A} f_n + \frac{A-a}{A}\frac{b}{B} S_{n-1}\\ f_n > \frac{(A-a)b}{aB} S_{n-1}\\ b < \frac{aBf_n}{(A-a)S_{n-1}}$$

题解做法：通过第二个式子可以发现对于一本书，它的 $\frac{aB}{(A-a)}$ 越小，它就越可能被使用。所以按照这个值排序后，会使用的书一定是一个前缀，对于每个前缀分别计算 $f_n$ 的值即可。可以发现新加入一本书对原来 $f_n$ 的分子和分母的影响都是固定的，所以可以直接 $O(KAB)$ 解决问题。

但是我没有想到这一点！我顺着之前的想法，由第三个式子可以发现，如果确定了当前位置的答案 $f_n$ ，那么每个位置的 $t_i$ 就很容易被算出来。然后我就尝试二分了一下答案，通过二分的答案确定 $t$ 算出一个答案后再和二分的答案比较，发现过掉了样例和测试数据。于是得到了一个 $O(KA\log V)$ 的做法。但是我并不知道为什么这样二分是对的

后来思考了一下，发现这个二分答案的过程等价于二分选择权值前若干大的数。

代码中注意了之前的 $t\in [1,B]$ 而后面 $b \in [0,B-1]$ ，因此是向上取整。

Submission

G Snatch Groceries

太长懒得看，看最后一段和样例猜是按时间扫，输出第一个相交区间前的区间个数。

直接按左端点排序，然后找到第一个左端点小于上一个区间右端点的即可。很容易发现是对的。

Submission

H Keyboard Warrior

考虑通过 Hash 进行匹配。

把原串的开头一段和结尾一段字符拆出来，只考虑中间的字母计算 Hash 。

然后在操作的时候，如果加入的字符是原串开头字符且数量大于等于原串开头字符数量，那么把这个位置前面的字符对应的 Hash 值放入集合内。如果加入的字符是原串结尾字符且数量大于等于原串结尾的数量，那么就在这里查询一下 Hash 值减去原串中间部分的 Hash 乘上一个 base 的次幂。

复杂度 $O(n+m\log k)$ 。其中需要计算 base 的等比数列前缀和。

Submission

I ShuanQ

有 $PQ \equiv 1 \pmod M$ 所以 $M | PQ-1$ 。那么直接分解质因数并判一下 $M$ 是否合法即可。

Submission

J Assassination

感觉难点在题意。题意是删除尽量少的边，使得之前的所有最大生成树都经过至少一条删除的边。

考虑 Kruskal 的过程，每个相同权值的边都是可以在求生成树的时候选择的。而想要所有生成树都经过至少一条删除的边，就可以考虑把某个权值的边中的一部分删除掉，使得原图被分成两个互不联通的子图。因为在原来求最大生成树的时候，一定会在这个选择这个权值的边时把两个子图连接起来，但是删除这些边后就做不到了。

因此把所有边按权值排序，并且把权值大于当前权值的边加入生成树并缩点起来。然后等价于给定一张边数不超过 $100$ 的图，求最小割的大小。

对于一个连通块，考虑拿出度数最小的点，以这个点为源点并以所有其他同连通块的点分别做汇点跑点数次 dinic 求最小的最大流。如果最小度数是 $k$ ，那么显然 dinic 的复杂度不超过 $O(kE)$ （即使 EK 也就这个复杂度），因此总复杂度是 $O(kVE)$ 。但是考虑每个点的度数的和是 $2E-2$ ，因此实际上 $kV \le 2E-2$ ，所以复杂度是 $O(E^2)$ 的。又由于 $\sum E = m$ ，总复杂度是 $O(Em)$ 即 $100m$ 级别，可以通过。

全局最小割有一个 S…-W… 的算法应该也可以做，但是没学过。

Submission

K DOS Card

用线段树维护区间内最小值、最大值、次小值、次大值、$A_l - A_r$ 的最大值、$A_l - A_r + A_{l’}$ 的最大值、$A_l - A_r - A_{r’}$ 的最大值以及答案即可。

合并比较恶心，需要写的比较细心。

Submission

L Luxury cruise ship

对 $365 \times 31$ 之内的数跑个背包。如果 $N$ 比较大，先给答案加上 $N/365$ 再在这个范围内找所有和 $N$ 同余的数更新答案即可。

复杂度 $O(1)$ 。

Submission