0824 第 17 场 小白入门赛/强者挑战赛

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

T1. 桃园结义【算法赛】

问题描述

“俺老张最喜欢的就是喝酒吃肉，但今天这酒喝得有点晕乎，连自己有几个兄弟都数不清了。”张飞在桃园结义后，喝得酩酊大醉，竟忘了自己有几个结义兄弟。

刘备和关羽见状，决定逗逗张飞，让他数数结义兄弟一共有几个。张飞挠挠头，嘟囔着：“一个刘备，一个关羽，嗯…还有一个…呃，是谁来着？”

现在，请你帮助张飞，输出一个整数，表示桃园三结义的兄弟总数。

输入格式

无。

输出格式

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

T2. 北伐军费【算法赛】

问题描述

诸葛丞相正在筹备再次北伐，但军费开支庞大，让户部的官员们忧心忡忡。

户部尚书小心翼翼地说：“丞相，如今国库空虚，军费问题实在棘手…”

诸葛亮胸有成竹地回应：“无妨，我去向陛下借些。”

于是，诸葛亮来到了刘禅的寝宫。

“陛下，臣即将北伐，急需一笔军费…”诸葛亮恳求道。

刘禅面露难色：“啊，北伐确为大事，但朕最近斥巨资修建了一座宫殿，实在拿不出多少金币。”

“陛下，臣所需不多。这样吧，我们来玩个游戏，若臣赢了，还请陛下赐予臣一些军费，如何？”诸葛亮微微一笑。

“哦？什么游戏？朕最近对新奇的游戏颇感兴趣。”刘禅顿时来了兴致。

“我们来取铜钱。臣这里有 $n$ 个铜钱，每个铜钱上都刻着数字，第 $i$ 个铜钱上的数字是 $a_i$。我们轮流取一枚铜钱，由臣先来。无论谁取走后，剩下的所有铜钱上的数字都会乘以 $-1$。最后，若臣取走的铜钱数字之和 $A$ 减去陛下取走的铜钱数字之和 $B$ 为正，陛下就赐予臣 $A - B$ 的军费；若为负，则臣就…”诸葛亮故作神秘，留下悬念。

“有点意思，那就来吧！”刘禅的兴趣被激发。

就这样，诸葛亮和刘禅开始了这场精彩的铜钱游戏（由诸葛亮先手）。诸葛亮会尽力最大化 $A - B$ 的值，而刘禅则会尽力最小化这个值。

那么，请你计算一下，最终 $A - B$ 的值会是多少呢？

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 10^3$），表示铜钱的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^3 \leq a_i \leq 10^3$），表示每个铜钱上刻的数字。

输出格式

输出一个整数，表示最终 $A - B$ 的值。

样例输入

3
1 -2 3

样例输出

2

T3. 挑选武将【算法赛】

问题描述

却说天下大乱，曹操挟天子以令诸侯，招募了 $n$ 员猛将，想要兴兵南下。为了联络方便，每位武将都会驻扎在一个城池中，用 $a_i$ 表示第 $i$ 个武将驻扎的城池编号。

这一日，曹操看着账下的武将名单，不禁陷入了沉思。他摸着胡子，对身边的谋士郭嘉说道：“奉孝啊，你看这名单上的武将，个个都是能征善战之辈，但你也知道，这军中之事，最忌讳的就是结党营私。你看这名单上，有些人住在一个城池里，这要是都带上了，难免会…”

郭嘉听罢，立刻明白了曹操的担忧。他微微一笑，说道：“主公英明！这挑选武将，确实要慎重啊！不如这样，我给主公精挑细选 $k$ 员猛将，让他们尽量避免来自同一城池，以免生出不必要的麻烦。主公意下如何？”

曹操听后龙颜大悦，说道：“妙啊！那你快帮我算算，挑选的 $k$ 员猛将，最多能有几个是单独来自一个城池的？”

输入格式

第一行输入两个整数 $n,k$（$1\leq k \leq n \leq 10^5$），表示武将的总数量和要挑选的武将数量。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\leq a_i \leq 10^5$），表示每位武将驻扎的城池编号。

输出格式

输出一个整数，表示最多能挑选的单独来自不同城池的猛将数量。

样例输入

5 4
1 1 2 2 3

样例输出

2

样例说明

武将的驻扎城池编号分别为 $1$、$1$、$2$、$2$ 和 $3$。可挑选 $2$ 个来自城池 $1$ 的的武将，$1$ 个来自城池 $2$ 的武将，以及 $1$ 个来自城池 $3$ 的武将。这样，单独来自一个城池的武将共有 $2$ 个。

T4. 三顾茅庐【算法赛】

问题描述

卧龙凤雏，得一者可得天下！

在东汉末年，英雄豪杰聚集，刘备帐下的智囊徐庶家母遭曹操绑架，只得投奔曹家。在告别刘备之际，他将卧龙诸葛亮的所在告知刘备，引得刘备三顾茅庐，欲邀卧龙出山相助。

卧龙知晓刘备之雄心壮志，为考其统御之才，决定以一道难题来考验。

"我门前有一株神奇柳树，初高 $x$，每次操作可将其高度变为 $|\text{当前高度}-y|$，问经 $k$ 次操作后，树高为何？"

这个难题或许能考验刘备的智慧，望你能帮助他解答这一难题。

输入格式

第一行输入一个整数 $t(1 \leq t \leq 10^5)$ 表示卧龙的询问次数。

接下来 $t$ 行，每行三个整数 $x,y,k(0 \leq x,y,k \leq 10^9)$ 表示一次询问。

输出格式

输出 $t$ 行，每行一个整数表示答案。

输入样例

3
10 1 3
10 1000 99999
10 0 0

输出样例

7
990
10

T5. 逆天改命【算法赛】

问题描述

话说诸葛丞相北伐中原，路遇司马老贼，屡战屡败。眼看蜀汉大业将要付诸东流，忧心忡忡的丞相来到了五丈原，夜观天象，发现原本代表着蜀汉国运的 $n$ 盏星灯，如今却暗淡无光！

“唉，想我蜀汉将星陨落，难道天命如此？” 丞相长叹一声，眉头紧锁。

忽然，一阵凉风吹过，丞相手中的羽扇掉落在地。他俯身拾起羽扇，发现地上竟有一卷羊皮卷轴！丞相展开卷轴，只见上面写着“星灯续命”四个大字。

“星灯续命？难道是天无绝人之路？” 丞相顿时来了精神，仔细阅读卷轴上的内容。

原来，这 $n$ 盏星灯一字排开，相依为命。每一盏星灯的亮度，可分别用 $a_1, a_2, ..., a_n$ 来表示。

如今所有星灯都已熄灭，亮度均为 $0$。想要逆天改命，重燃星灯，就必须进行若干次操作。每次操作，丞相可以选择连续的一段星灯 $l, r$ ($1 \le l \le r \le n$)，若 $a_l, a_{l+1}, ..., a_r$ 中存在亮度为 $0$ 星灯，则 $a_l, a_{l+1}, ..., a_r$ 这些星灯的亮度都将提升一级（加 $1$）；反之，若 $a_l, a_{l+1}, ..., a_r$ 中不存在亮度为 $0$ 的星灯，则它们的亮度都将降低一级（减 $1$）。

卷轴的最后，还有一张星图，记载着最终每盏星灯所需的亮度 $b_1, b_2, ..., b_n$。

“看来这就是天意啊！” 丞相手握卷轴，眼神坚定，“我倒要试试，能否通过若干次（包括 $0$ 次）操作，将这 $n$ 盏星灯的亮度调整至星图所示的亮度，从而逆天改命，匡扶汉室！”

现在，请你帮助诸葛亮推算一番，看看他能否实现这逆天改命的壮举！

输入格式

第一行包含一个整数 $T$（$1\leq T \leq 10^3$），表示有 $T$ 组测试用例。

对于每组测试用例：

• 第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示星灯的数量。
• 第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ $(0 \leq b_i \leq 10^9)$，表示每盏星灯最终所需的亮度。

数据保证 $n$ 的总和不超过 $10^5$。

输出格式

输出一行，如果可以通过若干次操作将星灯的亮度调整至星图所示的亮度，输出 YES；否则输出 NO。

样例输入

1
5
1 1 1 1 1

样例输出

YES

样例说明

初始时，所有星灯的初始亮度都是 $0$。可以通过对整个范围进行一次操作，使所有星灯的亮度提升到 $1$，达到所需的亮度状态。

T6. 智算士气【算法赛】

问题描述

话说三国时期，曹操打算攻打蜀汉，需要派 $n$ 个将军各自带队出发。

为了避免浪费粮食，曹操想精确计算每个队伍的人数，于是他找来谋士刘晔商量。

刘晔说：“主公，咱可以简单点，用‘士气’来代表队伍人数，‘士气’越高，就表示人数越多，战斗力越强！”

曹操一听，乐了：“妙啊！不过这‘士气’怎么定才合适呢？”

刘晔说：“这‘士气’啊，得满足两个条件：

• 每个队伍的‘士气’都是不超过 $m$ 的正整数；
• 所有队伍的‘士气’的最小公倍数必须正好是 $m$，这样才能保证各部队协调作战，发挥最大战斗力！ ”

曹操听完，摸着胡子说：“好！那你说说，满足条件的‘士气’分配方案到底有多少种？”

刘晔赶紧说：“这…这得找专业的来算啊…”

于是，曹操转头问你：“你知道满足条件的方案数是多少吗？对了，我不喜欢很大的数字，所以你算出来的结果别忘了对 $998244353$ 取个余数。”

请你回答曹操的问题。

输入格式

输入一行包含两个整数 $n,m$（$2\leq n,m \leq 10^9$），分别表示将军（队伍）的数量、单个队伍“士气”的最大值和所有队伍“士气”的最小公倍数。

输出格式

输出一个整数，表示满足条件的士气分配方案的数量，结果对 $998244353$ 取余。

样例输入

2 8

样例输出

7

样例说明

可能的方案有：

$$[1, 8]\\ [8, 1]\\ [2, 8]\\ [8, 2]\\ [4, 8]\\ [8, 4]\\ [8,8]$$

共计 $7$ 种。

T7. 赤壁之战【算法赛】

问题描述

赤壁之战在即，曹操意图一统中原。

然而他忽然发现一个问题——手下的北方将士们个个水土不服，一上船就晕得东倒西歪。

为了让他的将士们在江上能站稳脚跟，曹操决定用铁索将所有战船连成一串，增强战船的稳定性，避免将士们在作战前就被晕船搞得七荤八素。

具体来说，曹操的军营中有 $n$ 艘战船，其中第 $i$ 艘战船的重量为 $a_i$。在铁索的加持下，战船的总稳定性被定义为 $\sum_{i=1}^{n-1} a_i \oplus a_{i+1}$。但是，为了让战船们更加“稳如泰山”，曹操还允许每艘战船可以增加重量 $x$。

作为曹营中的顶级谋士，你的任务就是帮助曹操计算出战船的最大总稳定性。

输入格式

第一行输入两个整数 $n,x(2 \leq N \leq 10^5, 1 \leq x \leq 10^9)$ 表示战船的数量和战船可以增加的重量。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(1 \leq a_i \leq 10^9)$ 表示每艘战船的重量。

输出格式

输出一个整数表示答案，

输入样例

5 2
1 3 6 7 10

输出样例

47

T8. 救灾【算法赛】

问题描述

魏国突发大水，百姓困苦不堪，曹操派遣谋士郭嘉与司马懿前往各地救灾。

具体来说，魏国共有 $N$ 座城市，之间由 $N-1$ 条道路相连，其中第 $i$ 条道路连接城市 $u_i$ 和 $v_i$。确保任何一座城市都可以通过现有的道路到达其他城市。

郭嘉和司马懿需要在 $M$ 天内完成救灾工作。两人最初都位于 $1$ 号城市。在第 $i(1 \leq i \leq M)$ 天，城市 $A_i$ 和 $B_i$ 需要救援，两人需商议各自前往的城市，并有以下约定：

• 若 $i$ 为奇数，则郭嘉可以优先选择前往城市 $A_i$ 或 $B_i$，如果郭嘉选择前往 $A_i$，则司马懿就只能前往 $B_i$；如果郭嘉选择前往 $B_i$，则司马懿就只能前往 $A_i$。
• 若 $i$ 为偶数，则司马懿可以优先选择前往城市 $A_i$ 或 $B_i$，如果司马懿选择前往 $A_i$，则郭嘉就只能前往 $B_i$；如果司马懿选择前往 $B_i$，则郭嘉就只能前往 $A_i$。

两人都希望最大化自己的行动距离，以彰显他们的辛劳，从而赢得曹操的赞赏。

即设郭嘉走的总距离为 $x$，司马懿走的总距离为 $y$。郭嘉希望最大化 $x-y$ 的值，而司马懿则希望最小化 $x-y$ 的值。假设两人都按照最优策略行事，问 $x-y$ 的值是多少？

注意：两人在完成每次救灾任务后会停留在当前城市过夜，且可能存在某一天 $A_i = B_i$ 的情况。

输入格式

第一行输入两个整数 $N,M(1 \leq N,M \leq 10^5)$ 表示城市的数量和救灾工作天数。

接下来 $N-1$ 行每行输入两个整数 $u,v (1 \leq u,v \leq N, u \ e v)$ 表示城市 $u,v$ 之间存在一条道路。

接下来 $M$ 行，每行两个整数 $A_i,B_i(1 \leq A_i,B_i \leq N)$ 表示第 $i$ 天需要被救灾的城市。

输出格式

输出一个整数表示答案。

输入样例

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

输出样例

-1

样例说明

对于样例，无论郭嘉第一天选择几号城市，只要司马懿第二天选择 $3$ 号城市，$x-y$ 的值就都会为 $-1$。

图片描述

T9. 三英战萝卜【算法赛】

问题描述

话说，曹操败走华容道后，心中愤懑不已。一日，曹操正与众谋士在帐中饮酒，忽闻帐外传来阵阵叫好声。曹操唤来一探子，探子禀报道：“启禀丞相，刘备、关羽、张飞三兄弟正在帐外比赛吃萝卜呢！” 曹操听闻，顿时来了兴致，命人将三兄弟请入帐中。

曹操命人搬来 $n$ 个萝卜，言道：“三位将军勇武过人，今日不妨比试一番，看谁能吃得最多！” 说着，曹操指向那 $n$ 个萝卜，解释道：“共有 $n$ 个萝卜，其中第 $i$ 个萝卜的重量为 $a_i$，三位将军需将这些萝卜分别吃下，但需满足以下条件：

• 每人至少要吃下一个萝卜。
• 关羽吃下的萝卜的总重量与张飞吃下的萝卜的总重量相同。”

“若能满足以上条件，则以玄德（刘备）所吃下萝卜的总重量为准。总重量越大，则可获得的奖赏越丰厚。不知三位将军意下如何？”

刘备、关羽、张飞三人欣然接收。现在，请你帮助他们计算一下，在满足曹操所设条件的情况下，刘备所能吃的萝卜总重量最大能是多少？如果无论如何都不能满足条件，请输出 $-1$。

输入格式

第一行包含一个整数 $n$（$3 \leq n \leq 2\times 10^3$），表示萝卜的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq 2\times 10^3$），表示每个萝卜的重量。

输出格式

输出一个整数，表示在满足条件的情况下，刘备所能吃的萝卜总重量的最大值。如果无法满足条件，则输出 $-1$。

样例输入

5
1 2 3 4 5

样例输出

9

样例说明

关羽吃第 $1$、$2$ 个萝卜，张飞吃第 $3$ 个萝卜，刘备吃第 $4$、$5$ 个萝卜，满足条件。 刘备吃的总重量为 $9$。