学步园

题目看了好久……

然后感谢小伙伴给我讲了题意。

求出现了偶数次的那个数以及它出现的次数。

数论知识，偶+偶 = 偶， 偶+奇 = 奇 。所以当那个奇数出现之后，那之后的所有数的前数之和必定为奇数。出现规律大概是  偶偶偶偶偶偶偶奇奇奇奇奇……

这样只要二分查找第一个出现的奇数即可。

因为无法确定会有多少组数据，所以开动态数组。

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

string s;
ll num[4];
struct node
{
    ll x,y,z;
}t;
vector<node> n;
vector<node>::iterator iter;
bool ok(ll m)
{
    ll res = 0;
    for(iter=n.begin();iter!=n.end();++iter)
    {
        node tem = *iter;
        if(m>=tem.x)
        {
            ll mm = min(tem.y,m);
            res+=(mm-tem.x)/tem.z+1;
        }
    }
    return res%2==1;
}
ll sum(ll m)
{
    ll res = 0;
    for(iter=n.begin();iter!=n.end();++iter)
    {
        node tem = *iter;
        if(m>=tem.x&&m<=tem.y)
        {
            if((m-tem.x)%tem.z == 0)
                res++;
        }
    }
    return res;
}
ll solve()
{
    ll l = 0;
    ll r = 1LL<<33;
    ll mid;
    for(mid=(l+r)/2;l<=r;mid=(l+r)/2)
    {
        if(ok(mid))
            r = mid-1;
        else
            l = mid+1;
    }
    return l;
}

int main()
{
    bool y = false;
    int test = 0;
    while(getline(cin,s))
    {
        stringstream ss(s);
        int tt = 0;
        while(ss>>num[tt])
            tt++;
        if(tt!=0)
        {
            t.x = num[0];
            t.y = num[1];
            t.z = num[2];
            n.push_back(t);
            y = true;
            test++;
        }
        else
        {
            test = 0;
            if(y)
            {
                ll a = solve();
                if(a>=1LL<<33)
                    printf("no corruption\n");
                else
                    printf("%I64d %I64d\n",a,sum(a));
                n.clear();
                y = false;
            }

        }
    }
    if(test)
    {
        ll a = solve();
        if(a>=1LL<<33)
            printf("no corruption\n");
        else
            printf("%I64d %I64d\n",a,sum(a));
        y = false;
    }

    return 0;
}