P4403 秦腾与教学评估
这题第一眼看的时候（还没看数据范围），其实就知道不可能写暴力了（尽管我抱着侥幸心理扣扣瞄了一眼数据范围，看完彻底死心了qwq）。
那么怎么写呢？
ans：前缀和+二分
这道题有一个关键，注意到了很容易就能写出来。没有注意到可能就写不出来了……
这个神奇的地方就隐藏在那一大堆话里：
为了美观我截了全句，但其实重要的是后半句：最多仅有一个。
既然这样，我们可以用前缀和来确认答案在左区间还是右区间，只要判断前缀和奇偶性就可以啦~
现在再看，是多容易啊~
——————————————————————
那为什么我滴了一个小时！！！
有几个要注意的：
1.对于最后的ans，利用的是l，而不是mid或者r！（原因很简单，l是逐步逼近答案并且最终确定答案那个变量）
2.前缀和不是一开始就全部求出（会tle），而是现用现求。（我觉得这题还是放水了，因为每一次都从1到n来求还是太慢了，但是能过）
3.要开long long。——>一开始没开，tle；偷偷开了O2优化，还是tle；忍无可忍，开了long long，竟然过了……" > "
虽然我还是不知道ing改成long long和超时有什么关系(虽然一定有什么关系)，但是还是提醒自己，long long有的时候是必要的啊。
那就直接上代码喽：
#include<cstdio> #include<iostream> using namespace std; #define int long long struct data { int s,e,la; } q[200005]; int t,n,maxn,ans; int check(int x) { int sum=0; for(int i=1;i<=n;i++) { if(q[i].s<=x) sum+=(min(q[i].e,x)-q[i].s)/q[i].la+1; } return sum; } main() { int l,r,mid,u; scanf("%lld",&t); while(t--) { maxn=0; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",&q[i].s,&q[i].e,&q[i].la); maxn=max(maxn,q[i].e); } int all=check(maxn); if(all%2==0) { printf("Poor QIN Teng:( "); continue; } l=1,r=maxn,mid=0; while(l<r) { mid=(l+r)/2; u=check(mid); if(u%2) r=mid; else l=mid+1; } ans=check(l)-check(l-1); printf("%lld %lld ",l,ans); } return 0; }
这就AC啦~~~