正題

題目鏈接:https://atcoder.jp/contests/arc132/tasks/arc132_d

---

題目大意

給出兩個恰好有$n$個$1$和$m$個$0$的字符串$s,t$，定義兩個字符串距離為通過交換兩個相鄰的字符把一個變成另一個的最小步數(shù)。

對于字符串$k$如果$dis(s,k)+dis(k,t)=dis(s,t)$那么$k$在$s,t$之間。

定義一個字符串的權(quán)值為相鄰的相同字符對數(shù)。

求所有在$s,t$之間的字符串中權(quán)值最大是多少。

$1\le n+m\le 3\times 10^5$

---

解題思路

先考慮在$s,t$之間的字符串有什么性質(zhì)，顯然的我們對于求$dis(s,t)$的時候最優(yōu)的策略肯定是把$s$的第$i$個$1$移動到$t$的第$i$個$1$處。

也就是對于兩個串中第$i$個$1$的位置記為$x,y$，那么就是一個一要從$x\to y$，也就是在$s～t$之間的字符串第$i$個一肯定在$x～y$這個范圍。

這樣我們處理出每個$1$的合法區(qū)間$l_i,r_i$，顯然的$l_i$和$r_i$必定遞增，因為交換兩個$1$的順序必定不劃算。所以可以考慮貪心。

不考慮邊界的問題，那么我們顯然要讓$1$的連續(xù)段盡量少，那么從小到大考慮$l,r$如果能和上一個放一起就放一起，不然就放在$r$的位置最賺。

然后考慮邊界，右邊界可以直接判斷因為我們肯定是盡量往右放的。左邊界的話我們?nèi)绻?span id="ze8trgl8bvbq" class="katex--inline">$l_1=1$我們就分兩種情況考慮，也就是第一個放在左邊界和第一個放在$r_1$兩種情況取個最大值。

時間復(fù)雜度：$O(n+m)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) using namespace std; const int N=6e5+10; int A,B,m,n,t[N],l[N],r[N],ans,prt; char a[N],b[N]; //void Change(int x,int val){ // while(x<=m){ // t[x]+=val; // x+=lowbit(x); // } // return; //} //int Ask(int x){ // int ans=0; // while(x){ // ans+=t[x]; // x-=lowbit(x); // } // return ans; //} int main() {scanf("%d%d",&A,&B);m=A+B;scanf("%s",a+1);scanf("%s",b+1);for(int i=1;i<=m;i++)if(a[i]=='1')l[++n]=i;n=0;for(int i=1;i<=m;i++)if(b[i]=='1')r[++n]=i;for(int i=1;i<=n;i++){if(l[i]>r[i])swap(l[i],r[i]);}int last=-1;for(int i=1;i<=n;i++){if(l[i]<=last+1)last++;else ans++,last=r[i];}ans=ans*2;if(last!=m)ans++;prt=m-ans;if(l[1]==1){last=1;ans=1;for(int i=2;i<=n;i++){if(l[i]<=last+1)last++;else ans+=2,last=r[i];}if(last!=m)ans++;ans=m-ans;prt=max(prt,ans);}printf("%d\n",prt);return 0; }

總結(jié)

以上是生活随笔為你收集整理的ARC132D-Between Two Binary Strings【贪心】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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