深圳百度推广网站建设,网站策划选题,移动app开发定制,做英文网站价格$ CSP.S $ 集训刷题记录#xff1a; $ By~wcwcwch $ 一、字符串专题#xff1a; 1. 【模板】$ manacher $ 算法 模型#xff1a; 求出字符串 $ S $ 中所有回文串的位置及长度。 $ solution $ #xff1a; 个人理解#xff1a;解决这类问题#xff0c;回文串的对称性质最重… $ CSP.S $ 集训刷题记录 $ By~wcwcwch $ 一、字符串专题 1. 【模板】$ manacher $ 算法 模型 求出字符串 $ S $ 中所有回文串的位置及长度。 $ solution $ 个人理解解决这类问题回文串的对称性质最重要。 于复杂度最关键的一句话 $ f[i]min~(~r-i~,~f[~mid\times2-i~]~)~ $ 实现不同边界可能不一样 这个 $ min $ 函数左边 $ r-i $ 是当前位置到它所属于的回文串边界的距离右边 $ mid\times 2 -1 $ 是它在所属于的回文串的另一边的对应位置。如果取左边那么我用当前位置扩展会超出当前回文串边界于是必然能够使 $ r $ 向右扩展如果取右边我们发现由于回文串的对称性这个位置必然不能继续向外扩展因为他最开始向外扩展必然还是在当前回文串边界内否则 $ min $ 函数肯定取的左边而如果它能在当前回文串内扩展它的对称位置 $ mid\times 2 -1 $ 也能而 $ f[~mid\times2-i~] $ 已是扩展最大值与之矛盾。 总结一下如果 $ min $ 函数取左边那么 $ r $ 一定能向右扩展如果取右边那么复杂度为 $ 1 $ 常数。于是复杂度为 $ r $ 的值域和 $ 1 $ 的次数两者都不超过 $ n $ 于是复杂度为 $ O(2\times n) $ 就算再加上与处理时加“#”号也是常数而已。 2. 【模板】扩展 $ KMP $ 模型 有一个字符串 $ a $ 要求输出【 $ a $ 本身】和【 $ a $ 的每一个后缀】的最长公共前缀 。 $ solution $ $ KMP $ 和 $ Manacher $ 思想的结合产物。不过个人更倾向于 $ Manacher $ 。因为他的计算方法和 $ Manacher $ 神似都是在某一个位置先根据之前的结果得到一个初始的公共前缀长度就是“回文串”变成了最长公共前缀回文串的中心 $ mid $ 变成了最长公共前缀的左端点 $ l $ 最后 $ min $ 函数长的不一样了。 我们对于 $ a $ 处理出它【每一位开始的后缀】和【 $ a $ 本身】的最长公共前缀 $ f[i] $ 。注意我们要从第二位开始 因为 $ f[1]|a| $ 很特殊。我们用 $ l $ 记录已经遍历过的 $ i $ 中 $ if[i] $ 最大的 $ i $ 同时用 $ r $ 记录 $ if[i] $ 这两者初始均为 $ 0 $ 。然后 $ f[i]min(~r-i~,~f[i-l1]~) $ 这个计算初始值的式子和 $ Manacher $ 很像 $ i $ 处于一个公共前缀里那么 $ i $ 后面的字母一定和 $ f[i-l1] $ 后面的字母在 $ r-i $ 范围内保持一致于是直接拿来作为初始值即可。复杂度证明和上面 $ Manacher $ 一样 $ code $ int n,m;
int f[2000005];
string s,a;int main(){cina; na.size();cins; ms.size();s s#a; nm2; //加到一起rg l0,r0; f[1]m; //第一个不管for(rg i2;in;i){if(ir) f[i]min(r-i,f[i-l1]); //确定初始值while(s[f[i]1]s[if[i]]) f[i]; //向后扩展if(if[i]-1r) li,rif[i]-1; //更新l和r的值}for(rg i1;im;i) printf(%d%c,f[i],im?\n: );for(rg im2;in;i) printf(%d%c,f[i],in-1?\n: );return 0;
} 3. $ LOJ~3095 $ $ Snoi~2019 $ 字符串 题意概括 给一个长度为 $ n $ 的字符串 $ S $ 记 $ S′_i $ 表示 $ S $ 删去第 $ i $ 个字符后得到的字符串输出\(( S′_1 , 1)...(S′_n , n)\) 的字典序排序结果。 $ n\leq 10^6 $ $ solution $ 我们仔细观察题目手算分析样例可以发现一个性质 设从 $ i $ 号位置开始往后第一个与 $ i $ 号位不同的位置为 $ j $ 则 $ [i,j-1] $ 的字符串相等。若 $ a[i]a[j] $ 则可以发现后面的字符串因为多包含一个 $ a[i] $ 而小于 $ [i,j-1] $ 。若 $ a[i]a[j] $ 则可以发现后面的字符串因为多包含一个 $ a[i] $ 而大于 $ [i,j-1] $ 。于是我们开一个双端加入的数组记录最后的答案。期望复杂度 $ O(n) $ $ code $ nqr(); cina; a a; a[n1]); //防出界rg l0,rn1; //记录双端指针for(rg i1;in;i){ rg ji;while(a[i]a[i1])i; //找到连续相同串的右端点if(a[i1]a[i]) for(rg kj;ki;k) s[l]k; //这一段都必然比后面的串小else for(rg ki;kj;--k) s[--r]k; //这一段都必然比后面的串大}for(rg i1;in;i) printf(%d ,s[i]); 4. 洛谷 $ P5446 $ $ THUPC~2018 $ 绿绿和串串 题意概括 对于字符串 $ S $ 定义运算 $ f(S) $ 为将 $ S $ 的前 $ |S|-1 $ 个字符倒序接在 $ S $ 后面形成的长为 $ 2|S|-1 $ 的新字符串。现给出字符串 $ T $ 询问有哪些串长度不超过 $ |T| $ 的串 $ S $ 经过若干次 $ f $ 运算后得到的串包含 $ T $ 作为前缀。$ 1 \le |T| \le 5 \times 10^6. $ $ solution $ 很纠结的一道题调了好一会才发现思维不够严谨判断出错了。 首先我们不难发现这是一道与回文串有关的题目我们可以发现如果 $ S $ 串中存在一个位置 $ i $ 使得它的最长回文串能到达 $ S $ 串的末尾那么对 $ [1,i] $ 这一段字符进行 $ f(1,i) $ 的操作一定可以得到一个合法新字符串使 $ S $ 为其前缀。然后我们还可以发现如果将这些位置标记如果 $ S $ 串中还有一些位置 $ i $ 使得从 $ i $ 扩展的回文串可以到达 $ S $ 串的第一个字符且这个回文串的末尾字符是被标记了的那么这个位置也是合法的因为只要进行多次 $ f $ 操作即可。 $ code $ tqr();while(t--){cins; ns.size(); s s; //读入rg mid0,r0; s[0](; s[n1]); //设边界for(rg i1;in;i){ f[i]0;if(ir) f[i]min(r-i,f[(mid1)-i]); //manacher寻找初值while(s[i-f[i]-1]s[if[i]1]) f[i]; //扩展if(if[i]r) midi,rif[i]; //更新} k[n]1;for(rg in;i1;--i) //如果转一次就合法或者能够连转多次if(if[i]n||(i-f[i]1k[if[i]])) k[i]1;for(rg i1;in;i)if(k[i])printf(%d ,i),k[i]0; //输出清零puts();} 5. 洛谷 $ P4503 $ $ CTSC~2014~$ 企鹅 $~QQ $ 题意概括 给出一个带通配符的字符串 $ S $ 通配符分两种一种可以匹配恰好一个字符另一种可以匹配任意个包括 $ 0 $ 个字符。再给出 $ n $ 个串 $ T_i $ 询问 $ T_i $ 能否与 $ S $ 匹配。 $ 1 \le n \le 100, 1 \le |S|,|T_i| \le 10^5, 0 \le $ 通配符个数 $ \le 10. $ $ solution $ 总算搞了一道 $ Hash $ 题了应该算是第一道仔细调了细节的代码。对于 $ Hash $ 我们有单哈希和多哈希根据元素信息的维数来看。但是个人还是喜欢单哈希里的 $ long~long $ 效果和双 $ int $ 哈希差不多。 $ long~long $ 好写跑的飞快但是模数太大容易溢出双 $ int $ 哈希一般用 $ STL:pair $ 跑的不快但是正确性高很多。 这道题我们可以采取暴力措施因为只有一位可以不同所以我们干脆枚举这一位是哪一位然后将每个字符串除开这一位的前缀和后缀相互比较如果相同那么就是合法的一对。前缀和后缀的比较可以预处理 $ Hash $ 得到。 期望复杂度 $ O(m\times n\times logn) $ $ code $ const ll mod20190816170251; //纪念CCF关门的日子是个质数
//小常识1e183和1e189都是质数很好记998244353和998244853和993244853也是。ll ans;
int n,m,k;
ll q[30005];
ll f[30003][202]; //前缀hash
ll s[30003][202]; //后缀hash
char a[30005];int main(){nqr(); mqr(); kqr();for(rg i1;in;i){scanf(%s,a1); //scanf读入快一点 //107这个数不要太大防溢出for(rg j1;jm;j) f[i][j](f[i][j-1]*107a[j])%mod; //前缀hashfor(rg jm;j1;--j) s[i][j](s[i][j1]*107a[j])%mod; //后缀hash} ll x1; //模数不能太大否则这里会炸掉for(rg i1;im;i){ //每个位置分开做会快些正确性也高一些for(rg j1;jn;j)q[j]f[j][i-1]*xs[j][i1]; //前后合并sort(q1,qn1);for(rg j1,o1;jn;jo){while(q[j]q[o1]) o; //找到连续一段相同的ans((ll)(o-j1)*(o-j))1; //注意答案贡献为C[x][2]从一段中取一对} xx*107%mod;}printf(%lld\n,ans);return 0;
} 6. 洛谷 $ P3167 $ $ CQOI~2014 $ 通配符匹配 题意概括 给出一个带通配符的字符串 $ S $ 通配符分两种一种可以匹配恰好一个字符另一种可以匹配任意个包括 $ 0 $ 个字符。再给出 $ n $ 个串 $ T_i $ 询问 $ T_i $ 能否与 $ S $ 匹配。 $ 1 \le n \le 100, 1 \le |S|,|T_i| \le 10^5, 0 \le $ 通配符个数 $ \le 10. $ $ solution $ 想法颇多但实现艰巨的一道题写了一晚上加一上午。 讲课时和 $ Itst $ 讨论觉得是 $ AC $ 自动机结果大鸽鸽一讲是 $ Hash $ 题解第一篇居然也是 $ Hash $ 但是 $ AC $ 自动机本就和 $ Hash $ 完成的东西一样都要求两段子串是否相等 $ AC $ 自动机预处理 $ Hash $ 在线 $ O(1) $ 求所以同出一源。 首先这道题的突破口是通配符无疑因为数量太少我们可以根据通配符划分模式串得到不多于 $ 10 $ 个模式串。然后我们可以考虑在给的 $ n $ 个串中找到这些模式串的位置然后想办法合并这些位置以判断是否合法。想法是好的实现起来却十分残酷首先 $ AC $ 自动机找串复杂度 $ |S|^2 $ 直接扑街但是我们很快发现模式串不多而且只需要知道其是否在某个位置出现我们考虑状压每次不暴力访问直接位运算期望复杂度 $ O(|S|) $ 。 然后我们发现实现这个匹配是非常难的。但是我们也可以发现匹配是线性的按顺序的匹配和动态规划很像于是我们考虑动态规划对每一个位置记录他可以匹配完哪一个的模式串。然后我们对于每一个状态某一个位置是某一个模式串的末尾可以根据这个模式串之前是哪一个通配符来转移如果是 $ ? $ 那么直接找到模式串开头前一个位置看它是否匹配了上一个模式串如果是 $ * $ 就找之前所有状态是否有匹配了上一个模式串的位置用前缀或位运算和。利用状压我们可以直接位运算解决所有转移。 $ code $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;int n,m,t;
int s[10005];
int b[10005];
int mx[100005];
int f[100005];
int k[100005];
char a[100005];struct AC{int tt;int end[100005];int fail[100005];int son[100005][26];inline void add(int l,int r,int v){rg now0,*to;for(rg il;ir;i){toson[now][a[i]-a];if(*to)now*to;else now*tott;}end[now]|(1v); //将这个模式串编号状压到自动机里面}inline void failed(){queueint q;for(rg i0;i26;i)if(son[0][i]){end[son[0][i]]|end[0]; //fail树的应用这个位置的字符串包含哪些模式串q.push(son[0][i]);}rg *to,next;while(!q.empty()){rg iq.front(); q.pop(); nextfail[i];for(rg j0;j26;j){toson[i][j];if(*to){ q.push(*to);fail[*to]son[next][j];end[*to]|end[son[next][j]]; //fail树的应用这个位置的字符串包含哪些模式串}else *toson[next][j];}}}inline void find(int l){ //找到文本串里每个位置对应哪些模式串末尾rg now0; f[0]end[now];for(rg i1;il;i){nowson[now][a[i]-a];f[i]end[now]; //这个位置是那些模式串的末尾}}
}T;inline int qr(){register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}int main(){scanf(%s,a1); mstrlen(a1); a[m]s; //最后加个字符是为了防通配符在末尾for(rg i1,j1,x0;im;ij){while(jma[j]aa[j]z)j; //以通配符为界划分为若干模式串T.add(i,j-1,t); s[(1t)]x; b[(1t)]j-i; //记录上一个通配符是哪一种以及串长if(jma[j]?) x1; else x2; //辨别这个通配符是哪一种}T.failed(); rg nqr();for(rg i1;in;i){ //每个待匹配串都视为文本串跑AC自动机scanf(%s,a1); mstrlen(a1);a[m]s; T.find(m); k[0]mx[0]1; //预处理初始化for(rg j1;jm;j) k[j]mx[j]0; //初始化for(rg j0;jm;j){for(rg xf[j];x;x-x-x){ //这层循环的复杂度为通配符个数rg yx-x;if(s[y]0) k[j]|y(k[j-b[y]]1); //如果之前没有通配符if(s[y]1) k[j]|y(k[j-b[y]-1]1); //上一个通配符是?就直接看前面对应位置是否可以匹配if(s[y]2) k[j]|y(mx[j-b[y]]1); //上一个通配符是*就直接看全局因为中间字符可消mx[j]|k[j]; //这个对于*操作很重要记录这个位置之前的最高匹配度} mx[j1]mx[j]; //这个对于*操作很重要记录这个位置之前的最高匹配度}if(k[m](1t))puts(YES); //看最后一位的匹配度是否达到最高else puts(NO);}return 0;
}7. 洛谷 $ P3193 $ $ HNOI~2008~GT $ 考试 题意概括 给一个数字串 $ S $ 求有多少长度为 $ n $ 的数字串 $ T $ 不包含 $ S $ 作为子串。 $ 1 \le |S| \le 100, 1 \le n \le 10^9. $ $ solution $ 并没有想象中上一道题的这么难唯独就是要写严格 $ O(1) $ 的 $ kmp $ 算法。感觉比普通的还好写一点。 首先我们求的串中必须不包含 $ S $ 这个我们其实不难想到动态规划。设 $ F[i][j] $ 表示已经构造到第 $ i $ 个位置在末尾最多有 $ j $ 个位置和 $ S $ 的前 $ j $ 个位置一致。之所以这样设状态是因为我们构造合法串时只需要知道串后面的字符和 $ S $ 的匹配程度这样可以知道我们放下一个字符会不会使得一段后缀变为 $ S $ 任何一个子串都可以表示为一个前缀的后缀。然后我们就需要转移方程这个其实就是一个 $ kmp $ 的过程。但是为了快速转移我们需要知道在当前串后面加入某个字符会使匹配转移到哪一个位置这个需要用严格 $ O(1) $ 的 $ kmp $ 算法。再然后我们就可以将这个转移过程用矩阵来完成通过改变矩阵系数使得一次转移等同一次乘法。然后快速幂。 $ code $ int n,m,k;
int nx[105];
int f[105][10];
char a[105];struct su{ //矩阵int s[101][101];inline void operator *(const su x){ //矩阵乘法su res;for(rg i0;im;i){for(rg j0;jm;j){rg y0;for(rg k0;km;k)ys[i][k]*x.s[k][j];res.s[i][j]y%k; //有时候将取模放外面会快些}} *thisres;}inline su operator ^(int y){ //矩阵快速幂su res,x*this;for(rg i0;im;i) res.s[i][i]1;while(y){if(y1)res*x;x*x; y1;}return res;}
}ans,xx;int main(){nqr(); mqr(); kqr();scanf(%s,a1);ans.s[0][0]1;for(rg i1;im;i){nx[i]f[i-1][a[i]-0]; //似乎比不严格的好写f[i-1][a[i]-0]i; //f[i][j]表示从这一位在后面加字符j会匹配到哪个位置for(rg j0;j9;j) //复杂度比一般kmp高一点f[i][j]f[nx[i]][j]; //就是严格O(1)的kmp}for(rg i0;im;i)for(rg j0;j9;j)xx.s[i][f[i][j]]; //加入矩阵系数ans*xx^n; int tot0; //矩阵快速幂for(rg i0;im;i)totans.s[0][i]; //统计所有不含所给串的串的个数printf(%d\n,tot%k);return 0;
}8. 洛谷 $ P2414 $ $ NOI~2011 $ 阿狸的打字机 题意概括 给你一棵 $ n $ 个节点的 $ Trie $ 树 $ q $ 次询问 $ Trie $ 树上 $ x $ 节点代表的字符串在 $ y $ 节点代表的字符串中出现了多少次。 $ 1 \le n, q \le 10^6. $ $ solution $ 很难的一道题可以说是很多算法的结合 $ AC $ 自动机 $ fail $ 树 $ dfs $ 序树状数组 首先是读入一般读入肯定超时因为放进 $ AC $ 自动机的字符串很多很长但是他们很多前缀相同。于是根据题意模拟我们在 $ trie $ 数上跑操作序列只要记录每一个节点的父亲就可以支持加入字符后的撤销操作然后打印操作直接在当前 $ trie $ 的节点处打标机即可详细见代码 然后是关于 $ fail $ 树我们对于每一个 $ fail $ 指针件一条反向边因为一个节点只有一个 $ fail $ 指针得到的图一定是棵有根树。然后我们思考这棵树的意义假设每个节点对应一个从根到这个节点的字符串我们在普通情况下从某个节点对应字符串 $ S $ 沿 $ fail $ 指针跑遍历的字符串都是 $ S $ 的子串且是后缀于是反过来我们在 $ fail $ 树上从某个节点对应 $ S $ 遍历其子树遍历到的字符串都一定包含 $ S $ 作为子串且 $ S $ 是它们后缀 然后我们还知道一个子串一定可以表示成母串的前缀的后缀。于是如果我们要在 $ trie $ 上找 $ x $ 节点代表的字符串在 $ y $ 节点代表的字符串中出现了多少次我们只需要将 $ y $ 字符串的每一个前缀对应节点在 $ trie $ 上为到根链都标记然后在 $ fail $ 树上的 $ x $ 好节点开始遍历子树有多少节点被标记那么 $ x $ 节点代表的字符串在 $ y $ 节点代表的字符串中出现了多少次。 但是我们发现询问很多字符串长度很大。但是我们可以离线因为字符串的所有前缀对应节点在 $ trie $ 上为一条到根的链我们马上回忆到一种题型在 $ dfs $ 一棵树时维护节点到根路径的信息在遍历到某一节点时加入节点贡献在离开节点时删掉节点贡献。再联想一下我们需要知道 $ fail $ 的子树信息和我们就可以想到先找到树的 $ dfs $ 序用树状数组维护以 $ dfs $ 序为对应位置的数组然后遍历整棵 $ trie $ 树在遍历到某一节点时给树状数组对应位置加一在离开节点时减一。然后如果遍历 $ trie $ 树时当前节点为询问中的 $ y $ 字符串所有前缀都以标记就到树状数组里找到对应询问 $ x $ 字符串对应位置的子树和。 $ code $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;int tim;
int n,m,tot;
int a[100005];
int tr[100005];
int dfn[100005];
int low[100005];
int ans[100005];struct bian{int to,next;
}b[1000005];
int tou[100005],top;struct lian{int to,res,id,next;
}q[100005];
int hd[100005],len;struct AC{int tt;int fa[100005];int end[100005];int fail[100005];int son[100005][26];bool vis[100005][26];inline void add(const string ch){rg now0,*to,lch.size();for(rg i0;il;i){if(ch[i]ach[i]z){toson[now][ch[i]-a];if(*to) now*to; else *tott,fa[*to]now,now*to;}if(ch[i]B) nowfa[now]; //额外计一个父亲用来撤销if(ch[i]P) a[n]now;}}inline void failed(){queueint q;for(rg i0;i26;i){if(son[0][i]){fail[son[0][i]]0;q.push(son[0][i]);}}rg *to,next;while(!q.empty()){rg iq.front(); q.pop(); nextfail[i];for(rg j0;j26;j){toson[i][j];if(*to){ q.push(*to);fail[*to]son[next][j];}else vis[i][j]1,*toson[next][j];} //因为之后需要遍历原始字典树所以需要一个vis数组记录更改}}inline void get_eg(){for(rg i1;itt;i){ rg xfail[i],yi;b[top]bian{y,tou[x]}; tou[x]top;} //根据fail指针建fail树的边反边}
}ac;inline int qr(){register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}inline void add(int x,int v){for(;xtim;xx-x) tr[x]v;
} //需要注意树状数组的范围inline int ask(int x){ rg res0;for(;x;x-x-x) restr[x];return res;
}inline void yu(int i){dfn[i]tim;for(rg jtou[i];j;jb[j].next) yu(b[j].to);low[i]tim;
} //有向树的dfs序dfn和low记录子树区间inline void dfs(int i){add(dfn[i],1);for(rg jhd[i];j;jq[j].next){q[j].resask(low[q[j].to])-ask(dfn[q[j].to]-1);} //用链式前向星记录询问for(rg j0;j26;j)if(ac.son[i][j]!ac.vis[i][j])dfs(ac.son[i][j]);add(dfn[i],-1);
} //遍历原始字典树是因为每一个子串都是前缀的后缀
//字典树遍历所有前缀而fail树的dfs序与前缀的后缀有关int main(){//freopen(.in,r,stdin);//freopen(.out,w,stdout);string ch; getline(cin,ch); ac.add(ch);ac.failed(); ac.get_eg();yu(0); mqr();for(rg i1;im;i){rg xa[qr()],ya[qr()]; //将询问具体到哪个字符串q[i]lian{x,0,i,hd[y]}; hd[y]i;} dfs(0);for(rg i1;im;i) ans[q[i].id]q[i].res;for(rg i1;im;i) printf(%d\n,ans[i]);return 0;
} 9. 拯救紫萱学姐试题 题意概括 定义对于两个字符串 $ a $ 和 $ b $ 如果 $ a $ 既是 $ b $ 的前缀也是 $ b $ 的后缀那么称 $ a $ 和 $ b $ 相似空字符串和任何字符串相似。一个字符串可以通过编辑变换成一个比它短而且与它相似的字符串付出的代价为这两个字符串的长度之差的平方。两个字符串通过编辑而变为同一个字符串所花费的最小代价被称为最短编辑距离。现给定一个字符串你需要知道这个字符串的每一对前缀的最短编辑距离中的最大值是多少。 $ 1 \le |S| \le 10^6 $ $ solution $ 其实看到 $ a $ 既是 $ b $ 的前缀也是 $ b $ 的后缀时就可以想到 $ kmp $ 思想。然后我们就会发现每一次编辑变换就是沿着 $ kmp $ 的 $ next $ 数组往前跳。然后为了代价最小我们肯定每次只跳一步。于是可以得到一个结论对于两个前缀他们沿 $ next $ 数组向前跳第一个相同的位置所对应的前缀就是最终状态类似于将 $ next $ 数组反向连边在树上跑 $ LCA $ 。于是我们根据 $ next $ 数组从后往前遍历每次用当前位置跟新它 $ next[] $ 对应位置的最大代价同时记录答案。 $ code $ ll ans;
int n;
int f[2000005];
ll s[2000005];
char a[2000005];int main(){scanf(%s,a1); nstrlen(a1); f[1]0;for(rg i2,j0;in;i){ //kmpwhile(ja[i]!a[j1]) jf[j];if(a[i]a[j1]) f[i]j; //next数组}for(rg in;i1;--i){ll jf[i];ll x(ll)(i-j)*(i-j); //记录这一步的代价ansmax(ans,s[i]xs[j]); //更新答案s[j]max(s[j],s[i]x); //更新最大代价}printf(%lld\n,ans);return 0;
} 10. 洛谷 $ P3279 $ $ SCOI~2013 $ 密码 题意概括 给出一个长度为 $ n $ 的数组 $ {p_i} $ 和一个长度为 $ n $ 的数组 $ { q_i } $ 分别表示以字符串中每个字符以及每两个相邻字符的间隙为中心的最长回文串长度。你需要根据给出的 $ { p_i } $ 和 $ {q_i} $ 构造出一个满足条件的字符串 $ S $ 。 $ n \le 10^6 $ $ solution $ 将 $ manacher $ 倒着做一遍从前往后构造字符串。 因为回文串对称性质前面一般直接赋值到后面一半。因为回文串对称性质我们记录一个 $ bool $ 数组回文串的后面第一个字符不能等于回文串前一个字符。然后贪心放小的字符即可。 $ code $ int n;
int a[1000005];
int b[1000005];
int s[1000005];
bool f[1000005][27];int main(){nqr(); rg r1; s[0]26;for(rg i1;in;i)a[i]qr()1; //注意for(rg i1;in;i) b[i]qr()1;for(rg i1;in;i){if(ir){ r; //贪心放最小的for(rg j0;j26;j)if(!f[i][j]){s[i]j; break;}} rg xi-a[i],yia[i]; //记录边界f[y1][s[x-1]]1; //后面第一个字符不能等于回文串前一个字符while(ry) s[r]s[i*2-r],r;xi-b[i]1,yib[i]; //同上f[y1][s[x-1]]1;while(ry) s[r]s[i*2-r1],r;}for(rg i1;in;i)printf(%c,s[i]a);puts();return 0;
} 11. \(LOJ~6187~Odd\) 题意概括 有一个 $ n $ 个数的数组 $ A $ 。求有多少个子区间满足每个区间里出现过的数都只出现了奇数次。 $ n \leq 2 \times 10^5, a_i \leq 10^6 $ $ solution $ 很难调的一道题细节很多小技巧也很多。似乎上一道我这么认为的题也是分块 我们考虑这道题的“奇偶”二字说明本题很可能和状压、位运算什么的有关。考场上以为状压一下、求个前缀异或和、再开个桶就可以解决奈何数据范围大、“出现过”三字太毒瘤但是仔细摸索一番我们不难想到 $ Hash $ 。因为我们要求每个区间所以很直接的想法就是枚举一个端点寻找合法的另一个端点。而要快速知道一个区间内数的奇偶性我们只能依靠异或操作和后缀和通过异或操作使得合法区间一定满足异或和为 $ 0 $ 这样根据右端点后缀异或和就能得到左端点后缀异或和然后查存后缀异或和的桶子就好 为了能够方便异或操作我们给每个值随机一个大数这样正确性会很高总共后缀异或和的数量为 $ n $ 个值域为 $ 2^{63} $ 安全。然后我们枚举右端点 $ r $ 并实时维护后缀显然右端点以右的点的后缀异或和不需要管因为两次异或得0。因为合法区间的异或和为 $ 0 $ 而区间里的数又是奇数次所以我们可以忽略每一个数的最后一个。于是当我们右端点向右移时假设下一个数为 $ v_i $ 那么对于前面所有后缀它肯定是里面等于 $ v $ 的书中最后一个。假设上一个 $ v $ 出现位置为 $ j $ 于是从 $ [1,j] $ 的所有后缀均需要异或 $ v $ $ [j1,i] $ 不需要。然后因为右端点后缀为 $ 0 $ 合法区间异或和为零我们只需要知道前面有多少位置的后缀异或和为 $ 0 $ 即可 然后讲一下实现首先我们需要随机 $ rand $ 大数。然后我们需要记录每一个位置的后缀异或和并支持区间某个前缀区间异或修改以及区间前缀区间查询 $ 0 $ 的出现次数因为值域很大所以我们得考虑 $ Hash $ 表查询对于区间修改查询我们可以线段树但是线段树被卡内存了仅分块还活着然后对于区间异或我们可用类似线段树的 $ lazytag $ 一样给每个块打标记查询这个块时有多少0就是查询有多少 $ 0~xor~lazytag $ 分块操作有点绕要仔细分析 注意 $ Hash $ 表因为分块的缘故需要支持删除和加入我们要链表删除回收空间不能暴力更改空间会爆 $ code $ ll ans;
int n,m;
int a[200005];
ll b[1000005]; //随机化权值
ll s[1000005]; //后缀随着右端点向右移会变化的后缀
int t[1000005]; //上一个出现位置
int f[200005]; //分块struct Hash{int tt,top;ll vv[505]; //数值int da[505]; //数量int to[505]; //链表指向int stc[505]; //我删掉的位置回收栈int hd[2005];inline void add(ll x,int v){rg yx%2003; rg i0; //先Hash一下for(rg jhd[y];j;ij,jto[j]){ //链式前向星存储if(vv[j]x){da[j]v; //更新权值if(!da[j]){stc[top]j; //计入回收栈if(!i) hd[y]to[j]; //链表删除else to[i]to[j];} return ;}}itop?stc[top--]:(tt); //找到一个没用的位置vv[i]x; da[i]1; to[i]hd[y]; hd[y]i; //存储}inline int ask(ll x){for(rg jhd[x%2003];j;jto[j]) //链式前向星访问if(vv[j]x) return da[j];return 0;}
}ha[505];
ll lz[505];int main(){srand(time(NULL)); //随机化nqr(); msqrt(n-1)1; //分块的大小for(rg i1;in;i) f[i](i-1)/m1; //这个下标在哪个块for(rg i1;in;i) a[i]qr(),b[a[i]]rand()((ll)rand()31); //随机权值for(rg i1;in;i){ha[f[i]].add(0,1); //加入初始值if(t[a[i]]){ rg xf[t[a[i]]]; ll vb[a[i]]; //上一个出现的位置该位置的随机权值for(rg j1;jx;j) lz[j]^v; //块上打标记for(rg jm*(x-1)1;jt[a[i]];j)ha[x].add(s[j],-1), s[j]^v, ha[x].add(s[j],1); //先取出后修改再加入} t[a[i]]i; //该位置变为最后一个出现位置for(rg j1;jf[i];j) ansha[j].ask(lz[j]); //询问直接访问大块就可以了}printf(%lld\n,ans);return 0;
} 二、搜索专题 $ hncpc~2019E~Numbers $ 题意概括 给一个数字串 $ S $ 求将其划分成 $ [0,99] z$ 不含前导零且互不相同的数的方案数。 $ solution $ 湖南师范大学的 $ ACM $ 比赛题没有 $ source $ 。反正比较简单直接口糊。 爆搜枚举每个位置是否是小于 $ 10 $ 的位置其他位置的数就确定了。于是边搜索边 $ check $ 就好了 题意概括 $ solution $ $ code $ 三、图论专题 题意概括 $ solution $ $ code $ 四、数据结构专题 题意概括 $ solution $ $ code $ 转载于:https://www.cnblogs.com/812-xiao-wen/p/11600101.html
