正題

題目鏈接:https://www.luogu.com.cn/problem/CF1416E

---

題目大意

給出$n$個正整數的一個序列$a_i$，你要把$a_i$拆成兩個正整數的和$b_{2i},b_{2i+1}$，要求使得$b$的相同連續段最少。

$1\le n\le 5\times 10^5,1\le a_i\le 10^9$

---

解題思路

考慮求最大的相鄰相同數目，先考慮暴力的$dp$，設$f_{i,j}$表示分解完$a_i$且$b_{2i+1}=j$時的方案，那么有轉移方程
$$f_{i,j}=\max \{f_{i?1,k}+[k=a_i?j]\}+[2j=a_i]$$
而且不難發現對于一個$i$來說它的所有$f_{i,j}$在加上$[2j=a_i]$之前差距不會超過$1$，而且我們顯然只有可能從最大值轉移。

對于$2j=a_i$的情況很難處理，我們可以先考慮都是奇數的情況。

首先開始都有$f_{1,j}=0$，可以記為區間$[1,a_1?1]$，然后到第二個對于一個最大的$j$，我們可以轉移到$a_2?j$（如果合法）。同樣的我們可以翻轉之后得到一個新的最大區間$[l,r]$，當某次之后這個區間空了那么因為上面提到的$f_{i,j}$的差距不會超過$1$，所以最大值不變然后區間變回$[1,a_i?1]$。

之后考慮$a_i$有偶數的情況怎么處理，此時會出現的問題就是：如果$\frac{a_i}{2}$加之前是最大值，那么加上之后就變為了唯一的最大值，這個很好處理，而如果之前不是最大值，那么加了之后就變為了最大值。

這個時候有可能會在區間之外出現一些單點的最大值，我們可以用$set$來儲存這些位置，至于翻轉之后所有的位置$x$都會變為$a_i?x$，那么可以儲存一個$x$表示實際上這個位置的值為$x\times f+buf$的情況，這樣我們就可以快速的翻轉然后把不合法的值去掉就好了。

時間復雜度：$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<set> #define ll long long using namespace std; const ll N=5e5+10; ll T,n,ans,l,r,flag,f,buf,a[N]; set<ll> s; void solve(ll lim){flag=1;if(l<=r){if(lim<=l)l=1,r=0;else l=lim-l,r=lim-min(r,lim-1),swap(l,r),flag=0;}f=f*-1;buf=lim-buf;while(!s.empty()){ll w=(*s.begin())*f+buf;if(w<1||w>=lim)s.erase(s.begin());else break;}while(!s.empty()){ll w=(*(--s.end()))*f+buf;if(w<1||w>=lim)s.erase(--s.end());else break;}return; } signed main() {scanf("%lld",&T);while(T--){s.clear();f=ans=1;buf=flag=0;scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);if(a[1]&1)l=1,r=a[1]-1,ans++;else l=r=a[1]/2;for(ll i=2;i<=n;i++){ // if(s.size())printf("%d\n",*s.begin());if(a[i]&1){solve(a[i]);ans++; if(s.empty()&&flag)l=1,r=a[i]-1,ans++;}else{if(s.find((a[i]/2-buf)*f)!=s.end()||a[i]/2>=l&&a[i]/2<=r)s.clear(),l=r=a[i]/2;else solve(a[i]),s.insert((a[i]/2-buf)*f),ans++;}}printf("%lld\n",ans);}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF1416E-Split【dp,set】的全部內容，希望文章能夠幫你解決所遇到的問題。

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