html5 公众号 网站开发,大连市城市建设管理局网站,做淘宝网站用什么浏览器,wordpress小程序二开正题
题目链接:https://www.luogu.com.cn/problem/P6793 题目大意
给出两个长度为nnn的字符串#xff0c;取出他们所有长度为kkk的连续子串分别构成两个可重集合A,BA,BA,B。
你每次可以花费xxx点代价修改AAA中一个字符串长度为xxx的后缀#xff0c;求至少花费多少代价能够…正题
题目链接:https://www.luogu.com.cn/problem/P6793 题目大意
给出两个长度为nnn的字符串取出他们所有长度为kkk的连续子串分别构成两个可重集合A,BA,BA,B。
你每次可以花费xxx点代价修改AAA中一个字符串长度为xxx的后缀求至少花费多少代价能够使得两个集合完全相同。
1≤k≤n≤1.5×1051\leq k\leq n\leq 1.5\times 10^51≤k≤n≤1.5×105 解题思路
两个串S,TS,TS,T的匹配代价是max{k−LCP(S,T),0}max\{k-LCP(S,T),0\}max{k−LCP(S,T),0}
这个和之前有道题很像沿用想法就是在后缀树上搞。
两个点的LCPLCPLCP可以在他们后缀树上的LCALCALCA处得到。
现在问题就变为了有一些黑白点知道两个点匹配的代价与LCALCALCA的关系求最小代价和。
基础贪心直接在深度小的地方合并完就好了。
后缀树就是把反串跑广义SAM就好了
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N6e510;
struct node{ll to,next;
}a[N];
ll n,k,tot,ls[N],v[N][2],ans;
ll ch[N][26],fa[N],len[N],cnt;
char sa[N],sb[N];
ll Insert(ll p,ll c){if(ch[p][c]){ll qch[p][c];if(len[p]1len[q])return q;ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;return nq;}ll npcnt;len[np]len[p]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{ll qch[p][c];if(len[p]1len[q])fa[np]q;else{ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]fa[np]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return np;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x){for(ll ils[x];i;ia[i].next){ll ya[i].to;dfs(y);v[x][0]v[y][0];v[x][1]v[y][1];}ll tmpmin(v[x][0],v[x][1]);ansmax(k-len[x],0ll)*tmp;v[x][0]-tmp;v[x][1]-tmp;return;
}
signed main()
{scanf(%lld%lld,n,k);scanf(%s,sa1);scanf(%s,sb1);ll lastcnt1;for(ll in;i1;i--)lastInsert(last,sa[i]-a),v[last][0]((n-i1)k);last1;for(ll in;i1;i--)lastInsert(last,sb[i]-a),v[last][1]((n-i1)k);for(ll i2;icnt;i)addl(fa[i],i);dfs(1);printf(%lld\n,ans);return 0;
}
