感觉挺有参考意义的，单独拎出来发一个。
Loj6564 最长公共子序列
求 \(a,b\) LCS 长度。
\(n,m \le 7\times 10^4\)，1s，1GB。
这 \(O(n^2)\) 还能往下卡吗？
可以的，\(O(\frac{n^2}{w})\)。
考虑 \(dp_{i,j}\) 的转移，有 \(0 \le dp_{i,j+1}-dp_{i,j} \le 1\)，即差分数组是 01 串，给差分压位吧。
- 我们现在要匹配 \(a,b\) 两个串。
- 设 \(f_{i,j}\) 表示 \(a\) 匹配到前 \(i\) 位，\(b\) 匹配到前 \(j\) 位的答案，差分 bitset 为 \(f_i\)。
- 预处理出每个字符在 \(a\) 中出现的位置组成的 bitset \(g_i\)。
- 考虑求 LCS 的过程。相当于是我们要尽量匹配前面的字符。
- 放到 \(f_i\) 里面也就是，对于 \(f_i\) 的每段连续的 \(000\cdots 1\) ，在 \(g_{b_i}\) 的对应区间中找到最靠前的那一个 \(1\)，然后把 \(f_i\) 的那个位置变成 \(1\)，并把这段区间原本最后的 \(1\) 变成 \(0\)，即往前匹配一位。特别地，最后的 \(000\cdots 0\) 也算，只是没有 \(1\) 变 \(0\) 的操作。
- 这玩意用位运算表示是记 \(X=f_{i-1}\operatorname{or} g_{b_i}\)，\(f_i=(X-((f_{i-1}<<1)|1))\operatorname{xor} X \operatorname{and} X\)。
- 大概解释下意义：
- 取 lowbit 有这么一种写法：\(\text{lowbit}(x)=(x-1)\text{ xor }x\text{ and } x\)。
- 因为分了段，不一样的就只是那个 \(x-1\)，考虑怎么把对 \(x\) 整个 \(-1\) 变成对 \(x\) 的每一段都单独 \(-1\)。
- 这是好解决的，因为每一段在 \(f_{i-1}\) 中都以 \(1\) 结尾，右移一位变成每一段开头，再加上最前面的 \(1\) 就可以了。
最后 \(f_n\) \(1\) 的个数即为答案。
然后如你所见，因为带个二进制减法，bitset 要手写……
struct bts {
using ull=unsigned long long;
int n;
ull a[N/64+7];
bts() { memset(a,0,sizeof(a)); }
void ini(int _n) { memset(a,0,sizeof(a)); n=_n/64+1; }
void set(int p) { a[p>>6]|=(ull)1<<(p&63); }
int cnt(int ret=0) {
for (int i=0;i<n;i++) ret+=__builtin_popcountll(a[i]);
return ret;
}
void sft() {
ull flg=0,tmp;
for (int i=0;i<n;i++)
tmp=flg,flg=a[i]>>63&1,a[i]=(a[i]^(flg<<63))<<1|tmp;
}
friend bts operator & (bts x,bts y) {
bts ret=x;
for (int i=0;i<x.n;i++) ret.a[i]=x.a[i]&y.a[i];
return ret;
}
friend bts operator ^ (bts x,bts y) {
bts ret=x;
for (int i=0;i<x.n;i++) ret.a[i]=x.a[i]^y.a[i];
return ret;
}
friend bts operator | (bts x,bts y) {
bts ret=x;
for (int i=0;i<x.n;i++) ret.a[i]=x.a[i]|y.a[i];
return ret;
}
friend bts operator - (bts x,bts y) {
bts ret=x; ull lst=0;
for (int i=0;i<x.n;i++)
ret.a[i]=x.a[i]-y.a[i]-lst,lst=x.a[i]<y.a[i]+lst;
return ret;
}
} f,g[N],tmp;
int mtc(int n,int m,int *a,int *b) {
f.ini(n),tmp.ini(n);
for (int i=0;i<N;i++) g[i].ini(n);
for (int i=1;i<=n;i++) g[a[i]].set(i);
for (int i=1;i<=m;i++) {
tmp=f|g[b[i]];
f.sft(),f.set(0);
f=((tmp-f)^tmp)&tmp;
}
return f.cnt();
}
Gym103652F Square Subsequences
给定一个字符串。求字符串中最长的满足条件的子序列：长度为偶数，且前半段和后半段相同。输出具体结果
\(1 \le \sum n \le 3000\)，2s，256MB。
枚举分割点切成两个串再套上面的 LCS 即可。
然后这里会出现一个巨坑：
博主一开始写的时候直接把出来的 \(f\) 中每一个 \(1\) 的位置当成匹配到的位置，然后直接把每一个 \(1\) 上的字符输了出来……
但是根据转移式，每一个 \(1\) 不一定来自同一个 \(f\) 前面的值，还有可能来自已经死去了的 \(f_{i-1}\)……博主因为这一点调了三个小时。
由于这题匹配的串的特殊性，确定了分割点之后再跑一遍朴素 DP 确定答案即可。
理论上你很难在 bitset 里把匹配过程记下来……所以如果要求方案的话还是老老实实写 \(O(n^2)\) DP 罢。如果有会的戳一下博主。
标签：le,匹配,LCS,int,bitset,优化,dp From： https://www.cnblogs.com/CarroT1212/p/18005954/BitsetOptimizingLCS