题目链接

Showstopper POJ - 3484

思路

$$ 本题输入不太常规，但是区域赛出过这样的输入，比如某年北京？\\\\考虑前缀和，因为只有一个数出现奇数次，所以前缀和是偶偶…偶偶奇奇…奇奇\\\\二分就可以了 $$

时间复杂度

$$ O(Nlog(M)) $$

代码

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;



vector<long long> x, y, z;

void init() {
    x.resize(0);
    y.resize(0);
    z.resize(0);
}

char str[1000];
long long ans1, ans2;

bool check(long long mid) {
    long long sum = 0;
    long long cnt = 0;
    for (int i = 0; i < (int)x.size(); i++) {
        long long xx = x[i];
        long long yy = y[i];
        long long zz = z[i];
        if (xx <= mid) {
            sum += (min(mid, yy) - xx) / zz  + 1;
            if (mid <= yy && (mid - xx) % zz == 0) {
                cnt++;
            }
        }
    }
    if (sum & 1) {
        ans1 = mid;
        ans2 = cnt;
        return true;
    } else {
        return false;
    }
}

void solve() {
    long long l = 0, r = 1LL << 33;
    ans1 = -1;
    while (l <= r) {
        long long mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    if (ans1 == -1) {
        puts("no corruption");
        return;
    }
    printf("%lld %lld\n", ans1, ans2);
}

int main() {
    while (~scanf("%[^\n]", str)) {
        getchar();
        if (strlen(str) != 0) {
            long long xx, yy, zz;
            sscanf(str, "%lld%lld%lld", &xx, &yy, &zz);// don't forget &
            x.push_back(xx);
            y.push_back(yy);
            z.push_back(zz);
        }

        if (strlen(str) == 0 && (int)x.size() != 0) {
            solve();
            init();
        }
        memset(str, 0, sizeof str);
    }

    if ((int)x.size() != 0) {
        solve();
    }
    return 0;
}