Flyer （HDU - 4768，二分答案 + 思维）

一.题目链接：

HDU-4768

二.题目大意：

有 n 个社团拉人.

从编号为 a 的学生开始，到编号为 b 的学生结束，每隔 c 个人拉一个.

保证学生被拉选奇数次的个数至多为一.

若不存在被拉选奇数次的学生，则输出 "DC Qiang is unhappy."

否则，输出被拉选奇数次的学生的编号 与 其被拉选的次数.

三.分析：

因为保证学生被拉选奇数次的个数至多为一

所以只需要二分学生标号，check(mid) 函数中检查从编号在 [1, mid] 的学生中，被拉选次数的和.

如果和为奇数，则说明目标在[l, mid] 之间.

否则，在[mid + 1, r] 之间.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)2e4;
const ll inf = 0x3f3f3f3f3f;

int n;
struct node
{
    ll a, b, c;
} s[M + 5];

bool check(ll mid)
{
    ll cnt = 0;
    for(int i = 0; i < n; ++i)
        cnt += max(0ll, (min(mid, s[i].b) + s[i].c - s[i].a) / s[i].c);
    return cnt & 1;
}

/**
2
1 10 1
1 9 1

10 1
**/

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; ++i)
            scanf("%lld %lld %lld", &s[i].a, &s[i].b, &s[i].c);
        ll l = 1;
        ll r = inf;
        while(l < r)
        {
            ll mid = (l + r) >> 1;
            if(check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        if(!check(r))
            printf("DC Qiang is unhappy.\n");
        else
        {
            ll cnt = 0;
            for(int i = 0; i < n; ++i)
            {
                if(r >= s[i].a && r <= s[i].b && (r - s[i].a) / s[i].c * s[i].c + s[i].a == r)
                    cnt++;
            }
            printf("%lld %lld\n", r, cnt);
        }
    }
    return 0;
}