洛谷傳送門

解析

因為至多有一個單數
假設其位置為k，1-i的累加和為s[i]
則s[1]-s[k-1]全是偶數
s[k]-s[max]全是奇數
答案呈單調性，可以用二分算法
check函數（計算前綴和）也很容易用O（n）寫出：

long long check(int x){long long tot=0;for(int i=1;i<=n;i++){if(p[i].b<=x){tot += (p[i].b-p[i].a)/p[i].m+1;}else if(p[i].a>x) continue;else{tot += (x-p[i].a)/p[i].m+1;}}return tot; }

（時間復雜度應該可以更優，但這樣夠了，大腦就不想動了。。。）
兩個地方要加1，因為排頭有一個，之后的個數這是長度除間隔的地板除法
然后二分枚舉位置判斷奇偶即可

PS：不開longlong見祖宗

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<string> #include<queue> #include<vector> using namespace std; const int M=1e9; long long n,t; long long mx=0; struct node{long long a,b,m; }p[200500]; long long check(int x){long long tot=0;for(int i=1;i<=n;i++){if(p[i].b<=x){tot += (p[i].b-p[i].a)/p[i].m+1;}else if(p[i].a>x) continue;else{tot += (x-p[i].a)/p[i].m+1;}}return tot; } int main(){scanf("%lld",&t);for(int k=1;k<=t;k++){mx=0;scanf("%lld",&n); for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].m);mx=max(mx,p[i].b);}long long st=0,ed=mx+1;while(st<ed){long long mid=(st+ed) >> 1;if(check(mid)%2==1) ed=mid;else st=mid+1;}if(st==mx+1){//返回mx+1，說明全是偶數，無懈可擊printf("Poor QIN Teng:( \n");continue;}printf("%lld %lld\n",st,check(st)-check(st-1));}return 0; }

AC快樂！！！

總結

以上是生活随笔為你收集整理的二分：[BJWC2008]秦腾与教学评估的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。