Codeforces 1240D: Stack Exterminable Arrays 题解

主要思路

刚开始看到分治的标签就下定决心用分治做,没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。

首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案,那么我们往左的时候可以合并之,并设置\(nxt[i]\)来进行跳跃;由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG,所以我们可以使用类似 AC 自动机的方式用 Map 合并信息:交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。

继续阅读Codeforces 1240D: Stack Exterminable Arrays 题解

P3346:[ZJOI2015]诸神眷顾的幻想乡 – 题解

主要思路

这算是广义后缀自动机的一个通用(general)运用。我们可以像统计多个串一样来做这个,只不过我们需要在树上 DFS 时记录分岔点的 SAM 节点,然后进行回溯。剩下计算本质不同字串个数的方法就很套路了。

继续阅读P3346:[ZJOI2015]诸神眷顾的幻想乡 – 题解

后缀自动机 | SAM

概述

后缀自动机是处理字符串信息的有力工具。后缀自动机存储在 Trie 树上,配合 Link 指针就可以被认为是一张 DAG。任意一条从原点出发的路径都可以被认为是这个字符串的一个子串,且在后缀自动机上不会存在重复的子串信息(然而,我们可以进行一些扩展来维护子串位置信息)。

继续阅读后缀自动机 | SAM

[Fortuna OJ]Jul 8th – Group B 解题报告

今天这几题咋就那么毒瘤呢?

A – String

其实这道题考场上应该能做出来的,是一道很简单的计数问题。在考场上一看到字符串就懵了,不知道为什么我对字符串的字典序有阴影,现在看来就是一道傻逼题。

考虑这样计数:

  1. 枚举一个\(i\),考虑前\(i-1\)个字符与\(T\)串相同,然后第\(i\)个字符小于\(T[i]\),这样可以保证后面怎么放置字母都能满足要求。
  2. 在枚举了\(i\)的情况下,枚举字符\(ch\),范围在\([a, T[i])\),考虑以下两种情况对答案的贡献:
    1. 如果\(ch = S[i]\),那么后面需要变动的字符个数为\(k\)个,对答案的贡献:\[ {n – i \choose k} 25^{k} \]
    2. 如果不等于,那么后面需要变动的字符个数为\(k-1\)个,因为本位占了一个;对答案的贡献:\[ {n – i \choose k – 1} 25^{k – 1} \]
  3. 贡献之后,如果本位\(T[i] \neq S[i]\),那么把\(k–\),代表多固定了一个不同的字符。

继续阅读[Fortuna OJ]Jul 8th – Group B 解题报告

Codeforces Round #539 (Div. 2) 解题报告 (CF1113)

C – Sasha and a Bit of Relax

其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\),然而这个运算可以直接移项:因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数,我们只需要在 Trie 树末端维护奇偶计数即可。

继续阅读Codeforces Round #539 (Div. 2) 解题报告 (CF1113)