PowerOJ 尔尔序的神奇计数问题 暴力or容斥


尔尔序的神奇计数问题

Time Limit: 8000 MS Memory Limit: 2097152 KB

Description

    现在有$4$个集合,分别为$A,B,C,D$,且每一个集合的大小都是$n$。尔尔序想求解一个问题,现在他把$A,B,C$的交集的大小、$A,B,D$的交集的大小,$A,C,D$的交集的大小,$B,C,D$的交集的大小之和记为$X$,同时把$A,B$的交集的大小、$A,C$的交集的大小、$A,D$的交集的大小、$B,C$的交集的大小、$B,D$的交集的大小之和记为$Y$,求解$|X-Y|$的值。

Input

第一行输入一个整数$n$ ($1 \leq n \leq 5 \times 10^4$)代表这$4$个集合的大小。 第二行输入$n$整数$A_i$ ($1 \leq A_i \leq 10^{18}$),代表集合$A$中的数。 第三行输入$n$整数$B_i$ ($1 \leq B_i \leq 10^{18}$),代表集合$B$中的数。 第四行输入$n$整数$C_i$ ($1 \leq C_i \leq 10^{18}$),代表集合$C$中的数。 第五行输入$n$整数$D_i$ ($1 \leq D_i \leq 10^{18}$),代表集合$D$中的数。 保证在同一集合内没有重复的数。

Output

输出$|X-Y|$的值。

Sample Input

Sample Output

题解

数据量比较小,对每个集合排序后,用set_intersection求交集即可。使用容斥原理可以发现,最后的答案其实是|size(A+B+C+D) + size(CD) + size(ABCD) – 4*n|

C++代码

Java代码

 

 

 

 

PowerOJ 2611 尔尔序才是最强的 贪心+优先队列


尔尔序才是最强的

Time Limit: 1000 MS Memory Limit: 2097152 KB

Description

    和往常一样,尔尔序和他的小伙伴兮兮芜开始了每天的王者荣耀之旅。在某局游戏中,尔尔序有了一个新奇的想法。现在尔尔序想独自以最快的速度击杀游戏里的主宰,向兮兮芜证明他才是最强的。
    现在主宰有$x$滴血,每秒钟会恢复$y$滴血,如果主宰回了血之后超过了初始的血量$x$,那么主宰的血量仍然为初始血量$x$。
    尔尔序有$n$个技能(不要执着于王者只有3个技能QAQ)。对于编号为$i$的技能,如果主宰当前有超过(严格大于)$p_i\%$的初始血量时,则该技能无法使用。使用后,该技能会给主宰挂上一个每秒掉$d_i$滴血的BUFF。
    尔尔序想知道他能否一个人击杀主宰,获得兮兮芜的崇拜?
    请注意,每个技能尔尔序最多只能使用一次。且每秒钟尔尔序最多只能使用一个技能。主宰每秒钟会先受到以前挂上的BUFF的伤害,再恢复$y$滴血。如果回血之后,主宰的血量仍然小于等于0,主宰即被尔尔序击杀。该秒挂上的BUFF在这秒不会对主宰造成伤害。

Input

第1行输入三个整数 $n, x, y$,分别代表尔尔序的技能数,主宰的初始血量,主宰每秒恢复的血量。 第2行到第$n+1$行输入两个整数,为编号为$i$的技能的$p_i$和$d_i$值,意义和描述中相同。 $ 1 \leq n,x,y \leq 1000$ $ 0 \leq p_i,d_i \leq 1000$

Output

如果尔尔序不能一个人击杀主宰,获得兮兮芜的崇拜,输出一行“What a pity eex!”(没有引号)。 否则先输出一行“Luckly dog eex!”(没有引号)。接下来一行先输出一个整数,为主宰被击杀的最早时刻,然后再输出一个整数,为需要使用技能的数量$num$。接下来$num$行输出两个整数,为每个技能使用的时刻和编号。从0时刻开始计算时间。

Sample Input

Sample Output

题解

由于主宰的血量越少,尔尔序可选用的技能就越多。所以直接选择当前能释放的能造成最大伤害的技能即可。维护两个优先队列,分别为不可用技能(释放限制血量大的优先出队)和可用技能(释放造成伤害大的优先出队)。每秒将已经可用的技能从不可用队列中取出,放到可用技能的队列中。如果此时可用技能不为空,则释放一个造成伤害最大的技能。如果当前没有可释放的技能,并且BUFF伤害小于等回血量y。则不可杀死主宰。

C++代码

Java代码