$ CH~0805~ $ 防线 (二分值域，前缀和，特殊性质)
$ solution: $
注意博主所给题面的输出和原题有些不同
这道题当时想了很久很久，就是想不到怎么写。果然还是太 $ vegetable $ 了。首先我们可以肯定的是，我们不能暴力枚举，复杂度太高，数据范围太大！所以我们需要从题目中寻找性质！
题目说了要寻找一个数目为奇数的点，本来以为自己在二进制是与否这方面已经很有经验，但是这道题反手打脸。奇偶数是一个以二进制很有关的东西：（奇数+奇数=偶数）类似（ 1 异或 1 = 0 ），（奇数+偶数=奇数）类似（ 1 异或 0 = 1 ），所以这道题我们可以用前缀和来判断。题目给了一条很不起眼的条件：最多只有一个奇数位置！
这个条件让我可以二分值域，搞个前缀和，如果前面有奇数存在那么前缀和一定是奇数，反之为偶数。所以我们二分值域，算前缀和即可找到那个位置！
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
ll ans;
int t,n;
int a[200005];
int b[200005];
int v[200005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline ll ask(ll x){
ll res=0;
for(rg i=1;i<=n;++i){
if(a[i]>x)continue;
if(b[i]<x) res+=1+(ll)(b[i]-a[i])/v[i];
else res+=1+(ll)(x-a[i])/v[i];
}return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
t=qr();
while(t--){ n=qr();
rg l=2147483647,r=0; ans=0;
for(rg i=1;i<=n;++i){
a[i]=qr(),b[i]=qr(),v[i]=qr();
l=min(l,a[i]); r=max(r,b[i]);
ans+=(b[i]-a[i])/v[i]+1;
}
if(ans%2==0){
puts("Poor QIN Teng:(");
continue;
} ll mid;
while(l<=r){
mid=((ll)l+r)>>1;
if(!(ask(mid)%2))l=mid+1;
else r=mid-1;
}
printf("%d %lld\n",l,ask(l)-ask(l-1));
}
return 0;
}
转载于:https://www.cnblogs.com/812-xiao-wen/p/11250602.html
