正題

題目鏈接:https://loj.ac/p/6564

---

題目大意

給兩個序列$a,b$求它們的最長公共子序列。

$1\le n,m,a_i,b_i\le 7\times 10^4$

---

解題思路

無意間看到的一個$bitset$科技。

首先設$f_{i,j}$表示$a$串匹配到第$i$個$b$串匹配到第$j$個時的最長長度，做過$dp$套$dp$的應該知道$f_{i,j}$的性質。
$$0\le f_{i,j}?f_{i,j?1}\le 1$$

基本的思路就是設$01$矩陣$M$滿足$f_{i,j}={\sum }_{k=1}^j{M}_{i,k}$然后用$bitset$優化轉移

然后考慮一下怎么轉移，我們先預處理出$p$數組其中$p_i$表示數字$i$出現的位置集合

我們的轉移要把$M$中的$1$盡量的往前移動并且看能否加上一個新的$1$。

假設現在的字符是$c$，那么我們將使用$p_c$進行轉移。

我們把$M$中每個$1$作為結尾分成若干段（最后的$0$也是一段，順序是從低位到高位）。

那么對于一段中如果這一段$p_c$有$1$那么我們就取最前面的那個$1$，這樣因為前面假設有$j$個$1$那么這次就匹配$p_c$最前面的那個作為$j+1$。

但是我們顯然不可能一段一段做，我們可以考慮怎么把這個操作轉成位運算🤔。

考慮一下我們平時是怎么取一個$01$串的第一位的，我們有$lowbit(x)=((x?1)xorx)andx$對吧。

發現這里每段分開取實際上難實現的地方只有$x?1$，考慮怎么實現這個問題。

因為$1$是段的末尾，所以每一段的開頭前面都是$1$，所以如果我們讓$M$左移一位那么就變成開頭是$1$了（需要注意補上第一段的$1$，所以應該是$(M<<1)+1$）

最后來說是
$$M=(X?(M<<1)+1)xorXandX$$

這樣我們就完成了$M$的轉移，因為需要位運算，所以需要手寫$bitset$。

時間復雜度$O(\frac{nm}{\omega })$

我是看這篇博客學的，看不懂的可以去看下:https://www.cnblogs.com/-Wallace-/p/bit-lcs.html

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ull unsigned long long using namespace std; const int N=7e4+10; int n,m,L; struct bitset{ull t[N/64+5];bitset(){memset(t,0,sizeof(t));return;}void set(int p){t[p>>6]|=(1ull<<(p&63));return;}void shift(){ull last=0;for(int i=0;i<L;i++){ull cur=t[i]>>63;(t[i]<<=1)|=last;last=cur;}return;}int count(){int ans=0;for(int i=0;i<L;i++){ull x=t[i];while(x)x-=(x&-x),ans++;}return ans;}bitset& operator=(const bitset &b){memcpy(t,b.t,sizeof(t));return *this;}bitset& operator|=(const bitset &b){for(int i=0;i<L;i++)t[i]|=b.t[i];return *this;}bitset& operator&=(const bitset &b){for(int i=0;i<L;i++)t[i]&=b.t[i];return *this;}bitset& operator^=(const bitset &b){for(int i=0;i<L;i++)t[i]^=b.t[i];return *this;} }p[N],f,g; bitset operator-(const bitset &a,const bitset &b){bitset tmp;ull last=0;for(int i=0;i<L;i++){ull cur=(a.t[i]<b.t[i]+last);tmp.t[i]=a.t[i]-b.t[i]-last;last=cur;}return tmp; } int main() {scanf("%d%d",&n,&m);L=(n>>6)+1;for(int i=1,c;i<=n;i++)scanf("%d",&c),p[c].set(i);for(int i=1,c;i<=m;i++){scanf("%d",&c);(g=f)|=p[c];f.shift();f.set(0);f=g-f;f^=g;f&=g;}printf("%d",f.count());return 0; }

總結

以上是生活随笔為你收集整理的[科技]Loj#6564-最长公共子序列【bitset】的全部內容，希望文章能夠幫你解決所遇到的問題。

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