Solution 8.9
T1 区间询问
签到题：分两种情况讨论
1. L == R 时 四个答案就是 L, L, L, L
2. L != R 时 四个答案就是 1, R, L, R * (R - 1)
T2 包含
我们可以用 dp 进行预处理，dp[i] 代表对于询问的数字为 i 时的答案。(1 代表
包含，0 代表不包含)
首先对于输入的所有数字 a[i] 可得 dp[a[i]] = 1。
然后我们倒着枚举值域，对于任意一个数字 x，如果 dp[x] = 1，那么去除其中
任意一位二进制上的 1，对应的 dp 值仍为 1 用 O(nlogn) 的时间进行预处理，之后就可
以 O(1) 回答每次查询了。详见代码：
【核心代码】
for(int i = maxn; i >= 0; i--) {
for(int j = 0; j < 20; j++)//枚举去掉哪个位置的 1
if(dp[i] && (i >> j & 1))
dp[i-(1<<j)] = 1;
}
T3 删数游戏
我们发现到某一位时，前面擦去那些数字并不影响当前位，影响的只有前面擦去的数量。
对于原来第 i 位的数，如果前面删除了 j 个数，那么他所在的位置就是 i - j
设 dp[i][j]表示到第 i 个数共擦去 j 个数的答案。 我们只需要分两种情况第 i 位上的数是否删
除即可。
转移方程为：
最后答案就是 max(dp[n][j])。
评论0