脚本宝典收集整理的这篇文章主要介绍了cf1615f LEGOndary Grandmaster，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

cf1615f LEGOndary Grandmaster

对于两个长度为 (n) 的 (01) 串 (s,t) ，你可以对 (s) 进行两种操作：把相邻两个 (00) 变成 (11) 或把相邻两个 (11) 变成 (00) ，定义 (s) 到 (t) 的距离为最少操作次数使得 (s) 变成 (t) ，如过没法变则距离为 (0) 。

现在你有两个不完整的字符串，可以把其中的 (??) 变成 (0) 或 (1) ，求所有情况所得到的两个 (01) 串的距离之和。

多测，有 (T) 组数据.

(1leq Tleq 1000,1leq |s|=|t|leq 2000,1leq sum |s|leq 2000)

这个 (00to 11,11to 00) 的操作是无法简单统计出 (sto t) 的操作数的.

这里用到一个我想了很久没有想到的套路，把 (s,t) 偶数位的 (01) 翻转，操作就可以看成是 (01to 10,10to 01) ，这就成了交换相邻两位了. 非常妙.

此时，对于 (s) 可以交换相邻两位，得到 (t) 的操作数是，令 (s) 中第 (i) 个 (1) 的位置 (ps_i) 和 (t) 中第 (i) 个 (1) 的位置 (pt_i) , 操作数和即为 (sum |ps_i-pt_i|) .

令 (f(i,j)) 为 (s) 串匹配最后一个 (1) 的位置 (i) ，(t) 串匹配到的最后一个 (1) 的位置为 (j) 的操作数，(g(i,j)) 是(s) 串匹配最后一个 (1) 的位置 (i) ，(t) 串匹配到的最后一个 (1) 的位置为 (j) 的串的数量.

可以得到转移 (f(i,j)=sumlimits_{lst_i}^i sumlimits_{lst_j}^j f(i',j')+|i-j|g(i',j')) .

这个 $sumsum $ 可以用前缀和解决.

时间复杂度 : (O(sum|s|^2))

空间复杂度 : (O(|s|^2))

code

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
const int inf=1e9+10;
const int mod=1e9+7;
int T;
int n;
string s,t;
int f[N][N],g[N][N],cnt[N][N],S[N][N];
bool oks[N],okt[N],valid[N][N];
inline void upd(int&x,int y){x=(x+y)%mod;}
void solve(){
	cin>>n>>s>>t;
	for(int i=0;i<n;i+=2){
		if(s[i]=='0')s[i]='1';
		else if(s[i]=='1')s[i]='0';
	}
	for(int i=0;i<n;i+=2){
		if(t[i]=='0')t[i]='1';
		else if(t[i]=='1')t[i]='0';
	}
	for(int i=0;i<n;i++){
		bool ok=true;
		for(int k=0;k<i;k++)if(s[k]=='1')ok=false;
		if(s[i]=='0')ok=false;
		if(!ok)continue;
		for(int j=0;j<n;j++){
			ok=true;
			for(int k=0;k<j;k++)if(t[k]=='1')ok=false;
			if(t[j]=='0')ok=false;
			if(!ok)continue;
			valid[i][j]=true;
		}
	}
	oks[n]=okt[n]=true;
	for(int i=n-1;i>=0;i--)oks[i]=s[i]!='1'?oks[i+1]:0;
	for(int i=n-1;i>=0;i--)okt[i]=t[i]!='1'?okt[i+1]:0; 
	for(int i=0;i<n;i++){
		int pos=0;
		for(int j=i-1;j>=0;j--){
			pos=j;
			if(s[j]=='1')break;
		}
		int sum1=0,sum2=0;
		for(int j=0;j<n;j++){
			if(s[i]!='0'&&t[j]!='0'){
				upd(cnt[i][j],sum1);
				upd(cnt[i][j],valid[i][j]);
				upd(f[i][j],(1ll*cnt[i][j]*abs(i-j)%mod+sum2)%mod);
			}
			if(t[j]=='1')sum1=sum2=0;
			upd(sum1,((i?S[i-1][j]:0)-(pos?S[pos-1][j]:0)+mod)%mod);
			upd(sum2,((i?g[i-1][j]:0)-(pos?g[pos-1][j]:0)+mod)%mod);
		}
		for(int j=0;j<n;j++)S[i][j]=((i?S[i-1][j]:0)+cnt[i][j])%mod;
		for(int j=0;j<n;j++)g[i][j]=((i?g[i-1][j]:0)+f[i][j])%mod;
		
	}
	int ans=0;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(oks[i+1]&&okt[j+1])upd(ans,f[i][j]);
	cout<<ans<<endl;
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)f[i][j]=g[i][j]=cnt[i][j]=S[i][j]=0;
	for(int i=0;i<=n;i++)oks[i]=okt[i]=0;
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)valid[i][j]=0;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	} 
	return 0;
}
/*inline? ll or int? size? min max?*/

脚本宝典总结

以上是脚本宝典为你收集整理的cf1615f LEGOndary Grandmaster全部内容，希望文章能够帮你解决cf1615f LEGOndary Grandmaster所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。