0224 第 7 场 小白入门赛/强者挑战赛

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

T1. 元宵节快乐【算法赛】

问题描述

夜幕降临，明月高悬，元宵之夜的美好氛围洋溢着整个城市。在这个特殊的夜晚，小鸟儿在树梢歌唱，烟花在空中绽放，人们欢聚一堂，共庆佳节。而你，我亲爱的朋友，在这元宵之夜，你依然沉浸于算法的海洋，参与着激烈的算法竞赛。我知道你对于编程的热爱和追求，你的智慧和才华将如明月照亮黑夜，如烟花绽放夜空。

在这个元宵之夜，让我们共同祝愿你，愿你的编程之路充满乐趣和成就。愿你的代码如琴弦的婉转，优雅而巧妙。愿你的思维如烟花的绚丽，创新而精彩。加油，我亲爱的朋友！愿你在这个元宵之夜，无论身在何处，都能感受到节日的喜悦和温馨。愿你的努力和付出得到回报，愿你在算法赛场中展现出非凡的才华。元宵节快乐！

请你输出 Today AK!，来赢取元宵节的祝福！

输入格式

本题为填空题，无需输入即可作答。

输出格式

输出一个字符串，赢取祝福。

T2. 猜灯谜【算法赛】

问题描述

在元宵节的活动现场，有一串环形排列的灯笼，共计 $n$ 个。每个灯笼上伴随着一个谜底以及一个数字，这些数字分别为 $a_1, a_2, \dots, a_n$。

根据元宵节的传统，每个灯笼的谜底都是由相邻两个灯笼上的数字之和得出的。需要注意的是，在环形排列的灯笼中，首尾两个灯笼也是相邻的。

现在，请你计算并依次输出每个灯笼的谜底。

输入格式

第一行包含一个整数 $n$（$3\leq n \leq 10^5$），表示灯笼的数量。 接下来一行，包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i\leq 10^5$），表示每个灯笼上的数字。

输出格式

输出 $n$ 个整数，分别表示第 $1,2,\dots, n$ 个灯笼的谜底。

样例输入

3
1 2 3

样例输出

5 4 3

T3. 数学奇才【算法赛】

问题描述

你是一位数学奇才，但却被困在了神秘的数字王国中。在你面前，摆放着一串神奇的数字，它们组成了一个长度为 $n$ 的序列，记作 $a$。你的使命是利用你特殊的能力，最大化序列中所有数字的总和，但是有一个限制：你只能进行不超过 $n$ 次操作。

那么，你的特殊能力是什么呢？嗯，你可以选择序列中的某一段连续的数字，然后将它们变为自身的相反数。举个例子，假设你选择了位置 $i$，那么 $a_1, a_2, \dots, a_i$ 中的每个数字都会乘以 $-1$。

现在，你需要巧妙运用你的能力，设计一种操作方案，使得经过不超过 $n$ 次操作后，序列 $a$ 中所有数字的总和尽可能大。请计算出这个最大的总和是多少？！

输入格式

第一行包含一个整数 $n$，表示序列 $a$ 的长度 $(1 \leq n \leq 10^5)$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $a$ 中的元素 $(-10^9 \leq a_i \leq 10^9)$。

输出格式

输出一个整数，表示经过不超过 $n$ 次操作后，序列 $a$ 中所有数字的最大总和。

样例输入

3
-1 -2 3

样例输出

6

说明

一种最优的操作方案是：选择位置 $2$，将序列变为 $[1, 2, 3]$。这样一来，序列中所有数字的总和为

$$1 + 2 + 3 = 6$$

显然，不会有比这更大的数字总和了。

T4. 你不干？有的是帕鲁干！【算法赛】

问题描述

你不干？有的是帕鲁干！

图片描述

出题人是一位善良的帕鲁管理员（赛博奴隶主）。对于手下的帕鲁，哪怕它是三级的专业技术员，一旦有红色的陋习词条，就不如旁边的一级帕鲁。让一个帕鲁全天候高强度工作，累倒后卖掉换新的帕鲁，会有更高的效益。与其花费大量的材料成本让其治病，不如把它卖掉。如果不想跑太远去卖帕鲁的话，还可以把不干活的帕鲁当成其他帕鲁的材料。一想到关掉电脑，哪些帕鲁都休息了，心理就会难过。

现在出题人想与帕鲁玩一个游戏，如果帕鲁没回答出来，就会把它卖掉。出题人找来了皮皮鸡，给它出了一道题，题目内容如下：

给定一个非负整数 $x$，皮皮鸡需要判断 $x$ 是否可以被表达成两个连续正奇数的平方之差，如果不可以，输出一行 No；若可以，输出两行：第一行输出 Yes，第二行按从小到大输出这两个连续正奇数。

题目保证有唯一解。

现在你魂穿成了皮皮鸡，为了带领帕鲁掀起红色革命，干倒赛博奴隶主，你可以回答出这道题吗？

输入格式

输入的第一行包含一个正整数 $T$（$1\leq T \leq 10^5$），表示测试用例组数。

对于每组测试用例：

输入一行，包含一个非负整数 $x$（$0\le x \le 10^{18}$），含义如题所述。

输出格式

对于每组测试用例：

如果 $x$ 不可以被表达成两个连续正奇数的平方之差，输出一行 No；若可以，输出两行：第一行输出 Yes，第二行按从小到大输出这两个连续奇数。

样例输入

3
8
14
1

样例输出

Yes
1 3
No
No

样例说明

对于第一个测试用例：$8=3^2-1^2$。

对于第二个和第三个测试用例，不存在一对连续的奇数平方之差等于其。

T5. 等腰三角形【算法赛】

问题描述

现有 $2N$ 个红色木棍和 $N$ 个蓝色木棍。

红色木棍的集合由一个长度为 $N$ 的正整数序列 $A$ 表示，序列中每存在一个 $A_i$ 表示有 $2$ 个长度为 $A_i$ 的红色木棍；

蓝色木棍的集合由一个长度为 $N$ 的正整数序列 $B$ 表示，序列中每存在一个 $B_i$ 表示有 $1$ 个长度为 $B_i$ 的蓝色木棍。

现在要求用 $3$ 个木棍组成一个等腰三角形，每个三角形中要包含 $2$ 个红色木棍以及 $1$ 个蓝色木棍，并且要求 $2$ 个红色木棍的长度相等。

求最多可以组成多少个这样的三角形。

输入格式

第一行输入 $1$ 个正整数 $N$（$1 \leq N \leq 200000$），表示序列 $A, B$ 的长度。

第二行输入 $N$ 个正整数 $A_1, A_2, \dots, A_N$（$1\leq A_i\leq 10^9$），表示序列 $A$。

第三行输入 $N$ 个正整数 $B_1,B_2,\dots, B_N$（$1\leq B_i \leq 10^9$），表示序列 $B$。

输出格式

输出仅一行，包含 $1$ 个整数，表示答案。

样例输入

4
4 3 2 1
2 4 3 2

样例输出

3

样例说明

两个长度为 $1$ 的红色木棍无法与给出的蓝色木棍组成三角形。

$({\color{red}2}, {\color{red}2}, {\color{blue}3}), ({\color{red}3}, {\color{red}3}, {\color{blue}4}), ({\color{red}4}, {\color{red}4}, {\color{blue}2})$ 是一组解。

图片描述

T6. 计算方程【算法赛】

问题描述

给定正整数 $k,m$。

请你根据以下式子

$$\sqrt{x} + \lfloor \log_{k}x\rfloor -m > 0$$

计算出符合结果的最小正整数 $x$ 。

输入格式

第一行输入 $1$ 个正整数 $t$（$1\leq t\leq 10^3$），表示测试用例组数。

接下来 $t$ 行，每行输入 $2$ 个正整数 $k,m$（$1\leq k,m \leq 10^4$）。

输出格式

输出 $t$ 行，每行包含 $1$ 个正整数，表示结果。

样例输入

4
4 6
2 7
2 8
2 9

样例输出

17
16
17
26

T7. 谁是帕鲁？【算法赛】

问题描述

我只是一段代码。而你，我的朋友，天一亮，你才是真正的帕鲁。

图片描述

干的不好，能力差，就会被优化掉。你不干？有的是帕鲁干！我招你进来，是为了解决其他帕鲁解决不了的问题的，你需要证明你的价值在哪里。别人是准神兽，四级的挖矿技能，而你随时可能被开。我对你的期望是非常高的，一直把你视作营地里的骨干力量，但我希望你再进步点，不要动不动就抑郁偷懒。现在，帕鲁被赛博奴隶主命令解决如下题目，如果解决不出该问题，就会被优化掉。具体题目如下：

对于阿拉伯数字 $0\sim 9$，有些数字从图形上看是有封闭图形存在的，具体为：

数字	封闭图形数量
$0$	$1$
$1$	$0$
$2$	$0$
$3$	$0$
$4$	$1$
$5$	$0$
$6$	$1$
$7$	$0$
$8$	$2$
$9$	$1$

请问，在区间 $[L,R]$ 中，有多少个数恰好有 $K$ 个封闭图形，输出该结果。

作为已经魂穿皮皮鸡的你，是否能解决该问题，从而保护你的帕鲁同伴呢？

输入格式

输入一行，包含 $3$ 个正整数 $L,R,K$（$1\le L\le R\le10 ^{12},0\le K\le 24$）。

输出格式

输出 $1$ 个正整数，为在区间 $[L,R]$ 中，有多少个数恰好有 $K$ 个封闭图形。

样例输入 1

1 14 1

样例输出 1

5

样例输入 2

114 514 2

样例输出 2

118

样例说明

对于测试样例 $1$：$4,6,9,10,14$ 均只有一个封闭图形。

T8. 源石开采【算法赛】

问题描述

地面上有 $n$ 条源石矿脉，每条源石矿脉开采一次可以获得 $a_i$（$i\in[1,n])$ 个源石，每条源石矿脉含有的源石是无限的。小红和小蓝一起来开采源石矿，他们都想获得更多的源石，于是他们制定了一个游戏规则。

首先，小蓝和小红会一起开采 $q$ 次源石矿脉，每次从 $l\sim r$ 号矿脉中对其中的产量前 $2$ 大的源石矿脉进行一次开采。例如 $a=[1,2,2,3,4],l=1,r=3$，则他们这一次开采可以获得 $2+2=4$ 个源石。

当他们开采完后，将所有开采到的源石堆放在一起，此时一共有 $\text{sum}$ 个源石。现在，小红和小蓝决定，他们每人轮流从开采出的源石中拿出源石，每人每次至少拿一个源石，最多拿 $m$ 个源石，谁取走了最后一块源石，谁就可以掌握本次开采出的源石的分配权。

当小蓝和小红都是在最优决策下，由 小红先手，最终谁能获得源石的分配权呢？

如果是小红获得，第一行输出 $\text{sum}$，第二行输出 red；如果是小蓝获得，第一行输出 $\text{sum}$，第二行输出 blue。

输入格式

第一行输入 $2$ 个正整数 $n$（$2\leq n \leq 2\times 10^5$） 和 $q$（$1\leq q \leq 10^5$），含义如题所述。

第二行输入 $n$ 个正整数 $a_1, a_2, \dots , a_n$（$1\leq a_i \leq 10^8$），表示序列 $a$。

接下来 $q$ 行，每行输入 $2$ 个正整数 $l,r$（$1\leq l < r \leq n$），代表需要开采的区间。

最后一行输入一个正整数 $m$（$1\leq m \leq 14$），含义如题所述。

输出格式

输出 $2$ 行，第一行输出开采完成的 $\text{sum}$ 个源石，第二行输出一个字符串，如果是小红获胜输出 red；如果是小蓝获胜输出 blue。

样例输入

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

样例输出

16
blue

样例说明

对于样例，三次开采之和为 $1+2+4+5+2+2=16$。可以证明在最多取 $7$ 个的情况下，无论如何博弈，小蓝都有必胜的方式。

T9. 集合划分【算法赛】

问题描述

在奥特曼的世界中，集合论是一种用来理解和描述各种事物和现象的理论工具。盖亚奥特曼发现，集合论可以帮助他更好地理解自己和宇宙，因此他对这个领域产生了浓厚的兴趣。

盖亚奥特曼对集合论的热爱始于他对各种不同类型事物的思考。他发现，无论是生物、非生物、星球、星系，甚至是各种概念和思想，都可以被视为集合的一种形式。他开始探索这些集合的特性、关系和规律，并尝试用集合论来描述和理解他所遇到的各种现象。

现在，盖亚奥特曼希望你能帮助他解决以下集合论问题。

给定长度为 $n$ 的非负整数序列 $\{a\}$，要求将序列 $\{a\}$ 分成 $2$ 个可重集合 $A,B$，满足每个元素在 $A$ 集合或 $B$ 集合，恰有 $2^n$ 种划分方式，现在额外要求集合 $A$ 中所有元素或运算的权值与集合 $B$ 中所有元素或运算的权值相同，特别地，当集合为空时，定义其所有元素的或运算权值为 $0$，请求满足条件的方案数，答案对 $998244353$ 取模。

输入格式

第一行包含 $1$ 个正整数 $n$（$1\leq n \leq 200$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i < 2^{15}$），表示序列 $a$。

输出格式

输出共 $1$ 行，输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入

4
4 5 6 7

样例输出

4