4422 - NOIP2020(CSP) 提高:第二题 动物园(zoo)

16051915328906.png

输入

16051915475390.png

输出

输出文件名为 zoo.out。

仅一行一个整数表示答案。

样例

输入

3 3 5 4
1 4 6
0 3
2 4
2 5

输出

13

输入

2 2 4 3
1 2
1 3
2 4

输出

2

提示

【样例 1 解释】

动物园里饲养了编号为 1、4、6 的三种动物,《饲养指南》上 3 条要求为:

1.若饲养的某种动物的编号的第 0 个二进制位为 1,则需购买第 3 种饲料。

2.若饲养的某种动物的编号的第 2 个二进制位为 1,则需购买第 4 种饲料。

3.若饲养的某种动物的编号的第 2 个二进制位为 1,则需购买第 5 种饲料。

饲料购买情况为:

1.编号为 1 的动物的第 0 个二进制位为 1,因此需要购买第 3 种饲料;

2.编号为 4、6 的动物的第 2 个二进制位为 1,因此需要购买第 4、5 种饲料。

由于在当前动物园中加入一种编号为 0,2,3,5,7,8,⋯,15 之一的动物,购物清单都不会改变,因此答案为 13。

 

【数据范围与提示】

对于 20%的数据:k ≤ n ≤ 5,m ≤ 10,c ≤ 10,所有的 pi 互不相同。

对于 40%的数据:n ≤ 15,k ≤ 20,m ≤ 20,c ≤ 20。

对于 60%的数据:n ≤ 30,k ≤ 30,m ≤ 1000。

对于 100%的数据:0 ≤ n, m ≤ 10^6,0 ≤ k ≤ 64,1 ≤ c ≤ 10^8。

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题