首页 > 代码库 > [hdu4768]二分

[hdu4768]二分

2024-08-01 23:08:52   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4768

题意：n个传单分别发给编号为ai, ai + ci, ai + 2 * ci, .. , ai + k * ci的学生，其中k 是满足 ai + k * ci <= bi 的最大的k，题目保证收到传单的个数为奇数的学生最多只有一个，求这个学生的编号和收到的传单数。

方法：考虑前i个学生，sum[i]表示前i个学生收到传单的个数的奇偶性，如果sum[i]为奇数，证明那个学生一定在前i个，否则在i之后，据此可以缩小范围，自然得出二分的方法。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 #include <vector> 8 #include <stack> 9 #include <string>10 #include <ctime>11 #include <queue>12 #define mem0(a) memset(a, 0, sizeof(a))13 #define mem(a, b) memset(a, b, sizeof(a))14 #define lson l, m, rt << 115 #define rson m + 1, r, rt << 1 | 116 #define eps 0.000000117 #define lowbit(x) ((x) & -(x))18 #define memc(a, b) memcpy(a, b, sizeof(b))19 #define x_x(a) ((a) * (a))20 #define LL long long21 #define DB double22 #define pi 3.1415926535923 #define MD 1000000724 #define INF (int)1e925 #define max(a, b) ((a) > (b)? (a) : (b))26 using namespace std;27 struct Node {28         int a, b, c;29         void inp() {30                 scanf("%d%d%d", &a, &b, &c);31         }32 } node[22000];33 int n;34 int sum(int p)35 {36         int ans = 0;37         for(int i = 1; i <= n; i++) {38                 if(p < node[i].a) continue;39                 ans ^= (((min(node[i].b, p) - node[i].a) / node[i].c + 1) & 1);40         }41         return ans;42 }43 int countNum(int p)44 {45         int ans = 0;46         for(int i = 1; i <= n; i++) {47                 ans += (p >= node[i].a && p <= node[i].b && (p - node[i].a) % node[i].c == 0);48         }49         return ans;50 }51 int main()52 {53         //freopen("input.txt", "r", stdin);54         while(cin>> n) {55                 for(int i = 1; i <= n; i++) {56                         node[i].inp();57                 }58                 int maxID = ((LL)1 << 31) - 1;59                 if(sum(maxID)) {60                         int l = 0, r = maxID;61                         while(l < r) {62                                 int m = ((LL)l + r) >> 1;63                                 if(sum(m)) r = m;64                                 else l = m + 1;65                         }66                         cout<< l<< " "<< countNum(l)<< endl;67                 }68                 else puts("DC Qiang is unhappy.");69         }70         return 0;71 }
View Code

 

[hdu4768]二分


联系
我们