Description

题目链接:Codeforces 633C

Yash 研究出了一种新的密码技术。对于给定的句子,密码通过以下方法生成:

  1. 将所有字母都变成小写。
  2. 将每个单词分别反转。
  3. 将句子里的空格全部删除。

现在 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$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1028C

在平面中给你 $n$ 个矩形,我们用左上角 $(x_1, y_1)$ 和右下角 $(x_2, y_2)$ 坐标描述一个矩形,保证其中存在 $n - 1$ 个矩形使得他们有公共点。如果一个点严格属于矩形内部或在它的边界上,那么认为这个点属于这个矩形。你需要找到一个整数坐标,使得它属于至少 $n - 1$ 个矩形。

数据范围:$2 \le n \le 132674$,$-10 ^ 9 \le x_1 < x_2 \le 10 ^ 9$,$-10 ^ 9 \le y_1 < y_2 \le 10 ^ 9$。

- 阅读剩余部分 -

Description

题目链接: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$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 700E

Bomboslav 成立了一个品牌代理商,正在帮助公司创建商标和广告。就这个问题而言,公司的广告应该是其名称的非空子串。

有时,公司会对品牌进行重塑并改变广告。如果广告 $B$ 作为子串在广告 $A$ 中出现至少 $2$ 次(允许重叠),那么认为广告 $A$ 比 $B$ 更酷。

你得到了某个公司的名字 $w$,你的任务是帮助 Bomboslav 确定最长的广告序列 $s_1, s_2, \dots, s_k$ 满足任何一个广告都比上一个更酷。

数据范围:$1 \le \lvert w \rvert \le 2 \times 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1150D

在中东考古研究期间,你发现了三种古代宗教的遗迹:第一宗教、第二宗教和第三宗教。你收集到了每一种宗教的演变信息,你现在想知道三种宗教是否可以和平共处。

宇宙之词是一个长度为 $n$ 的只包含小写字母的单词。在任何时候,每一种宗教都可以用一个由小写字母组成的单词来描述。

如果描述这三种宗教的单词是宇宙之词的不相交子序列,那么他们的信徒就可以和平共处。形式化地,我们能够对宇宙之词的若干位置给定一个标号 $1, 2, 3$,那么标号为 $i$ 的位置构成的单词就是第 $i$ 种宗教的描述。

然而,宗教是在不断发展的。最初,每个宗教的描述都是空的;在发展过程中,宗教进行了 $q$ 次变化。每次变化中,要么将一个字符附加到某个宗教的描述的末尾,要么从某个宗教的描述的末尾删除一个字符。每次变化后,你都需要判断宗教是否可以和平共处。

数据范围:$1 \le n \le 10 ^ 5$,$1 \le q \le 1000$,$\lvert \text{宗教的描述} \rvert \le 250$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1152D

Neko 把所有长度为 $2n$ 的合法括号序列插入到一棵 $\text{Trie}$ 树中,接着 Aki 向他提出了一个有趣的问题:在这个 $\text{Trie}$ 树中的最大匹配(找到最大的一组边,使得没有两条边具有公共顶点)的大小是多少?答案对 $10 ^ 9 + 7$ 取模。

数据范围:$1 \le n \le 1000$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1153F

你有一条长度为 $l$ 的线段,我们通过随机选择 $2$ 点,在这条线端上随机选择 $n$ 条线段。这 $2n$ 个点将线段分成了 $2n + 1$ 个区间。你需要对于给定的 $k$,求出被这 $n$ 个随机线段中至少 $k$ 个覆盖的区间的期望总长度。答案对 $998244353$ 取模。

数据范围:$1 \le k \le n \le 2000$,$1 \le l \le 10 ^ 9$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1153E

这是一道交互题。

Serval 在上学的途中,必须穿过一个池塘,池塘里面有一条危险的蛇。池塘可以用一张 $n \times n$ 的网格表示。蛇的头部和尾部在不同的格子里,它的身体是一串连接头部和尾部的格子,并且身体不会相交。Serval 碰到蛇就会有生命危险。

幸运的是,他有一个特殊的装置可以回答如下问题:你可以选择一个矩形,它会告诉你蛇身穿过矩形边界的次数。

你作为 Serval 的好朋友,请你在使用不超过 $2019$ 询问后帮 Serval 找到蛇头和蛇尾。注意:蛇不会随着询问而移动。

数据范围:$2 \le n \le 1000$。

- 阅读剩余部分 -