学步园

题目请戳这里

题目大意：给n个三元组(ai,bi,ci)，那么对于y = ci*x + ai(ai <= y <= bi,x >= 0)，求所有三元组产生的y中，出现次数为奇数的数以及出现次数。数据保证最多存在一个数出现奇数次。如果没有数出现奇数次，输出一句话。

题目分析：从出现奇数次作为突破口。首先对于某个三元组(ai,bi,ci)，yi = ci * x + ai，yi <= bi，那么可以确定这个三元组产生了(bi - ai)/ci + 1个数，那么统计所有三元组产生的数的总和，如果为偶数，那么一定不存在出现奇数次的数，直接输出那句话。如果是奇数，那么我们只需要找到这个数即可。

这个数可能很大，给每个整数开个计算器显然不可能。对所有三元组出现的数一一枚举也不可取，考虑到出现奇数次的只有一个数，那么我们可以在1~2^32范围内二分，寻找奇数区间，不断缩小范围，最后缩成一个点，那就是ans。

trick:1：二分的时候用__int64，会爆int；

2：ci可以为0！！当ci=0的时候，ai = bi；

详情请见代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
const int N = 20005;
const int M = 10000005;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const double PI = acos(-1.0);
typedef __int64 ll;
struct node
{
    ll a,b,c,num;
}p[N];
ll n,maxx;

ll fuck(ll x)
{
    int ret = 0;
    for(ll i = 1;i <= n;i ++)
    {
        if(p[i].c == 0)
        {
            if(x >= p[i].a)
                ret ++;
            continue;
        }
        if(x <= p[i].b && x >= p[i].a)
        {
            ret += ((x - p[i].a)/p[i].c + 1);
        }
		else if(x > p[i].b)
				ret += p[i].num;
    }
    return ret;
}

void gao()
{
    ll l,r,mid;
    l = 1;r = maxx;
    ll tmp,tp;
    ll ans;
    ll tl = 0;
    while(l <= r)
    {
        mid = (l + r)>>1;
        tmp = fuck(mid);
        if((tmp - tl) & 1)
            r = mid - 1,ans = mid;
        else
            l = mid + 1,tl = tmp;
    }
   printf("%d %d\n",ans,fuck(ans) - tl);
}

int main()
{
    ll i;
    while(scanf("%d",&n) != EOF)
    {
        ll sum = 0;
        maxx = 0;
        for(i = 1;i <= n;i ++)
        {
            scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
            if(p[i].c == 0)
                p[i].num = 1;
            else
            {
                p[i].num = (p[i].b - p[i].a)/p[i].c;
                p[i].num ++;
            }
            sum += p[i].num;
            if(maxx < p[i].b)
                maxx = p[i].b;
        }
        if((sum&1) == 0)
        {
            puts("DC Qiang is unhappy.");
            continue;
        }
        gao();
    }
    return 0;
}