Solved only: A, B

A

x需要2个A
y需要1个A,1个B
z需要3个B

问还缺少多少A,B

B

从1~n中拿k个数xor起来,要求最大值。

当k=1时,答案是n。
当k>1时,答案是n的二进制最高位开始往低位全部填满1。

C

题意复杂。

D

容易想到最优的放法是贪心地从最中间开始放鱼,并向外扩展。
我们计算每个格子可能被几个框覆盖。
计算可能覆盖这个格子的框的左上角的坐标(x, y)的范围
$max(1, x-r+1) \leq x \leq min(x, n-r+1)$
$max(1, y-r+1) \leq x \leq min(y, m-r+1)$
$(ubx-lbx+1) * (uby-lby+1)$ 就是覆盖这个格点的框的左上角坐标的可能性,也是这个点的贡献。
把贡献最大的k个格子累加一下,除以所有的情况,就是最后所求的期望。
所有情况是$(n-r+1)(m-r+1)$。

具体的实现可以用BFS+优先队列去维护贡献最大的那些格点。

E

给一些素数,问由这些素数为因子构成的所有小于1e18的数中第k小的。

最坏情况是最小的16个素数我以为组成的数集会超大。
题解上说这些素数构成的数集合$N$大概只有$8*10^8$,但还是存不下的。
方法是把$N$分成两个集合。
$A \bigcup B = N$ && $A \bigcap B = \emptyset$
也就是把给出的素数分成两部分,然后各自构成所有小于1e18的数,就满足了。
最后对答案行进lower_bound,关键在于 $O(n)$ 的check,需要将A, B集合排序,然后A从大到小枚举,B从小到大扫描。
原因是,枚举到A[i]乘以B[0] ~ B[j]是小于等于x的,那么A[i - 1]乘以B[0] ~ B[j]也必然是小于等于x的,只要扫描一遍B就可以了,复杂度线性。

1
2
3
4
5
6
7
8
9
10
11
bool check(ll x) {
ll cont = 0;
int j = 0;
for (int i = A.size(); ~i; --i) {
while (j < B.size() && B[j] <= x / A[i]) {
++j;
}
cont += j;
}
return cont >= k;
}