重庆网站设计工作室,雅虎网站收录入口,wordpress学院模板,龙岗网站https://acm.hdu.edu.cn/showproblem.php?pid7015 题意#xff1a;对于每次以i来分割字符串#xff0c;计算两个分割串的子串的k-匹配的数量。
思路#xff1a;当我们计算到ans[i]是#xff0c;我们可以当成从ans[i-1]加上【1-i】字符串和【i1#xff0c;n】的k-匹配数量…https://acm.hdu.edu.cn/showproblem.php?pid7015 题意对于每次以i来分割字符串计算两个分割串的子串的k-匹配的数量。
思路当我们计算到ans[i]是我们可以当成从ans[i-1]加上【1-i】字符串和【i1n】的k-匹配数量再减去【1-i-1】和【i-n】的k-匹配的数量。
sum1[i]【1-i-1】和【i-n】的k-匹配的数量
sum2[i]:【1-i】和【i1n】的k-匹配数量
那我们怎么算这个呢我们设dp1[i][j]代表从i开始和从j开始k-匹配的数量方向是从1—n
然后sum1[i] 就是dp1[0-(i-1)][i]的和我们求一下前缀和就好了
计算sum2[i]同理设dp2[i][j]表示反方向从i开始和和从j开始 k-匹配的数量反向是从n—1
然后sum2[i] 就是dp2[(i1)-n][i]的和
关键点在于我们如何求出dp1[i][j]dp2[i][j]
我们可以枚举d表示他们的距离每次求出dp1[i][id]和dp2[i][i-d]
然后使用双指针优化dp1[i][id]能匹配到 j那么dp1[i1][i1d]比然也能匹配到 j那我们下一个可以直接从开始j往后移。
#include cstdio
#include cstring
#include string
#include cmath
#include iostream
#include algorithm
#include queue
#include cstdlib
#include stack
#include vector
#include set
#include map
#include bitset
#include complex
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define sc second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
const ll mod1e97;
const ll N 6e610;
const double eps 1e-6;
const double PIacos(-1);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll re(){ll x;scanf(%lld,x);return x;}
int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1};
int n,k;
int dp1[3100][3100],dp2[3100][3100];
ll sum1[3100],sum2[3100];
char s[3100];
void solve(){cinnk;scanf(%s,s1);for(int i1;in;i){for(int j1;jn;j){dp1[i][j]dp2[i][j]0;}sum1[i]sum2[i]0;}for(int i1;in;i){if(s[i]s[i1]||k0) dp1[i][i1]1;if(s[i]s[i1]||k0) dp2[i1][i]1;}for(int d2;dn;d){int j-1;int x0;for(int i1;idn;i){while(xkidjnjd){j;if(idjn) break;if(s[ij]!s[idj]) x;}dp1[i][id]j;if(s[i]!s[id]) x--;j--;}}for(int d2;dn;d){int j-1;int x0;for(int in;i-d1;i--){while(xki-d-j1jd){j;if(i-d-j1) break;if(s[i-j]!s[i-d-j]) x;}dp2[i][i-d]j;if(s[i]!s[i-d]) x--;j--;}}for(int i1;in;i){for(int ji1;jn;j){sum2[i]dp2[j][i];}}for(int i2;in;i){for(int j1;ji;j){sum1[i]dp1[j][i];}}ll ans0;for(int i1;in;i){ans(sum2[i]-sum1[i]);coutansendl;}
}
int main()
{// ioscint;while(t--) solve();return 0;
}
