題目鏈接：點擊查看

題目大意：假設現在有一個數軸，一共有n組防具，每組防具給出的形式為S，D，E，在數軸上的分布為：S，S+D，S+2D....S+KD，保證S+KD<=E

現在規定數軸上某個點有偶數個防具是穩定的，有奇數個防具是不穩定的，0因為也是偶數，所以0也是穩定的，題目保證數軸上最多有一個不穩定的點，現在問這個不穩定點的位置，以及有多少個防具

題目分析：因為這個題目保證了最多只有一個不穩定的點，換句話說在經過上述計算后，最多只有一個點的權值為奇數，這樣我們在維護前綴和之后就可以直接二分了，如果當前點的前綴和為奇數，則答案一定在右區間，否則在左區間，現在問題就是怎么維護前綴和，題目中的數值給的都很大，大到了數組無法維護的程度，所以我們必須實時計算前綴和，每次計算時間復雜度為O(n)，配合上二分時間復雜度為nlogn，就可以解決這個問題了

根據上述防具的分布，就可以計算一段區間內有多少個防具，對于每個防具就可以O(1)算出貢獻了，為了防止爆int，都開longlong就好了

這里要%一下zx學長，又從他那里學會了一種小技巧，關于輸入結構體內變量的小技巧，可以在結構體內開一個input函數，又能偷懶了。。

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int n;struct Node {LL s,e,d;void input()//%zx{scanf("%lld%lld%lld",&s,&e,&d);} }a[N];LL check(LL mid) {LL sum=0;for(int i=1;i<=n;i++)if(a[i].s<=mid)sum+=(min(mid,a[i].e)-a[i].s)/a[i].d+1;//計算方法是區間長度減一后看看有多少個長度為d的區間，令每個區間左端點為防具，此時的加一為第一個防具return sum; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d",&n);for(int i=1;i<=n;i++)a[i].input();LL l=1,r=INT_MAX;LL pos=-1;while(l<=r){LL mid=l+r>>1;if(check(mid)&1){pos=mid;r=mid-1;}elsel=mid+1;}if(pos==-1)printf("There's no weakness.\n");else{LL ans=check(pos)-check(pos-1);printf("%lld %lld\n",pos,ans);}}return 0; }

?

總結

以上是生活随笔為你收集整理的CH - 0805 防线(二分+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

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