$ 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 intusing 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

總結

以上是生活随笔為你收集整理的CH0805 防线 (二分值域，前缀和，特殊性质)的全部內容，希望文章能夠幫你解決所遇到的問題。

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