ABC195 题解

[toc]

AC 代码

A – Health M Death

B – Many Oranges

C – Comma

D – Shipping Center

$N$ 个行李， $M$ 个盒子， $Q$ 个询问。每件行李有两个属性 $W$ 代表行李的重量， $V$ 代表行李的价值；每个盒子有一个最大载重量 $X$ 。

每次询问给出两个正整数 $L,R$ 代表区间 $[L,R]$ 之间的盒子不能使用，每个盒子 $i$ 只能装下重量不超过 $X_i$ 的行李，对于每次询问给出最大能装多少价值的行李。

$N,M,Q\leq 50$ ， $W_i,V_i,X_i\leq 10^6$ 。

由于 $N,M,Q\leq 50$ 所以多组询问就是吓人的，我们只需要想办法解决一组情况。

贪心地考虑，如果一个载重量尽可能小的盒子装了一个当前权值最大的物品，那么它在后续的装载过程中是不会被更优的物品替换的，于是贪心策略就是将所有行李按照权值从大到小排序，然后将每件行李放入尽可能小的盒子中，用一个 multiset 维护即可。

复杂度 $O (Q (N+M)\log M)$ 。

E – Lucky 7 Battle

给定两个长度为 $N$ 的字符串 $S,X$ ，其中 $S$ 由数字组成， $X$ 由 A, T 两种字符构成。

现在 Aoki 和 Takahashi 正在玩一个游戏，他们会遍历字符串 $X$ ，如果 $X_i=A$ 那么 Aoki 行动，反之 Takahashi 行动。第 $i$ 轮行动时，有两种不同的选项：

向字符串 $T$ 的末尾加入字符 0 ；

向字符串 $T$ 的末尾加入字符 $S_i$ ；

字符串 $T$ 初始为空，如果最后得到的 $T$ 代表的十进制数字在除去前导零后是 $7$ 的倍数，那么 Takahashi 获胜，反之 Aoki 获胜。

$N\leq 10^5$ 。

由于这题需要对 $7$ 取模，因此状态只有 $7$ 种，很容易想到用 $dp [i][j]$ 来存状态， $dp [i][j]=1$ 表示到第 $i$ 轮时的 $j$ 是 Takahashi 的必胜态， $=0$ 为必败态（ $j=0,1,2,3,4,5,6$ ）。然后思考两人的胜利 / 失败条件：Aoki 的胜利条件就是当前所有的可行状态中至少有一种可以导致结果不为 0，而必败条件就是一定会走到 0；Takahashi 的必胜条件则是当前一定有一种方法走到 $j=0$ 。

最后思考状态如何转移，不妨逆向思考，初值设为 $dp [n][0]=1$ 。如果在最后一轮（ $i=n-1$ ）时 Aoki 在状态 j，并且 $j\times 10 \pmod {7}=0 \cap (j\times10+(S_i-‘0’))\pmod {7}=0$ ，那么他在当前这个状态就是必败的，反之必胜。于是可以得到转移为：

 if (x[i] == 'A') {
    if (dp[i + 1][(j * 10 + s[i] - '0') % 7] && dp[i + 1][j * 10 % 7]) { // Aoki
        dp[i][j] = true;
    }
} else {
    if (dp[i + 1][(j * 10 + s[i] - '0') % 7] || dp[i + 1][j * 10 % 7]) { // Takahashi
        dp[i][j] = true;
    }
}

因此，最后如果 $dp [0][0]=1$ ，那么 Takahashi 必胜，否则 Aoki 必胜。时间复杂度 $O (7N)$ 。

F – Coprime Present

给定正整数 $A,B$ ，询问在区间 $[A,B]$ 之间能选出几个子集 $S$ 满足：集合中的任意两个元素互质（可以为空）。

$A,B\leq 10^{18},B-A\leq 71$ 。保证答案在 long long 范围内。

由于 $[A,B]$ 的最长区间长度仅为 $72$ ，因此我们可以得到一个关键信息：如果两个该区间中的某两个元素 $x,y$ 不互质，那么 $\gcd (x,y)\leq 72$ 。更进一步地考虑，该区间内的所有不互质数对均可表示为 $dx’,dy’$ ，其中 $d$ 是最大公因数中的最小质因子（因为更大的质因子不需要考虑），筛一下就可以发现 $72$ 以内的质数只有 $20$ 个，这个范围完全可以状压。

将区间 $[A,B]$ 中的数用 $72$ 以内的质数筛一遍，那么每个数都可以表示为 $p_0^{c_0} p_1^{c_1}\cdots p_{19}^{c_{19}}$ 的形态（ $c_i=0,1$ 不需要记录具体次数）。我们选出的子集 $S$ 中，每个质因子只能出现一次，因此我们可以用 $dp [s]$ 存下所有的状态（ $s$ 是一个大小为 $20$ 的 0/1 集合，表示 $p_i$ 是否存在于集合中）， $dp [s]$ 表示状态 $s$ 有几种合法子集。

状态转移时可以枚举一个必定出现的数字 $i$ （ $i$ 代表对应数字的状态集合），然后遍历去掉该数字状态的全部子集 $s$ ：

$\begin{aligned} dp[s+i]=dp[s+i]+dp[s](s\subset U/i) \end{aligned}$
最后，对

$dp$ 数组求和就是答案。时间复杂度不超过

$O (72\times 2^{20})$ 。