企业官网建设流程全解析

如题所示，要我们求的是最长可能的取模合并后相同的字符串长度，考虑到合并操作本身满足结合律，而且合并顺序不影响，故可以建立前缀和数组，代表i-n的合并取模数，这个题可以转化为，对ab字符串分别分块，使得每一块的数值取模相等，如果我们可以把它当作前缀和数组的差分

按块分：Pa[i]-Pa[i-1]=Pb[i]-Pb[i-1],最左边的边界都是0，就需要每块相等，可以推出每个Pa[i]=Pb[i],依据这个，相当于找位置严格递增的元素相等的序列，二维dp就是

dp[i][j]代表a串i之前、b串j之前的方案数量，状态转移方程为：

通过滚动数组进行优化，可以存一个数作为dp[i-1][j],更新之后就是左上角的方格，而dp[i-1][j]是旧数组，dp[i][j-1]是左边已经处理过的数组，代码如下：

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--) { string a,b; cin>>a>>b; int as=a.size(),bs=b.size(); vector<int> pa(as+2),pb(bs+2); for(int i=0;i<as;i++)pa[i+1]=(pa[i]+(i>=as?0:a[i]-'0'))%10; for(int i=0;i<bs;i++)pb[i+1]=(pb[i]+(i>=bs?0:b[i]-'0'))%10; vector<int> dp(as+2,0); if(pa[as]!=pb[bs]) { cout<<-1<<"\n"; continue; } for(int i=0;i<bs;i++) { int ini=0; for(int j=0;j<as;j++) { int old=dp[j]; if(pa[j]==pb[i]) { dp[j]=ini+1; } else { int left=(j==0?0:dp[j-1]); dp[j]=max(dp[j],left); } ini=old; } } cout<<dp[as-1]<<"\n"; } }