題目鏈接：點(diǎn)擊查看

題目大意：給出n種數(shù)，每種數(shù)有a[i]個(gè)，每3-5種連續(xù)的數(shù)都可以被消去，現(xiàn)在問(wèn)給出的所有數(shù)字最后能否全部消去

題目分析：正難則反，題目問(wèn)能否將數(shù)字全部消去，我們不妨設(shè)一開(kāi)始的起點(diǎn)每個(gè)數(shù)字都是0個(gè)，然后每次增加區(qū)間[l,r]中的數(shù)，判斷能否到達(dá)目標(biāo)狀態(tài)，這樣問(wèn)題就轉(zhuǎn)換成了一道差分區(qū)間的題目，我們對(duì)于初始的n個(gè)數(shù)的數(shù)量之間進(jìn)行差分，這樣前面的正數(shù)一定要匹配后面的負(fù)數(shù)才行，又因?yàn)?,4,5這三個(gè)數(shù)字可以組合出大于等于3的所有長(zhǎng)度了，所以題目就轉(zhuǎn)換為了n種數(shù)字能否轉(zhuǎn)換成長(zhǎng)度大于等于3的數(shù)字段，則相應(yīng)的，小于3的負(fù)數(shù)是肯定不能消除的，所以記得特判一下，這樣我們O(n)掃一遍差分?jǐn)?shù)組，每次對(duì)于當(dāng)前的遍歷位置i以及之后的(i+3)操作即可，若可以全部消去必須滿足下面兩個(gè)條件：

遍歷的過(guò)程中sum和不為負(fù)數(shù)

遍歷完成后sum和為0

同時(shí)我們需要對(duì)于n個(gè)數(shù)的差分?jǐn)?shù)組特殊處理一下，我們就假設(shè)a[0]=a[n+1]=0，這樣差分?jǐn)?shù)組b[1]=a[1]-0，b[n+1]=0-b[n]，剩下的實(shí)現(xiàn)就好了

代碼：

#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;int a[N],b[N];bool check() {if(b[2]<0||b[3]<0)//特判一下return false;LL sum=0;for(int i=1;i<=n;i++){sum+=b[i];int pos=i+3;if(pos>n+1)break;if(b[pos]<0){sum+=b[pos];b[pos]=0;}if(sum<0)break;}return sum==0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];b[n+1]=-a[n];if(check())printf("Case #%d: Yes\n",++kase);elseprintf("Case #%d: No\n",++kase);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Gym - 101775J Straight Master(差分数组)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。