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})$ 。