标签 数据结构 下的文章
- 首页
- 数据结构
「2019 Multi-University Training Contest 2」Longest Subarray
题目链接:HDU 6602
你有一个长度为 $n$ 的序列 $a$ 和两个整数 $C, K$ 满足序列中的所有元素 $1 \le a_{i} \le C$。
我们定义一个连续子序列 $a_{l}, a_{l + 1}, \dots, a_{r}$ 是「好的」当且仅当:
$$ \forall x \in [1, C], \sum_{i = l} ^ {r} [a_{i} = x] = 0\ \text{或}\ \sum_{i = l} ^ {r} [a_{i} = x] \ge K $$
抽象地,如果一个数字在子序列中出现过,那么它的出现次数必须不少于 $K$ 次。
他需要求出「好的」连续子序列的最长长度。
本题有多组数据。
数据范围:$1 \le n, C, K \le 10 ^ 5$,$1 \le a_{i} \le C$,$1 \le \sum n, \sum C, \sum K \le 5 \times 10 ^ 5$。
「2019 Multi-University Training Contest 1」Typewriter
题目链接:HDU 6583
有一天,Jerry 发现了一个奇怪的打字机。这个打字机又 $2$ 种模式:第一种模式可以花费 $p$ 的代价在最后插入一个任意字符;第二种模式可以花费 $q$ 的代价复制任意一个子串并插在最后。
现在 Jerry 想要给 Tom 写一封信,这封信可以用一个只包含小写字母的字符串 $S$ 表示。可惜 Jerry 很穷所以他想知道写这封信的最小花费。
本题由多组数据。
数据范围:$1 \le \lvert S \rvert \le 2 \times 10 ^ {5}$,$\sum \lvert S \rvert \le 5 \times 10 ^ {6}$。
「CTSC 2012」熟悉的文章
题目链接:Luogu 4022
阿米巴是小强的好朋友。
在小强眼中,阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛,小强向阿米巴求教。阿米巴给小强展示了几篇作文,小强觉得这些文章怎么看怎么觉得熟悉,仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光,却发现阿米巴露出了一个狡黠的微笑。
为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得眼熟,小强想出了一个评定作文「熟悉程度」的量化指标:$L_0$。小强首先将作文转化成一个 $01$ 串。之后,小强搜集了各路名家的文章,同样分别转化成 $01$ 串后,整理出一个包含了 $m$ 个 $01$ 串的标准作文库。
小强认为:如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过(即它是标准作文库 的某个串的一个连续子串),那么它是「熟悉」的。对于一篇作文 $A$,如果能够把 $A$ 分割成若干段子串,其中「熟悉」的子串的长度总和不少于 $A$ 总长度的 $90\%$,那么称 $A$ 是「熟悉的文章」。$L_0$ 是能够让 $A$ 成为「熟悉的文章」的所有 $L$ 的最大值。如果不存在这样的 $L$,那么规定 $L_0 = 0$。
现在小强有 $n$ 篇作文需要进行判断,请你分别求出他们的 $L_0$ 值。
数据范围:输入文件的长度不超过 $1.1 \times 10 ^ 6$ 字节。
「NOI 2015」品酒大会
题目链接:UOJ 131
一年一度的「幻影阁夏日品酒大会」隆重开幕了。大会包含品尝和趣味挑战两个环节,分别向优胜者颁发「首席品酒家」和「首席猎手」两个奖项,吸引了众多品酒师参加。
在大会的晚餐上,调酒师 Rainbow 调制了 $n$ 杯鸡尾酒。这 $n$ 杯鸡尾酒排成一行,其中第 $i$ 杯酒 ($1 \le i \le n$) 被贴上了一个标签 $s_i$,每个标签都是 $26$ 个小写英文字母之一。设 $\text{Str}(l, r)$ 表示第 $l$ 杯酒到第 $r$ 杯酒的 $r − l + 1$ 个标签顺次连接构成的字符串。若 $\text{Str}(p, p_0) = \text{Str}(q, q_0)$,其中 $1 \le p \le p_0 \le n$,$1 \le q \le q_0 \le n$,$p \ne q$,$p_0 − p + 1 = q_0 − q + 1 = r$,则称第 $p$ 杯酒与第 $q$ 杯酒是「$r$ 相似」的。当然两杯「$r$ 相似」($r > 1$)的酒同时也是「$1$ 相似」、「$2$ 相似」、$\dots$、「$(r − 1)$ 相似」的。特别地,对于任意的 $1 \le p, q \le n$,$p \ne q$,第 $p$ 杯酒和第 $q$ 杯酒都是「$0$ 相似」的。
在品尝环节上,品酒师 Freda 轻松地评定了每一杯酒的美味度,凭借其专业的水准和经验成功夺取了「首席品酒家」的称号,其中第 $i$ 杯酒 ($1 \le i \le n$) 的美味度为 $a_i$。现在 Rainbow 公布了挑战环节的问题:本次大会调制的鸡尾酒有一个特点,如果把第 $p$ 杯酒与第 $q$ 杯酒调兑在一起,将得到一杯美味度为 $a_p \cdot a_q$ 的酒。现在请各位品酒师分别对于 $r = 0, 1, 2, \dots, n − 1$,统计出有多少种方法可以选出两杯「$r$ 相似」的酒,并回答选择两杯「$r$ 相似」的酒调兑可以得到的美味度的最大值。
数据范围:$1 \le n \le 3 \times 10 ^ 5$,$\lvert a_i \rvert \le 10 ^ 9$。
「NOI 2016」优秀的拆分
题目链接:UOJ 219
如果一个字符串可以被拆分为 $\text{AABB}$ 的形式,其中 $\text{A}$ 和 $\text{B}$ 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。
例如,对于字符串 $ \texttt{aabaabaa} $ ,如果令 $\text{A}=\texttt{aab}$,$\text{B}=\texttt{a}$,我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。
一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。
比如我们令 $\text{A}=\texttt{a}$,$\text{B}=\texttt{baa}$,也可以用 $\text{AABB}$ 表示出上述字符串;但是,字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。
现在给出一个长度为 $n$ 的字符串 $S$,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意:
- 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
- 在一个拆分中,允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。
- 字符串本身也是它的一个子串。
本题有 $T$ 组数据。
数据范围:$1 \le T \le 10$,$1 \le n \le 3 \times 10 ^ 4$。
「NOI 2018」你的名字
题目链接:UOJ 395
小 A 被选为了 ION2018 的出题人,他精心准备了一道质量十分高的题目,且已经把除了题目命名以外的工作都做好了。
由于 ION 已经举办了很多届,所以在题目命名上也是有规定的,ION 命题手册规定:每年由命题委员会规定一个小写字母字符串,我们称之为那一年的命名串,要求每道题的名字必须是那一年的命名串的一个非空连续子串,且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因,小 A 不知道 ION2017 每道题的名字,但是他通过一些特殊手段得到了 ION2017 的命名串,现在小 A 有 $Q$ 次询问:每次给定 ION2017 的命名串 $S$ 和 ION2018 的命名串 $T$,求有几种题目的命名,使得这个名字一定满足命题委员会的规定,即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。
由于一些特殊原因,所有询问给出的 ION2017 的命名串都是某个串的连续子串 $S[l \dots r]$。
数据范围:$1 \le \lvert S \rvert \le 5 \times 10 ^ 5$,$1 \le Q \le 10 ^ 5$,$\sum \lvert T \rvert \le 10 ^ 6$,$1 \le l \le r \le \lvert S \rvert$。
「Codeforces 633C」Spy Syndrome 2
题目链接:Codeforces 633C
Yash 研究出了一种新的密码技术。对于给定的句子,密码通过以下方法生成:
- 将所有字母都变成小写。
- 将每个单词分别反转。
- 将句子里的空格全部删除。
现在 Yash 给你一个长度为 $n$ 的加密后的句子 $S$ 和一个长度为 $m$ 的单词列表 $w_i$。请你帮助他找出任何一种可能的原始句子,使得句子里的单词都来自于单词列表。注意:任何给定的单词都可以多次使用。
数据范围:$1 \le \lvert S \rvert \le 10 ^ 4$,$1 \le m \le 10 ^ 5$,$1 \le \lvert w_i \rvert \le 10 ^ 3$,$\sum \lvert w_i \rvert \le 10 ^ 6$。
「SDOI 2016」生成魔咒
题目链接:LOJ 2033
魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 $1$、$2$ 拼凑起来形成一个魔咒串 $[1, 2]$。
一个魔咒串 $S$ 的非空子串被称为魔咒串 $S$ 的生成魔咒。
例如 $S = [1, 2, 1]$ 时,它的生成魔咒有 $[1]$、$[2]$、$[1, 2]$、$[2, 1]$、$[1, 2, 1]$ 五种。$S = [1, 1, 1]$ 时,它的生成魔咒有 $[1]$、$[1, 1]$、$[1, 1, 1]$ 三种。
最初 $S$ 为空串。共进行 $n$ 次操作,每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 $S$ 共有多少种生成魔咒。
数据范围:$1 \le n \le 10 ^ 5$,$1 \le \Sigma \le 10 ^ 9$。