海沧区建设局网站 破路申请,怎么用织梦搭建网站,网页qq怎么登录,企业品牌推广的核心目的是传送门
题意#xff1a;给一个字符串SSS和正整数kkk#xff0c;将SSS分成最多kkk段#xff0c;每段不变或翻转#xff0c;使得最后的字典序最小。 ∣S∣≤5106|S|\leq5\times10^6∣S∣≤5106
发现不翻转可以看成拆成若干单字符分别翻转#xff0c;所以先分析一下必须翻转…传送门
题意给一个字符串SSS和正整数kkk将SSS分成最多kkk段每段不变或翻转使得最后的字典序最小。
∣S∣≤5×106|S|\leq5\times10^6∣S∣≤5×106
发现不翻转可以看成拆成若干单字符分别翻转所以先分析一下必须翻转的情况
把原串翻转记为SRS^RSR然后我们要求的是不断剪掉SRS^RSR的后缀然后依次拼起来
这样最终串的第一段是SRS^RSR的一个后缀所以最终串的开头一定有SRS^RSR的最小后缀但不一定是最小后缀作为第一段因为最小后缀可能会在前面作为非后缀出现
显然这个“最小后缀”是Lyndon分解后的最后一段记为sss 我们希望开头的sss尽量多
那么SRS^RSR可表示为a1st1a2st2...anstnasa_1st_1a_2st_2...a_nst_nasa1st1a2st2...anstnas(和Lyndon分解没有关系)
首先可以一刀把asasas砍掉然后找到a1∼ana_1\sim a_na1∼an中最大的砍下来 发现这第二段是砍掉asasas后的最小后缀相当于是下一轮的第一段
整理一下对SRS^RSR进行Lyndon分解并合并相等段这个Duval的时候魔改一下就可以了
然后依次砍掉最后一段并让k−1k-1k−1
注意我们假设了必须翻转如果我们发现有连续一段的长度为111的串相当于这一段不翻转只需要一步
这个流程需要砍掉两段只是后面一段和下一步的第一段重合了所以需要k2k2k2
完了之后有k≤2k \leq 2k≤2,如果剩下的只有一段直接大力讨论掉
如果k1k1k1,SSS和SRS^RSR取个min\minmin即可
如果k2k2k2,相当于分两段大力讨论 注意是针对原串
前面后面都不翻 就是原串只翻后面
我们考虑找到最优的位置
从左到右循环设当前最优位置为cutcutcut,需要更新的位置为iii 注意cuticuticuti (橙色部分为反串TTT指SRS^RSR)
我们希望比较两个串的大小 所以从cutcutcut开始找到第一个不同的位置比较大小
首先求出Scut∼i−1S_{cut\sim i-1}Scut∼i−1与TTT的最长公共前缀可以先跑一个exKMP,求出SSS的cutcutcut开始的后缀与TTT的最长公共前缀后和i−cuti-cuti−cut取min\minmin
如果把蓝色部分顶满了再加上后面的部分
即TTT从i−cuti-cuti−cut开始的后缀与TTT的最长公共前缀与n−i1n-i1n−i1取min\minmin
然后讨论一下找到第一个不同的字符比较大小即可
翻前面后面不管
继续从SRS^RSR的结尾截后缀设截取的后缀为TTT
考虑分解后的最后一个Lyndon串sss,TTT一定以sss开头也以sss结尾
根据意识流TTT一定不会只取一个分解后的LW的一部分也不会把两个相等的LW隔开
设TTT开始的第一段为s′ss′,所以sss是s′ss′的前缀
然后有若干个s′ss′接在后面这些s′ss′后的第一个设为ttt
根据Lyndon分解的定义t≤s′t \leq st≤s′。而如果ts′t sts′,那么从ttt开始截取后缀会比TTT小与定义矛盾
所以TTT一定是s′s′...s′ss...sss...sss...ss′s′...s′ss...s的形式
把上面剩下的 Lyndon分解合并相等段 的倒数第二段提出来如果sss是它的前缀说明倒数第二段是s′ss′此时分类讨论翻后面两段或者只翻最后一段如果不是说明s′ss′不存在只能翻最后一段
第二段和反串取min\minmin接在后面
复杂度O(n)O(n)O(n)
如果用std::string的话要注意AAB和AB复杂度不同……
#include iostream
#include cstdio
#include cstring
#include cctype
#include string
#include algorithm
#define MAXN 10000005
using namespace std;
string s,t,ts,ans;
int pos[MAXN],len[MAXN],tot;
inline string reverse(string s)
{string t;t.resize(s.size());int ns.size();for (int i0;in;i) t[n-i-1]s[i];return t;
}
void Duval(const string s)
{int ns.size();for (int i0;in;){int ji,ki1;while (s[j]s[k]) {if (s[j]s[k]) j;else ji; k;}len[tot]k-j;while (ij){pos[tot]ik-j-1;ik-j;}}
}
int p[MAXN];
void Exkmp(const string s)
{int ns.size();int mid0,mx0;p[0]n;for (int i1;in;i){if (imx) p[i]min(p[i-mid],mx-i1);while (s[ip[i]]s[p[i]]) p[i];if (ip[i]-1mx) midi,mxip[i]-1;}
}
int main()
{ios::sync_with_stdio(false);cins;treverse(s);int k;cink;if (k1) return coutmin(s,t),0;Duval(t);pos[0]-1;while (k2tot){if (len[tot]1){while (totlen[tot]1) anst.substr(pos[tot-1]1,pos[tot]-pos[tot-1]),--tot;--k;}else anst.substr(pos[tot-1]1,pos[tot]-pos[tot-1]),--k,--tot;}if (tot0) return coutans,0;if (tot1){string tmpt.substr(0,pos[1]1);tmpmin(tmp,reverse(tmp));coutanstmp;return 0;}sreverse(tt.substr(0,pos[tot]1));tst#s;Exkmp(ts);string tmpmin(s,t);int cut0,ns.size();for (int i1;in;i){int clmin(i-cut,p[n1cut]);if (cutcli) clp[cl];clmin(cl,n-cut);if ((cli-cut? s[cutcl]:t[cutcl-i])t[cl]) cuti;}tmpmin(tmp,s.substr(0,cut)t.substr(0,n-cut));string last.substr(pos[tot-1]1,len[tot]);string lasst.substr(pos[tot-2]1,len[tot]);int stpos[tot-1]1;string ttt.substr(st,n-st);string rest.substr(0,n-tt.size());ttmin(res,reverse(res));tmpmin(tmp,tt);if (laslass){stpos[tot-2]1;ttt.substr(st,n-st);rest.substr(0,n-tt.size());ttttmin(res,reverse(res));tmpmin(tmp,tt);}coutanstmp;return 0;
}
