【学习笔记】CF613E Puzzle Lover

这题本质上还是数据结构。

首先看到这个$2\times n$的网格图就很容易想到分治。我们还是考虑把要统计的东西变得可视化，一条路径要么穿过中线一次，那么我们可以将两边的串拼起来得到答案；要么穿过中线两次，考虑其中一边的路径是固定的，那么我们枚举两个端点再判断一下和原串是否匹配的上就做完了。那么考虑预处理出$d{p}_{i,j,0/1,0/1}$表示从位置$(1/2,i)$开始，匹配长度为$j$，向左/右走的方案数，这事实上非常好转移，可以自己编一下。当然可能还要把串正着和倒着处理一边，总之挺麻烦的。

将网格图翻转后做两次即可得到答案。求$Lcp$可以用暴力$dp$代替。事实上也并不需要分治。注意不要算重。

细节题，贼容易写挂。

复杂度$O(n^2)$。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define db double
#define cpx complex<db>
using namespace std;
const int mod=1e9+7;
const int N=2005;
int n,K,Right[2][N][N],Left[2][N][N],dpl[2][N][N],res;
string s[2],str;
void add(int &x,int y){x=(x+y)%mod;
}
void solve(){for(int i=0;i<2;i++){for(int j=n-1;j>=0;j--){for(int k=0;k<K;k++){Right[i][j][k]=(s[i][j]!=str[k])?0:((j!=n-1&&k>=1)?(Right[i][j+1][k-1]+1):1);}}}for(int i=0;i<2;i++){for(int j=0;j<n;j++){for(int k=0;k<K;k++){Left[i][j][k]=(s[i][j]!=str[k])?0:((j>=1&&k>=1)?(Left[i][j-1][k-1]+1):1);}}}memset(dpl,0,sizeof dpl);for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[0]){dpl[i][j][0]=1;}}}//fixedfor(int i=0;i<n;i++){for(int j=i;j<n;j++){for(int k=0;k<2;k++){//strangeif(Left[k][j][2*(j-i+1)-1]>=j-i+1&&Right[k^1][i][j-i]>=j-i+1){add(dpl[k][j][2*(j-i+1)-1],1);}}}}for(int k=1;k<K;k++){for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[k]){if(j)add(dpl[i][j][k],dpl[i][j-1][k-1]);if(s[i^1][j]==str[k-1]){if(j&&k-2>=0)add(dpl[i][j][k],dpl[i^1][j-1][k-2]);}}}}}
}
void getans(){//fixedfor(int i=0;i<2;i++){for(int j=0;j<n;j++){add(res,dpl[i][j][K-1]);}}for(int i=1;i<n;i++){for(int j=i+1;j<n;j++){for(int k=0;k<2;k++){if(Right[k][i][K-1]>=j-i+1&&K-(j-i+2)>=0&&Left[k^1][j][K-(j-i+2)]>=j-i+1&&K-2*(j-i+1)-1>=0){add(res,dpl[k^1][i-1][K-2*(j-i+1)-1]);}}}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s[0]>>s[1]>>str,n=s[0].size(),K=str.size();//fixedif(K==1){for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[0]){add(res,1);}}}cout<<res;return 0;}if(K==2){for(int i=0;i<2;i++){for(int j=0;j<n-1;j++){if(s[i][j]==str[0]&&s[i][j+1]==str[1]){add(res,1);}if(s[i][j+1]==str[0]&&s[i][j]==str[1]){add(res,1);}}}for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[0]&&s[i^1][j]==str[1]){add(res,1);}}}cout<<res;return 0;}//fixedsolve();getans();//fixedswap(s[0],s[1]),reverse(s[0].begin(),s[0].end()),reverse(s[1].begin(),s[1].end());solve();getans();cout<<res<<"\n";
}