题面翻译

· · 题解

CF233B

Two Strings

题目描述

一个长度为 |x| 的字符串 s = s_{1}s_{2}...s_{|s|} 的子序列（其中 |s| 是字符串 s 的长度）是一个字符串 x = s_{k1}s_{k2}...s_{k|x|} （满足 1 \leq k_{1} < k_{2} < ... < k_{|x|} \leq |s| ）。

给定两个字符串 s 和 t 。我们考虑字符串 s 的所有与字符串 t 相同的子序列。是否每个字符串 s 中的字符都至少出现在这些子序列中？换句话说，对于所有的 i （ 1 \leq i \leq |s| ），是否存在字符串 s 的子序列 x = s_{k1}s_{k2}...s_{k|x|} ，使得 x = t 且存在 j （ （ 1 \leq j \leq |x| ），使得 k_{j} = i 。

输入格式

第一行包含字符串 s ，第二行包含字符串 t 。每一行只包含小写英文字母。给定的字符串不为空，每个字符串的长度不超过 2 \times 10^{5} 。

输出格式

如果字符串 s 中的每个字符都至少出现在所描述的子序列中，则输出 "Yes"（不带引号），否则输出 "No"（不带引号）。

样例 #1

样例输入 #1

abab
ab

样例输出 #1

Yes

样例 #2

样例输入 #2

abacaba
aba

样例输出 #2

No

样例 #3

样例输入 #3

abc
ba

样例输出 #3

No

提示

在第一个示例中，字符串 t 可以以三种方式出现在字符串 s 中作为子序列：abab，abab 和 abab。在这些出现中，字符串 s 中的每个字符至少出现一次。

在第二个示例中，字符串 s 的第4个字符在字符串 t 的任何出现中都不存在。

在第三个示例中，字符串 s 中不存在字符串 t 的出现。

CF82D

Two out of Three

题面翻译

一队顾客排在一位收银员前面。他采取这样一个策略：每次，假如队伍有至少两人，就会从前面的前三人（如果有）中选取两位一起收银，所花费的时间为这两人单独收银所需时间的最大值。如果只有两人，那么一起收银；如果只有一人，那么单独收银。请问所需的总时间最少是多少？

题目描述

Vasya最近开发了一个优化顾客流程的新算法，并考虑了以下问题。

假设队列中有 n 个人等待收银员，其中每个人都有一个正整数 a_{i} ，表示与该顾客交互所需的时间。这个收银员的特殊之处在于，他可以同时为两个顾客提供服务。然而，如果两个顾客分别需要 a_{i} 和 a_{j} 时间来完成服务，则同时为他们提供服务所需的时间为 max(a_{i},a_{j}) .请注意，与顾客交互是一个不可中断的过程，因此，如果两个人同时来到收银员面前，意味着他们开始同时被服务，并且会同时完成（可能其中一个人需要等待）。

Vasya在他的算法中使用了一个巧妙的启发式方法——只要队列中有超过一个人在等待，那么就将前排的三个人中的任意两个人同时发送给收银员。如果队列中只有一个顾客编号 i ,则他去收银员那里，并且在 a_{i} 时间内完成服务。请注意，为顾客提供服务的总阶段数将始终等于 ⌈n/2⌉ .

Vasya认为这种方法将有助于应对我们都讨厌的排队等候的问题。这就是为什么他要求你设计一个程序，通过这个算法确定整个队列的最短处理时间。

输入格式

输入文件的第一行包含一个数字 n ( 1<=n<=1000 )，表示序列中的人数。第二行包含以空格分隔的整数 a_{1},a_{2},...,a_{n} ( 1<=a_{i}<=10^{6} ). 人们的编号从收银员开始，直到队列的末尾。

输出格式

第一行输出一个数字——处理所有 n 个人所需的最短时间。然后，在 ⌈n/2⌉ 行上打印顾客的服务顺序。每行（可能除了最后一行）必须包含两个由空格分隔的数字——当前处理阶段将提供服务的顾客编号。如果 n 是奇数，则最后一行必须包含一个数字——队列中最后一个被服务的顾客编号。顾客的编号从1开始

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

6
1 2
3 4

样例 #2

样例输入 #2

5
2 4 3 1 4

样例输出 #2

8
1 3
2 5
4

CF855C

Helga Hufflepuff's Cup

题面翻译

题目描述

给你一棵树，可以有 m 种不同的颜色，定义一种特殊颜色 k，要求整棵树中特殊颜色的数量不超过 x 个。同时，如果一个节点是特殊颜色，那么它相邻节点的颜色编号必须全部小于 k。求满足条件的方案数。

输入格式

第 1 行输入两个正整数 n,m。

接下来的 2 \thicksim n 行，每行输入两个数 u_{i},v_{i}，表示存在一条边连接节点 u_{i} 和节点 v_{i}。

最后一行输入两个正整数 k,x。

说明/提示

$1 \leq k \leq m$，$1 \leq x \leq 10$。 ## 题目描述 Harry, Ron 和 Hermione 发现了 Helga Hufflepuff 的杯子是一枚魂器。通过与 Bellatrix Lestrange 的交战，Hermione 得知这个杯子位于 Gringott's Wizarding Bank 中 Bellatrix 家族的地下金库。 这个巫师银行以一棵树的形式存在，总共有 $n$ 个金库，每个金库都有一种类型，用数字 $1$ 到 $m$ 表示。一棵树是一个无向连通图，没有环。 最高安全级别的金库是类型 $k$，所有类型为 $k$ 的金库都具有最高的安全级别。 最高安全级别的金库最多可以有 $x$ 个。 另外，如果一个金库是最高安全级别，那么它相邻的金库保证不是最高安全级别，并且它们的类型保证小于 $k$。 Harry 想考虑所有可能性，这样他就可以轻松找到到达 Bellatrix 的金库的最佳路径。所以，你需要告诉他，在给定 Gringotts 的树结构下，满足上述条件的每个金库类型的可能方案数。 ## 输入格式 输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$ —— 金库的数量和可能的不同金库类型的数量。 ($1 \leq n \leq 10^{5}$, $1 \leq m \leq 10^{9}$) 接下来的 $n-1$ 行，每行包含两个用空格分隔的整数 $u_{i}$ 和 $v_{i}$ ($1 \leq u_{i},v_{i} \leq n$)，表示第 $i$ 条边，连接着金库 $u_{i}$ 和金库 $v_{i}$。保证给定的图是一棵树。 输入的最后一行包含两个整数 $k$ 和 $x$ ($1 \leq k \leq m$, $1 \leq x \leq 10$)，表示最高安全级别金库的类型和最多可能的最高安全级别金库的数量。 ## 输出格式 输出一个整数，表示满足条件的每个金库类型可能方案的数量，结果对 $10^{9}+7$ 取模。 ## 样例 #1 ### 样例输入 #1 ``` 4 2 1 2 2 3 1 4 1 2 ``` ### 样例输出 #1 ``` 1 ``` ## 样例 #2 ### 样例输入 #2 ``` 3 3 1 2 1 3 2 1 ``` ### 样例输出 #2 ``` 13 ``` ## 样例 #3 ### 样例输入 #3 ``` 3 1 1 2 1 3 1 1 ``` ### 样例输出 #3 ``` 0 ``` ## 提示 在测试用例 $1$ 中，我们不能有任何最高安全级别的金库，因为它的类型是 $1$，意味着它相邻的金库类型必须小于 $1$，这是不允许的。因此，只有一种可能的组合，即所有金库的类型都是 $2$。 # CF847E # Packmen ## 题目翻译 输入一个整数 $n$，然后给出一个长度为 $n$ 的字符串。在字符串中，$\texttt*$ 表示包装，$\texttt{P}$ 表示人，$\texttt.$ 表示空位置。人每移动一格需要花费一秒的时间，人可以向左或向右移动。当人走到包装的位置时，会将该包装吃掉。问最少需要多少秒，人可以吃完所有的包装。 ## 题目描述 游戏场地是一个 $1\times n$ 的方格单元格条。有些单元格中有Packmen，有些单元格中有包装，其他单元格为空。 Packmen可以在 $1$ 个时间单位内移动到相邻的单元格。如果目标单元格中有 $\texttt*$，则Packmen将其吃掉。吃掉 $\texttt*$ 不需要任何时间。 初始时刻，所有的Packmen都开始移动。每个Packmen可以无限次改变移动方向，但不能超出游戏场地的边界。多个Packemen之间的移动互不干扰；一个单元格可以有任意数量的Packemn以任意方向移动。 你的任务是确定在多少秒后，Packmen可以吃掉所有 $\texttt*$ 。 ## 输入格式 第一行包含一个整数 $n$ ($2 \leq n \leq 10^5$) — 游戏场地的长度。 第二行包含游戏场地的描述，由 $n$ 个字符组成。如果第 $i$ 个位置上是字符 $\texttt{.}$，则表示该单元格为空。如果第 $i$ 个位置上是字符 $\texttt{*}$，则表示该单元格中有一个包装。如果第 $i$ 个位置上是字符 $\texttt{P}$，则表示该单元格中有一个Packmen。 保证游戏场地上至少有一个Packmen和一个包装。 ## 输出格式 输出一个整数，表示Packmen吃掉所有包装所需的最少时间。 ## 样例 #1 ### 样例输入 #1 ``` 7 *..P*P* ``` ### 样例输出 #1 ``` 3 ``` ## 样例 #2 ### 样例输入 #2 ``` 10 .**PP.*P.* ``` ### 样例输出 #2 ``` 2 ``` ## 提示 在第一个样例中，位置 $4$ 上的Packmen向左移动，吃掉了位置 $1$ 上的星号。他花费了 $3$ 个时间单位。在同样的 $3$ 个时间单位内，位置 $6$ 上的Packmen吃掉了它两个相邻的星号。例如，它可以向左移动并吃掉位置 $5$ 上的星号（花费 $1$ 个时间单位），然后从位置 $5$ 向右移动并吃掉位置 $7$ 上的星号（花费 $2$ 个时间单位）。因此，在 $3$ 个时间单位内，Packmen可以吃掉游戏场地上的所有星号。 在第二个样例中，位置 $4$ 上的Packmen向左移动，并在 $2$ 个时间单位后吃掉了位置 $3$ 和 $2$ 上的星号。位置 $5$ 和 $8$ 上的Packmen向右移动，并在 $2$ 个时间单位后分别吃掉了位置 $7$ 和 $10$ 上的星号。因此，$2$ 个时间单位足以让Packmen吃掉游戏场地上的所有星号。 # CF379D # New Year Letter ## 题目描述 许多国家都有这样一个新年或圣诞节的传统，即给圣诞老人写信并列出希望得到的礼物清单。Vasya是一个普通的程序员男孩。和其他普通男孩一样，他打算在除夕夜给圣诞老人写信（我们俄罗斯人实际上期待的是新年的圣诞老人，而不是圣诞节的圣诞老人）。 Vasya想出了一个写信的算法。首先，他选择两个字符串$s_1$和$s_2$，这两个字符串由大写英文字母组成。然后，这个男孩使用递归方程$s_n=s_{n-2}+s_{n-1}$生成字符串$s_k$，其中"+"表示字符串按给定顺序连接。然后，Vasya将字符串$s_k$写在一张纸上，放入信封中，然后寄给圣诞老人。 Vasya非常确定，如果字符串$s_k$中恰好包含$x$个子串"AC"，那么圣诞老人就会送给他最好的礼物（这里指的是AC++）。 除此之外，Vasya只确定了$s_1$的长度为$n$，$s_2$的长度为$m$，其他的还没有确定。 现在，Vasya有了一项紧急的新年任务，他希望你能帮他选择合适的$s_1$和$s_2$来实现他的愿望。请帮助他。 ## 输入格式 第一行输入四个整数$k, x, n, m$，满足$3 \le k \le 50, 0 \le x \le 10^9, 1 \le n, m \le 100$。 ## 输出格式 输出两行，第一行是长度为$n$的字符串$s_1$，第二行是长度为$m$的字符串$s_2$。如果不存在满足条件的字符串，输出"Happy new year!"。 ## 样例 #1 ### 样例输入 #1 ``` 3 2 2 2 ``` ### 样例输出 #1 ``` AC AC ``` ## 样例 #2 ### 样例输入 #2 ``` 3 3 2 2 ``` ### 样例输出 #2 ``` Happy new year! ``` ## 样例 #3 ### 样例输入 #3 ``` 3 0 2 2 ``` ### 样例输出 #3 ``` AA AA ``` ## 样例 #4 ### 样例输入 #4 ``` 4 3 2 1 ``` ### 样例输出 #4 ``` Happy new year! ``` ## 样例 #5 ### 样例输入 #5 ``` 4 2 2 1 ``` ### 样例输出 #5 ``` Happy new year! ``` # CF427D # Mactch & Catch ## 题目翻译 给定两个字符串，求最短的满足各只出现一次的连续公共子串。 ## 题目描述 警察总部正在不同频率级别上监控信号。他们从两个不同频率的信号中得到了两个可疑的编码字符串$s_1$和$s_2$。怀疑这两个字符串分别来自两个不同的罪犯，并且他们正计划进行一些邪恶的行动。 现在他们试图在这两个字符串之间找到一个最短的公共子串。这个子串必须在第一个字符串中只出现一次，在第二个字符串中也只出现一次。 给定两个字符串$s_1$和$s_2$，由小写拉丁字母组成，请找到$s_1$和$s_2$的最小（按长度）的公共唯一子串$p$，其中$p$在$s_1$中是唯一的子串，在$s_2$中也是唯一的子串。有关子串和唯一性的形式定义，请参见注释。 ## 输入格式 输入的第一行包含$s_1$，第二行包含$s_2$ $(1\leq |s_1|,|s_2|\leq 5000)$。两个字符串都由小写拉丁字母组成。 ## 输出格式 输出$s_1$和$s_2$的最小公共唯一子串的长度。如果$s_1$和$s_2$没有公共唯一子串，则输出-1。 ## 样例 #1 ### 样例输入 #1 ``` apple pepperoni ``` ### 样例输出 #1 ``` 2 ``` ## 样例 #2 ### 样例输入 #2 ``` lover driver ``` ### 样例输出 #2 ``` 1 ``` ## 样例 #3 ### 样例输入 #3 ``` bidhan roy ``` ### 样例输出 #3 ``` -1 ``` ## 样例 #4 ### 样例输入 #4 ``` testsetses teeptes ``` ### 样例输出 #4 ``` 3 ``` ## 提示 假设我们有字符串$a=a_1a_2a_3...a_{|a|}$，其中$|a|$是字符串$a$的长度，$a_i$是字符串中的第$i$个字母。 我们将称字符串$a_{l}a_{l+1}a_{l+2}...a_{r}$ $(1\leq l\leq r\leq |a|)$为字符串$a$的子串$[l,r]$。 当且仅当没有一对$l_1,r_1$满足$l_1\neq l$且子串$[l_1,r_1]$与字符串$a$中的子串$[l,r]$相等时，子串$[l,r]$在字符串$a$中是唯一的。 # CF222E # Decoding Genome ## 题目描述 最近，一项火星的秘密任务已经展开。作为结果，科学家们获得了一些关于火星DNA的信息。现在我们知道，任何一个火星DNA最多包含 $ m $ 种不同的核苷酸，编号从 $ 1 $ 到 $ m 。火星DNA的特殊特征阻止了一些核苷酸对在该链中连续出现。例如，如果核苷酸1和核苷酸2不能连续出现在火星DNA中，那么核苷酸链 \[ 1, 2 \] 不是一个有效的火星DNA链，但是核苷酸链 \[ 2, 1 \] 可以是一个有效的链（如果没有对应的限制）。不能在DNA链中连续出现的核苷酸对的数量是 k $。 基因研究的需求需要了解火星DNA的正确长度为$ n $的链的数量。你的任务是编写一个程序来计算这个值。 ## 输入格式 第一行包含三个用空格分隔的整数 $ n,m,k $ ( $ 1<=n<=10^{15} $ , $ 1<=m<=52 $ , $ 0<=k<=m^{2} $ ). 接下来的 $ k $ 行，每行包含两个字符，没有空格，表示一个禁止的核苷酸对。第一个字符表示禁止对中的第一个核苷酸，第二个字符表示第二个核苷酸。 具有编号从1到26的核苷酸由英文字母"a"到"z"表示（1是"a"，2是"b"，...，26是"z"）。具有编号从27到52的核苷酸由英文字母"A"到"Z"表示（27是"A"，28是"B"，...，52是"Z"）。 保证每个禁止对最多在输入中出现一次。保证所有禁止对中的核苷酸编号都不会超过$ m $。请注意核苷酸对中的顺序是重要的。 请不要在C++中使用%lld来读取或写入64位整数。最好使用cin，cout流或%I64d指定符。 ## 输出格式 输出一个整数，即所求的数量对$ 1000000007 $（$ 10^9+7 $）取模后的值。 ## 数据范围 $1 \leq n \leq 10^{15} 1 \leq m \leq 52 0 \leq k \leq m^2

样例 #1

样例输入 #1

3 3 2
ab
ba

样例输出 #1

17

样例 #2

样例输入 #2

3 3 0

样例输出 #2

27

样例 #3

样例输入 #3

2 1 1
aa

样例输出 #3

0

提示

在第二个测试用例中，允许所有可能的三核苷酸DNA。每个核苷酸可以取三个值中的一个，因此总共有27种不同的三核苷酸DNA。

在第三个测试样例中，我们不能构建任何两个核苷酸的DNA - 唯一可能的核苷酸"a"不能连续出现两次。

ARC178D

Delete Range Mex

题目描述

给定正整数 N 和长度为 M 的非负整数序列 A=(A_{1},A_{2},\dots,\ A_{M}) 。

其中， A 的所有元素均为介于 0 到 N 之间的整数，并且各不相同。

请计算满足以下条件的排列 P 的数量对 998244353 取余后的结果：

## 输入格式 从标准输入中以以下格式给出输入： > $ N $ $ M $ $ A_{1} $ $ A_{2} $ $ \cdots $ $ A_{M}

输出格式

请输出答案。

样例 #1

样例输入 #1

4 2
1 3

样例输出 #1

8

样例 #2

样例输入 #2

4 4
0 3 2 1

样例输出 #2

1

样例 #3

样例输入 #3

16 7
9 2 4 0 1 6 7

样例输出 #3

3520

样例 #4

样例输入 #4

92 4
1 67 16 7

样例输出 #4

726870122

提示

限制条件

样例解释 1

通过将 B\ =\ (2,\ 1,\ 0,\ 3) 初始化，可以通过以下步骤使 B=A ：

样例解释 2

只有当 P\ =\ (0,\ 3,\ 2,\ 1) 时才满足条件。

样例解释 4

请将结果对 998244353 取余。