ch0805 防线

我会带着你远行 2022-10-01 15:54 127阅读 0赞

题目链接：  
[http://contest-hunter.org:83/contest/0x08「基本算法」练习/0805 防线（秦腾与教学评估）][http_contest-hunter.org_83_contest_0x08_0805]

本题，数据范围很大。应该想到用二分。 可是二分怎么确定mid的左边还是右边呢。  
我们继续看题目。题目保证了至多只有一个奇数点。想一下，最多只有一个。那么本题是唯一答案。同时其他地方的点都是偶数点。所以我们可以用到前缀和。如果mid的前缀和是偶数，那么奇数点一定在mid的后面。反之，在前面。可是我们无法开一个（1 << 32 - 1）的数组来保存前缀和。所以我们需要通过一个简单的变换来求出前缀和。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    struct Node
    {
        int s,e,d;
    }node[200010];
    
    int T,N;
    
    ll Judge(ll x)
    {
        ll sum = 0;
        //通过遍历所有的组的防具。求出前缀和。
        for(int i = 1; i <= N;i ++)
        {
            if(node[i].s <= x)
            {
                sum += (min(x,(ll)node[i].e) - node[i].s) / node[i].d + 1;
            }
        }
        return sum;
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d",&N);
            for(int i = 1; i <= N; i ++)
                scanf("%d%d%d",&node[i].s,&node[i].e,&node[i].d);
            ll l = 0,r = (long long)1 << 32 - 1;
            while(l < r)
            {
                ll mid = (ll)((l + (long long)r) >> 1);
                if(Judge(mid) & 1)
                    r = mid;
                else
                    l = mid + 1;
            }
            ll ans = Judge(r) - Judge(r - 1);
            if(ans == 0)
                printf("There's no weakness.\n");
            else
                printf("%lld %lld\n",l,ans);
        }
    }

[http_contest-hunter.org_83_contest_0x08_0805]: http://contest-hunter.org:83/contest/0x08%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E7%BB%83%E4%B9%A0/0805%20%E9%98%B2%E7%BA%BF%EF%BC%88%E7%A7%A6%E8%85%BE%E4%B8%8E%E6%95%99%E5%AD%A6%E8%AF%84%E4%BC%B0%EF%BC%89