1116 第 22 场 小白入门赛/强者挑战赛

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

T1. 变身【算法赛】

问题描述

炎炎夏日，蚊虫肆虐。炘南正潜心修炼光之能量，突然一只蚊子在他耳边嗡嗡作响，扰得他心烦意乱。

他猛地睁开眼，大喝一声：“炎龙侠，合体！”

红光一闪，炎龙侠现身！他使出必杀技——“封魔斩、火焰拳”！

结果，一记重拳下去，蚊子毫发无损，反倒是炘南的拳头隐隐作痛。

原来，这只蚊子竟是界王偷偷用黑魔法改造过的超级蚊子！它的防御力高达一亿点！

炘南无奈地叹了口气，心想：“看来对付这只蚊子，只能智取了。”

他灵机一动，掏出了一瓶风油精，轻轻一抹，蚊子瞬间逃之夭夭。

请问，炘南变身时喊出的口号，包含了多少个汉字？

输入格式

无

输出格式

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

T2. 消灭卡片【算法赛】

问题描述

指挥中心内，刺耳的警报声划破寂静。巨大的屏幕上显示着令人不安的数字：“$n$”——这是邪恶势力最新召唤出的怪物卡片数量！

“$n$ 张？！” 风鹰侠惊呼，语气中充满了担忧，“这可不是个小数目！”

帝王侠眉头紧锁，手指在控制台上快速滑动，调出一张张怪物卡片的资料。这些卡片形态各异，能力也千差万别，但无一例外地散发着令人心悸的黑暗气息。

“情况比预想的更糟，”帝王侠沉声道，“这些怪物卡片蕴含着巨大的能量，必须尽快消灭，否则后果不堪设想。”

“我们该怎么办？” 地虎侠焦急地问道。

“根据分析，这些怪物卡片的能量结构存在两种弱点，我们可以利用这两种弱点，分别派遣三人小队和五人战队进行精准打击。”

他调出两张作战方案图，上面分别显示着三角阵型和五角星阵型。“三人小队采用三角阵型，可以迅速消灭三张怪物卡片的能量核心；五人战队则结成五角星阵型，可以迅速消灭五张怪物卡片的能量核心。”

“也就是说，每次行动要么消灭 $3$ 张，要么消灭 $5$ 张？”风鹰侠确认道。

“是的。并且，我们必须用最少的行动，来消灭这 $n$ 张卡片”。帝王侠环视众人，语气坚定：“尽快，计算出最少的行动次数。”

输入格式

第一行输入一个整数 $t$ $(1 \leq t \leq 10^5)$，表示测试数据的数量。

接下来的 $t$ 行，每行输入一个整数 $n$（$1\leq n \leq 10^9$），表示怪物卡片的数量。

输出格式

对于每组测试数据，输出一个整数，表示消灭 $n$ 张卡片最少需要行动的次数。如果无法使用三角阵型、五角星阵型消灭所有怪物卡片，则输出 $-1$。

输出格式

对于每组测试数据，输出一个整数，表示最少需要的行动次数。

样例输入

2
2
6

样例输出

-1
2

提示

$n=2$ 时，（由于卡片数量不够）无法使用三角阵型、五角星阵型消灭所有怪物卡片，固输出 $-1$。

$n=6$ 时，可以使用 $2$ 次三角阵型来消灭所有怪物卡片，固输出 $2$。

T3. 招募队员【算法赛】

问题描述

为了对抗蠢蠢欲动的异能兽，炎龙侠、飞鹰侠、黑犀侠、雪獒侠和地虎侠五位铠甲勇士决定各自组建战队，迎战强敌。

消息一出，光影村的铠甲后人热血沸腾，纷纷组队报名。

现共有 $n$ 支队伍，每支队伍由五名年轻小伙组成，他们各自填写了最想跟随的铠甲勇士编号（$1$ 代表炎龙侠，$2$ 代表飞鹰侠，以此类推，$5$ 代表地虎侠）。用 $a_{i,j}$ 表示第 $i$ 支队伍的第 $j$ 名队员最想跟随的铠甲勇士的编号。例如，$a_{3,2} = 4$ 就表示第 $3$ 支队伍的第 $2$ 名队员想加入雪獒侠的战队。

为了公平公正，每位铠甲勇士需从报名队伍中选择一个连续的区间 $[l, r]$（$1 \le l \le r \le n$）进行招募。但有一个重要的规则：**对于区间内的每一支队伍，该铠甲勇士必须且只能招募一名心仪他的队员。**如果某支队伍中没有队员想跟随这位铠甲勇士，那么这位铠甲勇士就不能选择包含这支队伍的区间。

现在，五位铠甲勇士都想知道自己最多能招募到多少队员，以便制定最佳的作战策略。你能帮助他们计算出各自可招募的最大人数吗？

输入格式

第一行包含一个整数 $n$（$1\leq n \leq 10^5$），表示报名队伍的总数。

接下来 $n$ 行，每行包含五个整数 $a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}, a_{i,5}$（$1 \leq a_{i,j} \leq 5$），表示第 $i$ 支队伍中五名队员想跟随的铠甲勇士编号。

输出格式

输出一行，包含五个整数，分别表示炎龙侠、飞鹰侠、黑犀侠、雪獒侠和地虎侠最多能招募到的队员数量。

样例输入

5
1 2 3 4 5
1 2 3 4 5
1 1 1 1 1
1 2 3 4 5
1 2 3 4 5

样例输出

5 2 2 2 2

T4. 能量晶石【算法赛】

问题描述

暗影大帝被打败了，为了庆祝这来之不易的胜利，$N$ 个光影村小伙伴们聚在一起，准备开一场盛大的庆功宴。庆功宴上，光影村的长老们为每个小伙伴准备了一些能量晶石，其中第 $i$ 个小伙伴获得了 $A_i$ 个能量晶石。

可是，长老们分配的能量晶石数量并不相同。如果每个人最终得到的能量晶石数量不一样，一些小伙伴就会觉得不公平，可能会影响到庆功宴欢乐的气氛。

为了避免这种情况，小伙伴们决定互相帮助。每个小伙伴可以多次前往能量矿脉，每次前往都能为除自己以外的所有小伙伴额外带回一个能量晶石。但前往能量矿脉很消耗精力，大家都想尽可能少跑一趟。

那么，为了让所有小伙伴最终都拥有相同数量的能量晶石，至少需要前往能量矿脉多少次呢？

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示光影村小伙伴的人数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$($1 \le A_i \le 10^9$)，表示每个小伙伴拥有的能量晶石数量。

输出格式

输出一个整数，表示为了让所有小伙伴最终都拥有相同数量的能量晶石，至少需要前往能量矿脉的次数。

样例输入

3
2 2 3

样例输出

1

样例说明

在给定样例中，有 $3$ 个小伙伴，初始能量晶石数量分别为 $2, 2, 3$。如果第 $3$ 个小伙伴去一次能量矿脉，他将为其他两个小伙伴各带回一个能量晶石，最终每个小伙伴都拥有 $3$ 个能量晶石。因此，至少需要前往能量矿脉 $1$ 次。

T5. 缺失的环节【算法赛】

问题描述

暗影大帝又双叒叕来搞破坏了。这次，他派出了 $n$ 个暗影护法，每个护法都携带了一面写着 $0$ 或 $1$ 的旗帜。这些旗帜连起来，就组成了一个长度为 $n$ 的二进制暗号串 $S$。

皮皮虾 ERP 研究协会的专家们确信，暗影大帝的最终阴谋就藏在这个暗号串里。他们发现，每个连续的旗帜子集都对应着一个能量值，这个能量值可以通过将旗帜上的二进制数字串转换成十进制数得到。例如，如果旗帜子集是 "101"，则对应的能量值就是 $5$。

为了阻止暗影大帝的阴谋，铠甲勇士们需要找到最小的、没有被使用的能量值。这个能量值代表着暗影大帝阴谋中缺失的关键环节，找到它就能瓦解暗影大帝的计划。

具体来说，定义 $F(l, r)$ 为子串 $S[l \dots r]$ 转换成的十进制能量值。现在，对于所有的 $F(l, r)$，请你帮助铠甲勇士找出其中最小的、不存在的非负整数。

输入格式

第一行输入一个整数 $n$ ($1 \le N \le 10^5$) ，表示暗号串的长度。

第二行输入一个长度为 $N$ 的二进制字符串 $S$，表示暗号串。

输出格式

输出一个整数，表示最小的、不存在的非负整数能量值。

样例输入

3
101

样例输出

3

样例说明

子串	二进制	十进制
$S_{1,1}$	1	1
$S_{1,2}$	10	2
$S_{1,3}$	101	5
$S_{2,2}$	0	0
$S_{2,3}$	01	1
$S_{3,3}$	1	1

未出现的最小非负整数为 $3$。

T6. 召唤帝皇侠【算法赛】

图片描述

问题描述

暗影再次笼罩地球，邪恶的影界势力卷土重来，企图让世界陷入永恒的黑暗。为了对抗这股强大的黑暗势力，最强铠甲——帝皇侠，必须被唤醒！

召唤帝皇侠需要消耗巨大的能量，这些能量以光子为单位进行计算。目前，ERP 研究室的能量核心储存着 $X$ 个单位的光子能量。只是，帝皇侠的召唤仪式非常严格，并非任何能量值都能唤醒他。只有当释放的能量值 $N$（$1\leq N \leq X$） 是 $\lfloor \sqrt{N} \rfloor$ 的整数倍时，才能与光影石产生共鸣，成功召唤帝皇侠。

情况紧急，敌人步步紧逼。美真必须预先计算好所有符合条件的能量值 $N$ 的总和，以便在激烈的战斗中，根据能量核心剩余的能量，迅速判断是否存在符合条件的能量值。

作为美真的助手，请你帮助美真计算出所有符合条件的能量值 $N$ 的总和，并对 $998244353$ 取模。

输入格式

第一行给出测试用例的个数 $T$（$1\leq T \leq 10^5$）。

接下来 $T$ 行，每行包含一个整数 $X$（$1\leq X \leq 10^{18}$），表示能量核心储存的光子能量。

输出格式

对于每个测试用例，输出一个整数，表示所有符合条件的能量值 $N$ 的总和，并对 $998244353$ 取模。

样例输入

2
3
5

样例输出

6
10

样例说明

在第一个测试用例中，满足条件的 $N$ 有：$1,2,3$，总和为 $6$。

在第二个测试用例中，满足条件的 $N$ 有：$1,2,3,4$，总和为 $10$。

T7. 铠甲合体【算法赛】

图片描述

问题描述

暗影大帝又开始搞事情了！这次他派出了 $M$ 个战斗力爆表的暗影护法，准备一举摧毁 ERP 研究院！$M$ 个暗影护法的战斗力可分别用 $B_1, \cdots, B_M$ 表示。

ERP 研究院紧急召唤了 $N$ 位铠甲勇士前来迎战！每位铠甲勇士都拥有强大的能量，能量值分别为 $A_1, \cdots, A_N$。这些能量值之间存在着某种特殊的联系：任意两位铠甲勇士的能量值，其中一个总是另一个的整数倍。

例如，可能存在能量值分别为 $1, 2, 4, 8$ 的铠甲勇士，但绝不会出现能量值分别为 $2$ 和 $3$ 的铠甲勇士。

为了击败暗影护法，铠甲勇士们需要进行合体，将自身的能量组合起来。当合体后的能量总和恰好等于护法的战斗力时，就能将其击败。 现在，ERP 研究院需要你的帮助！对于每个暗影护法，请你计算出需要多少个铠甲勇士合体才能击败他。如果无论如何都无法击败，那就暂时撤退！

输入格式

第一行输入两个整数 $N$ 和 $M$ ($1 \le N, M \le 10^5$)，分别表示铠甲勇士的数量和暗影护法的数量。

第二行输入 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^{10}$)，表示每个铠甲勇士的能量值。

第三行输入 $M$ 个整数 $B_1, B_2, \dots, B_M$ ($1 \le B_i \le 10^{10}$)，表示每个暗影护法的战斗力。

输出格式

输出一行，包含 $M$ 个整数，分别表示击败每个暗影护法所需的最少合体个数；如果无法击败则输出 $-1$。

样例输入

3 2
2 2 2
6 3

样例输出

3 -1

样例解释

对于战斗力为 $6$ 的暗影护法，可以由三个能量值为 $2$ 的铠甲勇士合体击败，最少合体个数为 3。

对于战斗力为 $10$ 的暗影护法，无法由任何铠甲勇士组合击败，因此输出 -1。

T8. 战斗力评估【算法赛】

图片描述

问题描述

暗影大帝又开始搞事情了。他派出了 $N$ 个暗影护法，每个暗影护法的战斗力可以用一个正整数 $A_i$ 来表示。炘南队长为了更好地安排作战计划，决定对这些暗影护法进行一次战斗力评估。

评估过程是这样的：首先，炘南队长选择一个非负整数 $X$ 作为“能量系数”。然后，对于每个暗影护法，他会用暗影护法的战斗力 $A_i$ 与能量系数 $X$ 进行异或运算（就像光影石和铠甲进行能量融合一样），得到一个新的战斗力数值 $B_i = A_i \text{ XOR } X$。

接下来，为了方便比较，炘南队长会将这些新的战斗力数值 $B_i$ 按从小到大进行排序。排序完毕后，炘南队长又会将每个 $B_i$ 再与能量系数 $X$ 进行一次异或运算，得到最终的战斗力评估结果。

现在，炘南队长想知道，通过选择不同的能量系数 $X$，最终可以得到多少种不同的战斗力评估结果 $B$ 呢？

输入格式

第一行包含一个整数 $N$（$1\leq N \leq 10^5$），表示暗影护法的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1\leq A_i \leq 10^9$），表示每个暗影护法的战斗力。

输出格式

输出一个整数，表示最终可能得到的不同的战斗力评估结果 $B$ 的数量。

样例输入

3
1 2 2

样例输出

2

T9. 幸福饺子馆【算法赛】

问题描述

在打败黑魔兽之后，世界恢复了和平，炎龙侠炘南也如愿成为了“幸福饺子馆”的店长。炎炎夏日，饺子馆生意火爆。为了应对源源不断的顾客，炘南决定制作 $N$ 种不同口味的饺子。同时，为了保证口味的层次感，他规定饺子的辣度必须按照非严格递增的顺序排列，也就是第一种口味的辣度要小于等于第二种，第二种小于等于第三种，以此类推。

已知第一种口味的饺子辣度是 $L$，最后一种口味的饺子辣度是 $R$（每一种辣度对应一个整数）。

现在，请你对于所有可能的饺子辣度的组合方案，计算出所有饺子的辣度总和，并对 $998244353$ 取模。

例如，如果 $N=3,L=1, R=2$，则可能的辣度组合为 $(1,1,2), (1,2,2)$，总和为 $1+1+2+1+2+2 = 9$，对 $998244353$ 取模后的结果为 $9$。

输入格式

第一行给出测试用例的个数 $T$（$1\leq T \leq 10^5$）。

接下来 $T$ 行，每行包含三个整数 $N, L, R$（$2\leq N \leq 10^5$，$0\leq L \leq R\leq 10^5$），分别表示饺子数量、第一个饺子的辣度和最后一个饺子的辣度。整数之间用空格隔开。

输出格式

输出 $T$ 行，每行包含一个整数，表示所有可能的饺子辣度的组合方案的辣度总和对 $998244353$ 取模后的结果。

样例输入

2
3 1 2
3 1 3

样例输出

9
18