7.23 状态极差的杭电2
1001-Total Eclipse
题意
给定一个 $n$ 个点的图,每个点有一权值 $b$ ,每次选择 $k$ 个相互连通的点,使其中每个点权值减一,问最少需要多少操作可以使所有的点权值都为 $0$(每次选择的 $k$ 必须最大)
思路
先将节点按权值从大到小排序,然后依次遍历点 $id_i$ ,将之前遍历过且与 $id_i$ 不在同一联通块内的点 $v$ 与 $id_i$ 合并,并将父亲设为 $id_i$ ,每个点对答案的贡献为 $b_i-b_{father_i}$
代码
1 |
|
1006-The Oculus
题意
每个数都有唯一的斐波那契表示,即 $A=\sum_{i=1}^nb[i] * F_i$ ,$b[i]$ 为 $0$ 或 $1$ 且相邻为不同为 $1$ 。给定 $A$ 、$B$ 、$C$ 的斐波那契表示,$C=A * B$ ,但是 $C$ 的斐波那契表示中有一个 $1$ 被替换为了 $0$ ,求此位数
思路
考虑直接嗯搞。根据哈希思想,利用一个大质数/双模数就降低被卡的可能,改成大质数就过了(没过我就写双模去了)
坑点
$C$ 是 $2e6$ 的,别开小了
补充
自然溢出就能过的,只是我们最开始的单模不能过罢了
1010-Lead of Wisdom
题意
有 $n$ 个装备 $k$ 个类型,每个装备有 $a$ 、$b$ 、$c$ 、$d$ 四种属性,要求每种类型选一个且使得 $Sum=(100+\sum a) * (100+\sum b) * (100+\sum c) * (100+\sum d)$
思路
嗯搜 我自己也不知道为啥正着搜就t啊
代码
1 |
|
1012-String Distance
题意
给定 $1e5$ 的串 $S$ 和 $20$ 的 $T$ ,$1e5$ 的询问,每次给定 $l$ 和 $r$ ,求 $S_l$ 到 $S_r$ 和 $T$ 的 $lcs$ 长度
思路
$lcs$ 标配 $dp$ ?预处理出对于每个 $i$ 位第 $j$ 个字符最先出现的位置(记为 $pos[j][i]$),利用 $pos$ 进行转移
代码
1 |
|