Atcoder Dwango Programming Contest V

时间:2022-06-27 15:11:07

模拟,做了ABC三题。

D难一些,就不会了。

中规中矩的吧。。。

Atcoder DPCV B

题意:给一个序列,求出所有的子串和中AND值最大的k个数的AND。

思路:既然要求AND,那么肯定按位考虑。

从最高位往低位枚举,看所有的包含这一位的数,如果这些数的个数小于K,那么不能取。

否则把原来的数集合改成现在的数集合。

Atcoder DPCV C

题意:给一个字符串,求长度小于等于\(K_i\)的DMC子序列的个数。

思路:首先把询问离线。

然后从左往右枚举D的位置。

那么对于第\(i\)个询问,当前位置对其的贡献就是后面的与其距离不超过\(K_i\)的所有的C乘上它们中间的D的数量。

这个通过前缀积搞一下就好了。