[BJWC2008]秦腾与教学评估

洛咕

题意:在一条线段上有许多点.这些点可以用3n个整数来表示，每行的三个整数分别为\(S_i,E_i,D_i\)，表示有许多个点在\(S, S + D, S + 2D, …, S + KD (K \in Z, S + KD ≤ E, S + (K + 1)D > E)\)位置。求在这一条线段上是否有一个点上的点的个数为奇数，保证解最多只有一个，若无解则输出“Poor QIN Teng:(”（不包含引号），否则就输出那个唯一的点个个数以及有多少个点在它的上面.

二分答案.因为题目保证了最多只有一个点为奇数,其它点都为偶数,所以我们先特判从起点1到最远的点\(dist\)之间的所有点的个数,如果是偶数,直接判断不存在.否则我们二分答案,对于每一个\(mid\),如果1到mid之间有奇数个点,那么必然是在l到mid之间了.

找到位置后,直接枚举上面有多少个点就好了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=200005;
ll s[N],e[N],d[N];
inline ll calc(int n,ll x){
    ll sum=0;
    for(int i=1;i<=n;++i)
        if(s[i]<=x)sum+=(min(e[i],x)-s[i])/d[i]+1;
    return sum;
}
int main(){
    int T=read();
    while(T--){
        ll n=read(),dist=0;
        for(int i=1;i<=n;++i){
            s[i]=read();e[i]=read();d[i]=read();
            dist=max(dist,e[i]);
        }
        if(calc(n,dist)%2==0){//特判
            puts("Poor QIN Teng:( ");
            continue;
        }
        ll l=1,r=dist;
        while(l<r){
            ll mid=(l+r)>>1;
            if(calc(n,mid)%2==1)r=mid;      
            else l=mid+1;
        }
        ll ans=0;
        for(int i=1;i<=n;++i){
            if(s[i]>l||e[i]<l)continue;
            if((l-s[i])%d[i]==0)++ans;
        }
        printf("%lld %lld\n",l,ans);
    }
    return 0;
}

[BJWC2008]秦腾与教学评估

原文：https://www.cnblogs.com/PPXppx/p/11537729.html