0727 第 15 场 小白入门赛/强者挑战赛

• 小白入门赛：https://www.lanqiao.cn/oj-contest/newbie-15/
• 强者挑战赛：https://www.lanqiao.cn/oj-contest/senior-15/
• 题解回放：https://www.bilibili.com/video/BV1vy411i7aG/

T1. 唐僧玩梗【算法赛】

问题描述

“收徒，收坐骑，不收十二生肖以外的动物”。当唐僧穿越到现代，竟也玩起了网络游戏中的梗。

悟空、八戒、沙僧、小白龙听闻后，误将此当作师傅新立的规矩，于是纷纷开始查验自身是否属于十二生肖中的动物。若属于，则继续追随师傅；否则，便主动退出师门。

现在，请你输出一个整数，表示唐僧剩余徒弟和坐骑的总数。

输入格式

无。

输出格式

输出一个整数，表示答案。

T2. 大闹蟠桃园【算法赛】

问题描述

王母娘娘举办蟠桃会，却未邀请孙悟空。这使得孙悟空怒不可遏，他当即决定大闹蟠桃园，要将蟠桃据为己有。

在蟠桃园中，有 $N$ 条小路，编号从 $1$ 到 $N$。这些小路构成了一个环形网络，具体来说，小路 $i$ 与小路 $i + 1$（$i < n$） 相互连接，小路 $N$ 与小路 $1$ 相互连接。每条小路都可能有天兵把守。

为了加快采摘蟠桃的速度，孙悟空施展法术，变出了 $N$ 个分身，编号从 $1$ 到 $N$。每个分身起初皆立于其对应编号的小路上，且所采摘的蟠桃数量均为 $0$。每当孙悟空的本体挥动一次金箍棒，所有的分身就都会向右移动到下一条小路，并出现以下情况之一：

• 如果一个分身走入有天兵把守的小路，它采摘的蟠桃数量将变为 $0$。
• 如果一个分身走入没有天兵把守的小路，它采摘的的蟠桃数量将增加 $1$。

孙悟空的本体能够任意次数地挥动金箍棒（包括 $0$ 次）。

请问，在多次（包括 $0$ 次）挥动金箍棒后，所有分身所采摘的蟠桃数量之和的最大可能值是多少？

输入格式

输入包括两行。

第一行输入一个整数 $N$（$2 \leq N \leq 10^5$），表示道路的数量。

第二行输入一个仅包含 $L$、$Q$，且长度为 $N$ 的字符串 $S$，其中若 $S_i$ 为 $L$ 表示道路 $i$ 有天兵把守，为 $Q$ 表示道路 $i$ 没有天兵把守（数据保证至少有 $1$ 条道路有天兵把守）。

输出格式

输出一个整数，代表所有分身采摘蟠桃数量之和的最大可能值。

样例输入

3
LQL

样例输出

1

T3. 老君炼丹【算法赛】

问题描述

“炼丹，炼丹！这次我要把所有珍贵药材都放进去，炼出一粒无敌的仙丹”，太上老君大声叫嚷着。

起因是太上老君不小心让孙悟空钻进炼了丹炉，练就了火眼金睛，把天庭大闹了一番。

“老君啊老君，你这办的叫什么事儿！孙悟空现在越发神通广大，你得想办法将功补过！”玉帝怒气冲冲地说道。

“玉帝息怒，小仙这就去炼制一种超级无敌神奇的丹药，定能挽回颜面！”

于是，太上老君就开始翻箱倒柜寻找各种珍贵药材。不一会儿，他的炼丹炉里已经堆满了各种天材地宝，散发出阵阵奇异的香气。

“一共 $N$ 种仙草灵药，每种药材都有自己的药效$\dots$”太上老君喃喃自语道。每种药材的药效都可以用一个整数表示。具体地，第 $i$ 种药材的药效可以表示为 $A_i$。有些药材药性温和，对应的 $A_i$ 就是一个正数，而有些药材则药性猛烈，对应的 $A_i$ 就是一个负数。还有些药材药性平衡，对应的 $A_i$ 就为 $0$。

“炼丹的关键，就在于药材的融合。但我该如何融合这些药材呢？”

太上老君思索着。不一会儿，聪明的他就想到了融合方法：每一次，他可以从炉中选出两种药材，一种药效 $\geq 0$，一种药效 $\leq 0$，将它们混合在一起重新放入炉中，两种药材就会合成为一种药效为两者之和的新药材。当炉内只剩一种药材时，这最后一种药材就是太上老君所求的无敌仙丹。

“可是这些药材，真的可以成功合成一粒仙丹吗？”太上老君不禁陷入了沉思。

现在，请你帮助太上老君判断，他最终能否将这些药材融合成一粒仙丹。

输入格式

第一行包含一个整数 $N$（$1\leq N \leq 10^3$），表示药材的种类数。

接下来一行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$-10^5\leq A_i \leq 10^5$），表示每种药材的药效值。

输出格式

输出一行，包含一个字符。如果能成功融合，则输出 Y；否则，输出 N。

样例输入

3
2 3 -4

样例输出

Y

样例输入 2

2
1 2

样例输出 2

N

样例说明

对于第一个样例，可以先将药效为 $2$ 和 $-4$ 的两种药材进行融合，得到药效为 $-2$ 的新药材。然后，将药效为 $-2$ 的新药材和药效为 $3$ 的药材进行融合，得到药效为 $1$ 的新药材。此时药材只剩一种，即太上老君所求的无敌仙丹。答案为 Y。

对于第二个样例，由于两种药材的药效都 $> 0$，因此无法将它们融合成无敌仙丹。答案为 N。

T4. 拯救美猴王【算法赛】

问题描述

"五百年了，怎么还没有人来拯救我！"

自从孙悟空大闹天宫后，他被如来佛祖使用镇压符镇压在五指山下。整整五百年后，终于迎来了一位有缘人，也就是你。

你希望撕掉镇压符，解救孙悟空。但是镇压符上留下了一个问题：

在五指山前有 $N$ 颗桃树，其中第 $i$ 颗桃树上结了 $A_i$ 个桃子，请问有多少个五元组 $(a,b,c,d,e)$ 的下标组合满足以下条件：

• $1 \leq a <b<c<d<e\leq N$。
• $A_a+A_b =A_c=A_d+A_e$。

只有计算出正确答案才能将镇压符撕掉，从而解救悟空。时间紧迫，请你速速计算。

输入格式

第一行输入一个整数 $N(5 \leq N \leq 2000)$ 表示桃树的数量。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 2000)$ 表示每颗桃树上的桃子个数。

输出格式

输出一个整数表示答案。

输入样例

7
1 1 2 3 2 1 1

输出样例

6

T5. 蟠桃树【算法赛】

问题描述

"第 $114511$ 届蟠桃大会开始了！！！"

蟠桃大会是天庭中最重要的节日，各路神仙齐聚一堂，只为品尝这三千年一熟的神果。每年，王母娘娘都会将最大的一颗蟠桃奖励给最聪明的神仙。

具体地说，王母娘娘会出一道题目，最快回答的神仙将会得到本年度的最大蟠桃。今年的题目如下：

给定一颗有 $n$ 个节点的树，其中根节点编号为 $1$，第 $i$ 个点的颜色为 $s_i$，每个节点的颜色可能为白色或者黑色。请你计算任意满足以下条件的二元组 $(u,v)$ 的最近公共祖先的深度之和。

• $1 \leq u < v \leq n$。
• $s_u \ne s_v$。

由于答案可能很大，需要对 $998244353$ 取模后输出。

齐天大圣孙悟空十分渴望得到这颗最大的蟠桃，奈何智商有限，请你帮帮他。

注意：根节点的深度视为 $1$。

输入格式

第一行输入一个整数 $n(1 \leq n \leq 10^5)$ 表示树的节点数量。

第二行输入一个长度为 $n$ 的字符串 $s(s_i \in[0,1])$，其中 $s_i$ 表示第 $i$ 个节点的颜色，若 $s_i=0$ 则表示白色，否则表示黑色。

接下来 $n-1$ 行，每行两个整数 $u,v(1 \leq u,v \leq n)$ 表示节点 $u,v$ 之间有一条边。保证给定的数据为一棵树。

输出格式

输出一个整数表示答案，答案需要对 $998244353$ 取模后输出。

输入样例

5
10011
1 2
2 3
2 4
1 5

输出样例

8

说明

对于样例给定的树如下图：

图片描述

T6. 真假美猴王的幽谷纷争【算法赛】

问题描述

在取经的悠悠长途中，孙悟空饱经无数艰难困阻。在一回与妖怪的激烈拼杀过后，孙悟空身负重伤，法力锐减。

恰在此时，他听闻在一处神秘的幽谷里，生长着 $n$ 株奇异的灵花，其中第 $i$ 株灵花蕴含着 $a_i$ 份神奇的灵力。据说，若是获取这些灵力，便能迅速恢复伤势并增强自身的法力。

然而，不知怎的，这一消息竟被六耳猕猴获悉。六耳猕猴向来对孙悟空的本领和地位心怀觊觎，于是他决定跟随孙悟空，一同赶赴幽谷，争抢灵花的灵力。

因幽谷禁止争斗，所以在夺取灵花灵力时，他们商定了以下规则：

双方轮流行动。孙悟空享有优先行动权。一旦幽谷中再无灵花，争夺便宣告终止。每次行动时，可以选取一株灵花。设该灵花的灵力数量为 $A$：

1. 若 $A \leq k$，行动者能够将所有灵力吸纳。
2. 若 $A > k$，行动者需要将这株灵花拆分为两株灵花并重新放回幽谷，其中一株包含 $x$（$1 \leq x \leq A - 1$）点灵力，另一株包含 $A - x$ 点灵力。

孙悟空和六耳猕猴都企图通过最为理想的选取策略，让自己吸纳到的灵力总数达到最大。那么，请问孙悟空能够吸纳的最大灵力总数是多少呢？

输入格式

第一行包含两个整数 $n$（$1\leq n \leq 10^5$）和 $k$（$1\leq k \leq 10^9$），分别表示灵花的数量和一次行动可吸纳的灵力上限。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i \leq 10^9$），分别表示每株灵花所蕴含的灵力。

输出格式

输出一个整数，表示孙悟空能够吸纳的最大灵力总数。

样例输入

3 3
2 2 5

样例输出

4

样例说明

对孙悟空而言，一种最优的吸纳过程如下：

• 孙悟空选择第 $1$ 株灵花，吸纳 $2$ 点灵力。
• 六耳猕猴选择第 $2$ 株灵花，吸纳 $2$ 点灵力。
• 孙悟空选择第 $3$ 株灵花，并将灵花拆分为两株新的灵花，一株包含 $2$ 点灵力，一株包含 $3$ 点灵力。
• 六耳猕猴选择包含 $3$ 点灵力的灵花。
• 孙悟空选择包含 $2$ 点灵力的灵花。

因此，孙悟空能够吸纳的灵力总数的最大值为 $2 + 2 = 4$。

T7. 再遇白骨精【算法赛】

问题描述

话说唐僧师徒四人西天取经归来，路过白虎岭时，忽然狂风大作，飞沙走石。只见那白骨精幻化成一个书生，手持折扇，拦住了去路。

“几位圣僧，别来无恙啊！” 白骨精阴阳怪气地说道，“我这里有一道难题，若能解开，便放你们过去，如若不然…”

白骨精话音未落，孙悟空便跳到前面，抓耳挠腮道：“你这妖怪，休要胡言乱语，俺老孙可不怕你！快把题目拿来！”

白骨精冷笑一声，打开折扇，只见上面写着：

有 $n$ 个村庄，每个村庄都有 $m$ 户人家。每户人家都供奉着一尊佛像，香火旺盛时，佛像便会显灵。

若用 $a_{i, j} = 1$ 表示第 $i$ 个村庄的第 $j$ 户人家的佛像显灵了，用 $a_{i, j} = 0$ 表示佛像未显灵。那么请问，对于所有村庄的所有人家，总共有多少种不同的佛像显灵组合情况，可以使得对于每个 $j$（$1 \leq j \leq m-1$），都至少存在 $k$ 个村庄，其第 $j$ 户和第 $j+1$ 户人家的佛像同时显灵？

孙悟空听完题目，顿时傻了眼，想了半天也毫无头绪。只见唐僧微微一笑，对白骨精说道：“女施主，你这题难得倒我的徒弟，但可难不倒我…”。说罢，唐僧连忙转过身，拿出手机，发消息向你求助。

请你帮助唐僧回答这个问题。由于答案可能很大，因此你只需要给出答案对 $998244353$ 取模后的结果即可。

输入格式

输入的第一行包含三个整数 $n$（$1\leq n \leq 10$），$m$（$1\leq m \leq 100$） 和 $k$（$1\leq k \leq n$），其含义如题所述。

输出格式

输出一个整数，表示所有可能的佛像显灵组合情况的数量，对 $998244353$ 取模后的结果。

样例输入

3 2 2

样例输出

10

样例解释

在这个样例中，有 $3$ 个村庄，每个村庄有 $2$ 户人家，要求对于每个 $j$（$1\leq j \leq 2-1$），至少有 $2$ 个村庄的第 $j$ 户和第 $j+1$ 户人家的佛像同时显灵。我们可以通过列举所有可能的组合情况来计算答案。由于村庄数量较少，我们可以手动计算或编写程序来枚举所有符合条件的组合。

满足条件的组合有以下 $10$ 种：

点我展开

• 第 $1$ 种

第一个村庄：1 | 1

第二个村庄：1 | 1

第三个村庄：0 | 0

• 第 $2$ 种

第一个村庄：1 | 1

第二个村庄：1 | 1

第三个村庄：1 | 0

• 第 $3$ 种

第一个村庄：1 | 1

第二个村庄：1 | 1

第三个村庄：0 | 1

• 第 $4$ 种

第一个村庄：1 | 1

第二个村庄：1 | 1

第三个村庄：1 | 1

• 第 $5$ 种：

第一个村庄：1 | 1

第二个村庄：0 | 0

第三个村庄：1 | 1

• 第 $6$ 种：

第一个村庄：1 | 1

第二个村庄：1 | 0

第三个村庄：1 | 1

• 第 $7$ 种：

第一个村庄：1 | 1

第二个村庄：0 | 1

第三个村庄：1 | 1

• 第 $8$ 种：

第一个村庄：0 | 0

第二个村庄：1 | 1

第三个村庄：1 | 1

• 第 $9$ 种：

第一个村庄：1 | 0

第二个村庄：1 | 1

第三个村庄：1 | 1

• 第 $10$ 种：

第一个村庄：0 | 1

第二个村庄：1 | 1

第三个村庄：1 | 1

T8. 花果山洞【算法赛】

问题描述

"花果山也装修新山洞了！！"

所谓一猴得道，群猴升天。

自从孙悟空去天庭做官之后，花果山的待遇也水涨船高，许多山洞都进行了装修，成为了猴子们的新宿舍，但是如何安排猴子们进行山洞选择却是一个难题。

具体地说，现在需要将 $n$ 只猴子分配进 $n$ 个山洞，猴子们的编号为 $1 \sim n$，山洞的编号也为 $1 \sim n$。

在入住山洞时，我们需要将猴子们按照某种排列顺序依次从 $1$ 号洞开始入住，例如猴子们的排序为 $[4,2,3,1]$，则意味着 $4$ 号猴入住 $1$ 号山洞，$2$ 号猴入住 $2$ 号山洞，$3$ 号猴入住 $3$ 号山洞，$1$ 号猴入住 $4$ 号山洞。

由于猴群等级界限森严，每只猴子还会被另外一只猴子所压制，第 $i$ 只猴子会被编号为 $a_i$ 的猴子所压制，这意味着编号为 $a_i$ 的猴子所居住的山洞编号必须小于编号为 $i$ 的猴子所居住的山洞。

现在请问，在满足所有优先级关系的情况下，每个山洞可能出现多少种不同编号的猴子居住呢？

输入格式

第一行输入一个整数 $n(1 \leq n \leq 10^5)$，表示猴子和山洞的数量。

接下来一行 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(0\le a_i \le n,a_i \ e i)$，表示每只猴子被哪只猴子压制。

数据保证有且仅有一个 $a_i$ 满足 $a_i$ 等于 $0$，意味编号为 $i$ 的猴子不会被其他任何猴子所压制。并且优先级关系合法，不会出现环。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个山洞可能出现多少种不同编号的猴子居住。

输入样例

4
0 1 1 2

输出样例

1 2 3 2

T9. 神通顶点【算法赛】

问题描述

“孙悟空的神通顶点是多少？”

这是天庭众神讨论许久却仍未明晰的谜题。在众人眼中，孙悟空的神通好似广袤无垠，没有确切的界限。但从道法的层面思索，神通的范畴乃是修行者为在三界立足而练就的本事，其范围取决于修行者的心境和造化。

如来佛祖受到触动，认为尽管孙悟空的神通本身没有尽头，但其施展和运用或许存在界限。为了探究此理，如来佛祖为悟空设立了一项考验。

假设孙悟空当前的神通值为 $N$，现要求孙悟空分化出若干个分身（至少 $2$ 个）。第一个分身的神通值大于或等于 $2$；后续每一个分身的神通值均为前一个分身的神通值的整数倍；所有分身的神通值相乘的结果等于 $N$。

请问，孙悟空有多少种不同的完成考验的方式呢？

不同的方式是指在满足条件的情况下，分身的神通的数值组合不同。例如，若 $N = 16$ ，一种方式可以是第一个分身神通威力为 $2$ ，第二个为 $8$；另一种方式可以是第一个分身神通威力为 $4$，第二个为 $4$。这两种组合就被视为不同的方式。

输入格式

第一行包含一个整数 $N$（$2 \leq N \leq 10^{18}$）。

输出格式

输出一个整数，表示孙悟空完成考验的不同方式的数量。

样例输入

8

样例输出

2

样例说明

当 $N = 8$ 时，满足条件的方式有：$\lbrace 2, 4 \rbrace$，$\lbrace 2,2,2 \rbrace$。