2019年5月

Description

题目链接:Codeforces 1156F

你有一个装有 $n$ 张卡片的袋子,第 $i$ 张卡片上的数字为 $a_i$。

接下来你要玩一个卡片游戏。每一回合,你会随机选择选择袋子里的一张卡片(所有留在袋子里的卡片都是等概率选择的)。从第二回合起,每当你拿出一张卡片(将上面的数字记为 $x$),你都会和上一回合的卡片(将上面的数字记为 $y$)比较:

  • 如果 $x < y$,你将会输掉游戏,游戏结束。
  • 如果 $x = y$,你将会赢得游戏,游戏结束。
  • 如果 $x > y$,游戏继续。

如果袋子里没有卡片了,那么你也将输掉游戏。注意:你取出来的卡片不会重新放回袋子里。

请你求出赢得游戏的概率,答案对 $998244353$ 取模。

数据范围:$2 \le n \le 5000$,$1 \le a_i \le n$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1156D

你有一棵由 $n$ 个节点组成的树,每条边上有一个数字 $0$ 或 $1$。

假如我们从节点 $x$ 开始沿着简单路径到达节点 $y$,一旦经过了数字为 $1$ 的边就不会经过数字为 $0$ 的边。那么我们称二元组 $(x, y$($x \ne y$)是合法的。

你的任务是找出树上合法的二元组数量。

数据范围:$2 \le n \le 2 \times 10 ^ 5$。

- 阅读剩余部分 -

Description

题目链接:Codeforces 1156C

在一条数轴上有 $n$ 个点 $x_1, x_2, \dots, x_n$,两个点 $i, j$ 可以匹配当且仅当两者都满足:

  • 两个点 $i, j$ 都没有和别的点匹配。
  • $\lvert x_i - x_j \rvert \ge z​$。

请求出最多可以匹配多少对点。

数据范围:$2 \le n \le 2 \times 10 ^ 5​$,$1 \le x_i, z \le 10 ^ 9​$

- 阅读剩余部分 -

Description

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

- 阅读剩余部分 -

Description

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

- 阅读剩余部分 -

Description

题目链接:Codeforces 1152E

现在 Neko 有一个长度为 $n$ 的数组 $a$ 和一个长度为 $n - 1$ 的排列 $p$。现在他进行如下操作:

  • 构造一个长度为 $n - 1$ 的数组 $b$,其中 $b_i = \min(a_i, a_{i +1})$。
  • 构造一个长度为 $n - 1$ 的数组 $c$,其中 $c_i = \max(a_i, a_{i +1})$。
  • 构造一个长度为 $n - 1$ 的数组 $b'$,其中 $b'_i = b_{p_i}$。
  • 构造一个长度为 $n - 1$ 的数组 $b'$,其中 $c'_i = c_{p_i}$。

然而 Neko 只记得数组 $b'$ 和 $c'$ 了,将原来的数组 $a$ 和排列 $p$ 都忘记了。他想让你帮他找到任何一个合法的数组 $a$。如果没有任何一个可能的数组,那么输出 -1

数据范围:$2 \le n \le 10 ^ 5$,$1 \le b'_i, c'_i \le 10 ^ 9$。

- 阅读剩余部分 -

Description

题目链接: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$,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

  1. 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
  2. 在一个拆分中,允许出现 $\text{A}=\text{B}​$。例如 $\texttt{cccc}​$ 存在拆分 $\text{A}=\text{B}=\texttt{c}​$。
  3. 字符串本身也是它的一个子串。

本题有 $T​$ 组数据。

数据范围:$1 \le T \le 10$,$1 \le n \le 3 \times 10 ^ 4$。

- 阅读剩余部分 -

Description

题目链接:LOJ 2000

Doris 刚刚学习了 $\text{Fibnacci}$ 数列,用 $f[i]$ 表示数列的第 $i$ 项,那么:

$$ \begin{align*} f[0] &= 0 \\ f[1] &= 1 \\ f[n] &= f[n - 1] + f[n - 2], n \ge 2 \end{align*} $$

Doris 用老师的超级计算机生成了一个 $n \times m$ 的表格,第 $ i $ 行第 $ j $ 列的格子中的数是 $f[\gcd(i, j)]$,其中 $\gcd(i, j)$ 表示 $i$ 与 $j$ 的最大公约数。

Doris 的表格中共有 $ n \times m $ 个数,她想知道这些数的乘积是多少。

这些数的乘积实在是太大了,所以 Doris 只想知道乘积对 $10 ^ 9 + 7$ 取模后的结果。

本题有 $T$ 组数组。

数据范围:$1 \le T \le 1000$,$1 \le n, m \le 10 ^ 6$。

- 阅读剩余部分 -