2019年4月

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

- 阅读剩余部分 -

Description

题目链接:Codeforces 1153D

Serval 在一棵有根树上玩数字游戏。这棵有根树有 $n$ 个节点,节点 $1$ 是根节点,节点 $i$ 的父亲节点用 $f_i$ 表示。所有非叶子节点上有一个操作 $\max$ 或 $\min$,这意味着这个节点上的值为其所有儿子节点的最大值或最小值。

假设这棵树上有 $k$ 个叶子节点,Serval 会把 $1, 2, \dots, k$ 写在这 $k$ 个节点上(每个数字恰好使用 $1$ 次),并且他想要最大化根节点的值。作为他的好朋友,请你帮他求出根节点的最大值。

数据范围:$2 \le n \le 3 \times 10 ^ 5​$,$1 \le f_i \le i - 1​$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1138E

在国家 $N$ 中,有 $n$ 个城市通过 $m$ 条单向道路连接。尽管这个国家看起来并不是那么引人注目,但是这里有两件很有意思的事情。首先,这里的一周有 $d$ 天;另外,每个城市恰好有一个博物馆。

旅行社的员工知道每个博物馆的开放日期,他们正在为游客们制定一项新的旅游计划。旅游从标号为 $1$ 的首都城市出发,并且旅游的第一天必须在某一周的第一天。每天白天,如果当前城市的博物馆开放,那么游客可以进入博物馆参观;否则什么都做不了。晚上,游客要么结束旅游,要么通过道路前往下一个城市。注意,旅游过程中允许重复经过同一个城市。

你需要为旅游制定一条路线,使得在旅游期间参观的不同博物馆数量最多。

数据范围:$1 \le n \le 10 ^ 5$,$0 \le m \le 10 ^ 5$,$1 \le d \le 50$。

- 阅读剩余部分 -

Description

题目链接:LOJ 10059

有一个字符串 $S$。Farmer John 希望在 $S$ 中删掉 $n$ 个屏蔽词(一个屏蔽词可能出现多次),这些词记为 $t_1 \sim t_n$。

FJ 在 $S$ 中从头开始寻找屏蔽词,一旦找到一个屏蔽词,FJ 就删除它,然后又从头开始寻找(而不是接着往下找)。FJ 会重复这一过程,直到 $S$ 中没有屏蔽词为止。注意删除一个单词后可能会导致 $S$ 中出现另一个屏蔽词。这 $n$ 个屏蔽词不会出现一个单词是另一个单词子串的情况,这意味着每个屏蔽词在 $S$ 中出现的开始位置是互不相同的,请帮助 FJ 完成这些操作并输出最后的 $S$。

数据范围:$1 \le \lvert S \rvert, \sum\lvert t_i \rvert \le 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1151E

Kremland 的王国是有 $n$ 个节点的树,第 $i$ 个节点有权值 $a_i$,对于所有的 $1 \le i < n$ 都有一条连接节点 $i$ 和 $i + 1$ 的边。

对于整数 $l, r(l \le r)$,我们设函数 $f(l, r)$ 表示:

  • 我们将权值在区间 $[l, r]$ 内的点保留。
  • 函数的值为新图中连通块的数量。

你需要求出如下式子的值:

$$ \sum_{l = 1} ^ n \sum_{r = l} ^ n f(l, r) $$

数据范围:$1 \le n \le 10 ^ 5$,$1 \le a_i \le n$。

- 阅读剩余部分 -

Description

题目链接:LOJ 2095

我们知道,从区间 $[L, H]$($L$ 和 $H$ 为整数)中选取 $N$ 个整数,总共有 $(H - L + 1) ^ N$ 种方案。小 Z 很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的 $N$ 个整数都求一次最大公约数,以便进一步研究。然而他很快发现工作量太大了,于是向你寻求帮助。你的任务很简单,小 Z 会告诉你一个整数 $K$,你需要回答他最大公约数刚好为 $K$ 的选取方案有多少个。由于方案数较大,你只需要输出其除以 $10 ^ 9 + 7$ 的余数即可。

数据范围:$1 \le N, K \le 10 ^ 9​$,$1 \le L \le H \le 10 ^ 9​$,$H - L \le 10 ^ 5​$。

- 阅读剩余部分 -