ABC192 题解

[toc]

AC代码

A – Star

B – uNrEaDaBlE sTrInG

C – Kaprekar Number

定义了 Kaprekar Number 的运算，给出首项，求第 $N$ 个 Kaprekar Number 。

$N\leq 10^5$ 。

模拟一下，如果遇到循环节直接退出即可。

D – Base n

给定两个十进制正整数 $X,M$ ，询问 $X$ 在 $K$ 进制下小于等于 $M$ 的合法情况有几种？这里的合法情况指 $X$ 在 $K$ 进制下的不同数值数量。

例如 $X=22,M=10$ ，$X$ 在三进制下 $=8<10$ ；$X$ 在四进制之下 $=10\leq 10$ ；因此一共 $2$ 个合法的 $X$ 。

$X\leq 10^{60},M\leq 10^{18}$ 。

显然进制越高，那么 $X$ 就越大，于是我们可以二分查找合法区间。注意特判 $X$ 为个位数的情况（不论几进制都是他本身，最多只有一种合法情况）。

E – Train

给定一个 $N$ 个点，$M$ 条边的无向图，每一条边 $i$ 上都运作有一班列车，该班次的列车会在 $K_i$ 倍数的时间从某一个端点发车（双向发车），并且运行 $T_i$ 的时间到达另一个端点。询问从点 $X$ 出发到达点 $Y$ 的最少时间？

$N,M\leq 10^5$ 。$T_i,K_i\leq 10^9$ 。

是一个显然的最短路问题，唯一不同之处在于边权的计算：

运行dijkstra算法时，每到达一个点 $u$ 时假设最短时长为 $T_u$ ，那么从该点到达点 $v$ 的最短时长则为 $\lceil \frac{T_u}{K_{u,v}} \rceil \times K_{u,v}+T_{u,v}$ 。

F – Potion

有 $N$ 个魔力瓶，每个瓶子有 $A_i$ 点魔力，你可以从中选择 $K$ 个瓶子并获得这些瓶子的魔力之和，然后你的魔力每秒会增加 $K$ ，询问你的魔力到达 $X$ （必须严格到达 $X$ ，不能超过）需要的最少时间。

$N\leq 100,A_i\leq 10^7,10^9\leq X\leq 10^{18}$ 。

因为魔力每秒增加 $K$ ，这说明我们如果选了 $K$ 个瓶子，那么 X - 这K个瓶子的魔力和 必定是 $K$ 的倍数中最大的那个，这提示我们可以通过枚举 $K$ 进行dp。

枚举我们最终选了 $K(K=[1..N]$ 个瓶子，假设 $dp[i][j][k]$ 表示前 $i$ 个瓶子中选 $j$ 个，然后对 $K$ 取模后与 $k$ 同余的最大值（因为我们最终取了 $K$ 个瓶子，因此只需要考虑关于 $K$ 的剩余系）。

转移很简单：

算上枚举 $K$ 的 $O(N)$ ，复杂度合计为 $O(N^4)$ 。