【WC2008】【BZOJ1271】秦腾与教学评估(二分,前缀和,奇偶性乱搞)

            

problem

  • 一条路上有n个教学评估团,对于每个评估团从s开始每d个站一个人直到e结束
  • 现在要找到一个站的人数是奇数的点,这个点可能没有,且至多只有一个
  • 问这个点在哪以及这个点站了多少人

solution

  • 因为最多只有一个点是奇数,所以很显然会想到奇数+偶数=奇数,所以说明这个点前面的前缀和都是偶数,后面(包括这个位置)的前缀和都是奇数。
  • 那么我们就二分这个奇数的位置,对于mid,如果mid的前缀和为奇数,那么往前找,如果mid的前缀和为偶数,那么往后找。
  • 每次前缀和+二分,复杂度O(nlogn)

最后,记得开long long

codes

#include
#include
#include
#define maxn 200010
using namespace std;
typedef long long LL;
int n, s[maxn], e[maxn], d[maxn];
bool check(int x){
    int sum = 0;
    for(int i = 1; i <= n; i++)//O(1)求每个调查团的前缀和
        if(x >= s[i])sum += (min(e[i],x)-s[i])/d[i]+1;
    return sum&1;
}
int main(){
    int _w;  cin>>_w;
    while(_w--){
        cin>>n;
        for(int i = 1; i <= n; i++)
            scanf("%d%d%d",&s[i],&e[i],&d[i]);
        LL l=0, r=0x7fffffff;
        while(l < r){
            LL mid = l+r>>1;
            if(check(mid))r = mid;
            else l = mid+1;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
            if(l>=s[i] && l<=e[i] && (l-s[i])%d[i]==0)ans++;
        if(ans&1)cout<' '<'\n';
        else cout<<"Poor QIN Teng:(\n";
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像