正題

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

---

題目大意

兩個(gè)長(zhǎng)度為$k$的起始和目標(biāo)01串。
$n$個(gè)操作交換起始串的兩個(gè)位置，選擇一段長(zhǎng)度至少為$m$的連續(xù)操作序列使得相同的位數(shù)最多。
$1\le m\le n\le 10^6,1\le k\le 20$

---

解題思路

因?yàn)槭菑那巴蟛僮?#xff0c;所以可以拆成兩個(gè)后綴$[l,n]$和$[r+1,n]$。

對(duì)$S$執(zhí)行$l～n$然后對(duì)$T$執(zhí)行$r+1～n$之后比較就好了。

額考慮怎么做這個(gè)東西，我們可以$O(nk)$的處理出一個(gè)$s_i$表示對(duì)$S$執(zhí)行了$i～n$之后的序列，$t_i$表示對(duì)$T$執(zhí)行了$i～n$之后的序列，當(dāng)然要用二進(jìn)制壓起來(lái)。

然后我們要找到一對(duì)$l,r$使得$r?l\ge m$且$s_{l}xor{t}_r$的$1$最多。

有個(gè)做法是考慮$sandt$的$1$數(shù)，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$s$和$t$的$1$數(shù)固定。設(shè)$sandt$有$z$個(gè)$1$，$s$有$x$個(gè)$1$，$t$有$y$個(gè)$1$，那么他們相同的位數(shù)有$z+(k?x?y+z)=2z+k?x?y$個(gè)，所以其實(shí)是要最大化$z$就好了。

設(shè)$f_i$表示一個(gè)最小的$k$使得$s_{k}andi=i$，$g_i$則是表示對(duì)于$t$來(lái)說(shuō)最大的$k$。

然后求出這兩個(gè)就可以搞定這題了，因?yàn)槭亲钪邓圆恍枰玫?span id="ze8trgl8bvbq" class="katex--inline">$\text{FWT}$，直接$dp$就好了。

時(shí)間復(fù)雜度$O(nk)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1<<20; int k,n,m,s,t,zx[N],zy[N],f[N],g[N],bit[N],rev[N][20]; char st[30]; int swp(int s,int p){int ans=0;for(int i=0;i<k;i++)ans|=(((s>>rev[p][i])&1)<<i);return ans; } int main() {scanf("%d%d%d",&n,&m,&k);scanf("%s",st);for(int i=0;i<k;i++)s|=(st[i]-'0')*(1<<i);scanf("%s",st);for(int i=0;i<k;i++)t|=(st[i]-'0')*(1<<i);for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);x--;y--;for(int j=0;j<k;j++)rev[i][j]=j;swap(rev[i][x],rev[i][y]);}for(int i=n-1;i>=1;i--){int tmp[k];for(int j=0;j<k;j++)tmp[j]=rev[i][rev[i+1][j]];for(int j=0;j<k;j++)rev[i][j]=tmp[j];}memset(f,0x3f,sizeof(f));for(int i=n;i>=1;i--){int x=swp(s,i);f[x]=min(f[x],i);x=swp(t,i);g[x]=max(g[x],i);}g[t]=n+1;int MS=(1<<k);for(int i=1;i<MS;i++)bit[i]=bit[i-(i&-i)]+1;int ans=-1,ansl=0,ansr=0;for(int i=MS-1;i>=0;i--){for(int j=0;j<k;j++){f[i]=min(f[i],f[i|(1<<j)]);g[i]=max(g[i],g[i|(1<<j)]);}if(bit[i]>ans&&g[i]-f[i]>=m)ans=bit[i],ansl=f[i],ansr=g[i];}printf("%d\n%d %d\n",2*ans+k-bit[s]-bit[t],ansl,ansr-1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1392G-Omkar and Pies【dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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