hdu 4768 Flyer

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分

题意:给出n组信息,每组一行,分别为ai,bi,ci,表示给编号为 ai , ai+ci , ai+2ci , ai+3ci , ai+4*ci …..的人派传单,编号必须 <= bi 。n组都派完后,问有哪个人拿到的传单数量为奇数(数据中保证只会至多只有1个人的传单数为奇数),如果所有人拿到的传单数都偶数,输出那个英文句子,否则的话,输出那个人的编号以及它拿到的传单数

数据量很大,时限很小,不可能去模拟派传单,但是可以O(1)算出每个组传单,派了多少张。由于题目保证了至多1个人的传单数为偶数,所以传单总数是偶数的话,那一定输出 无,如果为奇数,就一定能找到那个人,所以对于一个总区间,统计左半的传单总数和右半传单总数,如果两边都是偶数那就是无,如果其中一半是奇数,那么那个人一定在那半部分里面,就可以继续二分找下去

整个代码还是比较好写的,注意一些细节即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 20010
#define INF 10000000000000000LL
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n;
struct elem{
LL a,b,c;
}x[N];
LL Min,Max;

LL cal(LL key){
LL num = 0;
for(int i = 0 ; i < n ;i++){
if(key < x[i].a || key > x[i].b) continue;
if((key - x[i].a) % x[i].c == 0) num++;
}
return num;
}

LL solve(LL L,LL R){
LL CNT = 0;
for(int i = 0 ; i < n ; i++){
if(x[i].a > R || x[i].b < L) continue;
LL st,ed,cnt;
if(x[i].a >= L) st = x[i].a;
else st = (L - x[i].a + x[i].c - 1) / x[i].c * x[i].c + x[i].a;
ed = min(x[i].b , R);
if(st > ed) continue;
cnt = (1 + (ed-st) / x[i].c);
CNT += cnt;
}
return CNT;
}

int main(){
while(scanf("%d",&n)!=EOF){
Min = INF; Max = -INF;
for(int i = 0 ;i < n; i++){
scanf("%I64d%I64d%I64d",&x[i].a,&x[i].b,&x[i].c);
Min = min(Min,x[i].a);
Max = max(Max,x[i].b);
}

LL low,high,ans;
low = Min,high = Max,ans = -1;
while(low < high){
LL mid = (low + high) >> 1;
LL cnt1 = solve(low,mid);
LL cnt2 = solve(mid+1,high);
if((cnt1 & 1) == 0 && (cnt2 & 1) == 0) break;
if((cnt1 & 1) == 1) high = mid;
else low = mid + 1;
}
if(low != high) puts("DC Qiang is unhappy.");
else{
LL num = cal(low);
printf("%I64d %I64d\n",low,num);
}
}
return 0;
}