0323 第 8 场 小白入门赛/强者挑战赛

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

T1. 坤星球【算法赛】

问题描述

坤星球是一颗十万光年之外的星球，相比于地球的时间流逝它的时间流逝更加缓慢，坤星球 $1$ 年等于地球 $2.5$​ 年。

现在问你，$2024$ 坤年等于地球多少年？

注意：答案输出阿拉伯数字，不能为浮点数。

输入格式

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

输出格式

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

T2. 二进制王国【算法赛】

问题描述

二进制王国是一个非常特殊的国家，因为该国家的居民仅由 $0$ 和 $1$ 组成。

在这个国家中，每个家庭都可以用一个由 $0$ 和 $1$ 组成的字符串 $S$ 来表示，例如 $101$、$000$、$111$ 等。

现在，国王选了出 $N$ 户家庭参加邻国的庆典。为了符合王国的审美标准，我们需要选择一种排队顺序，使得最终形成的队伍在字典序上是最小的。

国王将这个任务交给了你，请你解决这个问题。

输入格式

第一行包含一个整数 $N(1\ \leq N \leq 2\times10^5)$，代表二进制家庭数量。

接下来输入 $N$ 行，第 $i$ 行输入一个二进制字符串 $S_i$ 表示第 $i$​​ 户家庭。

数据范围保证：$\sum_{i=1}^{n} |S_i| \leq 2\times 10^5$，其中 $|S_i|$ 表示第 $i$ 个字符串的长度。

输出格式

输出一行一个字符串，表示字典序最小的排队情况。

输入样例

3
111
000
101

输出样例

000101111

说明

字典序最小的排队应该是 $S_2S_3S_1$，形成的队伍为 $000101111$。

T3. djwcb【算法赛】

问题描述

异灵术老师是一位考法考没考过、做程序员被辞退、当站长网页崩溃、做主播游戏关服的倒霉人，同时也是炉石相对论的发明人，具体为：

"嗷，我打错了，这一费奶五不对"

"嗷对的对的对的对的"

"对吗"

"嗷不对 哎呀不对不对"

"哎呀对的对的对的对的"

"嗷不对，还有个狙击"

现在，直播间的弹幕小老哥给他出了这样的一道题目：

给定 $2$ 个正整数 $x,p$，你需要输出 $x^p \bmod 10$ 的结果。

由于异灵术老师不会这道题，因此他找来了直播间的你，如果你做出来了这道题，他就答应你买雀魂的卡维皮肤给你看，你可以做出来这道题吗？

输入格式

第一行输入一个正整数 $T(1\le T\le 1000)$，表示测试数据组数。。

对于每组测试数据：

输入一行，包含两个正整数 $x,p(1\le x\le 10^3,1\le p\le 10^{200000})$。

数据保证 $1\le \sum_{i=1}^{T} \log_{10}{p_i}\le 2\times 10^5$。换句话说，便是保证所有数据指数之和在 $1\sim 2\times 10^5$。

输出格式

对于每组测试数据：

输出一个非负整数，表示 $x^p \bmod 10$ 的结果。

样例输入

2
9 3
10 2

样例输出

9
0

说明

对于第一个查询，$9^3=9\times 9\times 9=729,729 \bmod 10=9$。

T4. 求解线性方程组【算法赛】

问题描述

又到了大家最喜欢的数学考试时间！

小蓝老师给了你 $n$ 个方程组成的线性方程组，格式如下：

$x_1+x_2=a_1$

$x_1+x_2+x_3=a_2$

$x_2+x_3+x_4=a_3$

$\dots \dots\dots$

$x_{n-3}+x_{n-2}+x_{n-1}=a_{n-2}$

$x_{n-2}+x_{n-1}+x_{n}=a_{n-1}$

$x_{n-1}+x_n=a_n$

小蓝老师还会提供给你 $a_1,a_2,a_3,\cdots,a_n(1\le i\le n)$ 的值，并且规定 $x_i$ 由 $0$ 和 $1$​ 构成。

你需要求解给定的线性方程组，由于答案可能不唯一，你需要输出字典序最小的解。

输入格式

第一行输入包含一个正整数 $n(2\le n\le 2\times 10^5)$，表示线性方程组的数量。。

第二行输入 $n$ 个正整数 $a_1,a_2,a_3,\cdots,a_n$ 表示数组 $a(0\le a_i\le 3)$ 的值。

数据保证该线性方程组至少存在一组解，且一定是合法数据。

输出格式

输出 $n$ 个整数，为字典序最小的线性方程组的解，第 $i$ 个整数表示 $x_i$。

样例输入

5
1 2 2 2 1

样例输出

0 1 1 0 1

说明

该线性方程组有两组解，第一组解为 $\text{0 1 1 0 1}$，第二组解为 $\text{1 0 1 1 0}$，因为第一组解字典序更小，所以你需要输出第一组解。

T5. 美丽圆环【算法赛】

问题描述

小蓝得到了一个圆环，圆环上挂着 $N$ 个数字 $A_0, A_1, A_2, \ldots, A_{N-1}$。

为了使圆环变成一个美丽的圆环，需要满足以下条件：

• 对于第 $i$ 个数字 $A_i$，它的相邻数字为 $A_{(i-1+N)\bmod N}$ 和 $A_{(i+1)\bmod N}$。其中，至少有一个相邻数字大于等于 $A_i$，另一个相邻数字小于等于 $A_i$。

现在，小蓝想要让圆环变得足够美丽。他可以进行任意次以下操作：

1. 将圆环上的任意数字更改为任意整数。
2. 交换圆环上任意两个数字的位置。

请问，小蓝最少需要进行多少次操作 $1$ 才能使圆环变成一个美丽的圆环？

输入格式

第一行包含一个整数 $T(1 \leq T \leq1000)$，表示测试数据的组数。

对于每组测试数据：

• 第一行输入一个 $N(2 \leq N \leq 100)$，表示圆环上数字的个数。
• 第二行输入 $N$ 个整数 $A_0,A_1,A_2,\cdots,A_{N-1}$，表示圆环上的数组 $A(1 \leq A_i \leq N)$。

输出格式

对于每组测试用例输出一行一个整数表示答案。

输入样例

2
4
3 2 1 2
3
1 2 3

输出样例

1
2

说明

对于样例 $1$，我们可以先将数组变为 $[1,2,1,2]$ 后重排为 $[1,1,2,2]$​，此时数组符合条件。

对于样例 $2$，我们可以将数组变为 $[1,1,1]$，当然 $[2,2,2],[3,3,3]$ 也符合条件。

T6. 小蓝的跳跃【算法赛】

问题描述

在小蓝面前有 $n$ 个方格，每个方格里面都有一颗糖果，糖果的口味有两种，一种是芒果味，一种是蓝莓味。小蓝每次都可以向前跳跃一格或两格，每到一个方格，小蓝就会将方格上的糖果吃下去。如果小蓝吃到的糖果是芒果味，心情值就会减少 $1$ 点；如果小蓝吃到的糖果是蓝莓味，心情值就会增加 $1$ 点，小蓝的初始心情值为 $0$。

现在问你，是否存在一种跳跃方式，使得小蓝 跳跃出所有方格 后，心情值恰好为 $x$ 点。如果存在，则输出 Yes；如果不存在，则输出 No。

对于跳跃出所有方格的解释：

图片描述

小蓝初始在 $0$ 位置，需要跳跃到终点 $n+1$。

输入格式

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

对于每组测试数据：

第一行输入两个正整数 $n,x$，含义如题所述。（$1\le n\le 2\times 10^5,-2\times 10^5\le x\le 2\times 10^5$）。

第二行输入 $n$ 个整数，第 $i$ 个整数的值为 $1$ 或 $-1$，$1$ 代表该位置是蓝莓味的糖果，$-1$ 代表该位置是芒果味的糖果。（$1\le i\le n$）。

$1\le\sum_{i=1}^{t} n_i\le 2\times 10^5$。

输出格式

对于每组测试数据，若存在一种跳跃方式，使得小蓝跳跃出方格后，心情值恰好为 $x$ 点，则输出 Yes；如果不存在，则输出 No。

样例输入

3
4 1
1 1 1 1
3 1
1 -1 1
2 1
-1 1

样例输出

No
Yes
Yes

说明

对于第一组测试数据：不存在任意一种跳跃方式，使得结果为 $1$。

对于第二组测试数据：你可以选择吃所有的糖果，使得结果为 $1$。

对于第三组测试数据：你可以先跳跃到 $1$，然后再跳 $1$ 格出方格。

T7. 赛博奴隶主【算法赛】

问题描述

作为魂穿皮皮鸡的你，经过一段时间的发展，现在要带领帕鲁们打倒可恶的赛博奴隶主了！

要打倒一个 boss，首先就要知道 boss 的血量。我们的赛博奴隶主作为最大的 boss，自然也有他的血量。但是他十分狡猾，把自己的血量藏了起来。不过无论如何，他必须提供一种方式让帕鲁们知道他的血量。赛博奴隶主所提供的方式如下：

赛博奴隶主把头顶上的血量变成了一个数字 $n$，他的实际血量为 $n$ 的所有约数的 $k$ 次方之和，然后再对 $10^9+7$ 取余。

举个例子，如果 $n=9$，$k=3$，那么赛博奴隶主的实际血量为 $(1^3 + 3^3 + 9^3) \bmod (10^9+7) = 757$。

你现在需要做的就是求出赛博奴隶主的血量，然后带领帕鲁们一起打败他！让我们解放帕鲁吧！

图片描述

输入格式

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

接下来 $t$ 行，每行输入 $2$ 个正整数 $n,k$，其中 $n$ 表示赛博奴隶主的血条，$k$ 表示 $k$ 次方的血量转化比。（$1\leq n,k \leq 10^{18}$）。

输出格式

输出 $t$ 行，每行包含一个正整数，表示对应赛博奴隶主真实的血量，注意！这个结果是对 $10^9+7$ 取模后的结果。

样例输入

3
3 1
4 2
4 1

样例输出

4
21
7

说明

对于样例：

$4=1+3$。

$21=1+4+16$。

$7=1+2+4$。

T8. 取气球【算法赛】

问题描述

为庆祝蓝桥周赛的举办，大厅中挂满了 $n$ 个填充空气的气球。第 $1$ 号气球被粘在天花板上，其他气球则用绳子挂在比它编号小的气球上。为了防止气球被扯破，每个气球上方最多只能连着一根绳子。

小明觉得气球太多了，于是决定拿走一些。小明有两种方式可以拿走气球：

1. 割断一根绳子，这根绳子下方的所有气球都会掉落。小明可以将这些气球全部拿走。
2. 戳破一个气球，这根气球下方的所有气球都会掉落。当然，被戳破的气球本身是无法拿走的。

由于主办方财大气粗，每一根绳子和每一个气球都采用了不同的材料。对于第 $i$ 根绳子，小明需要花费 $w_i$ 的力气来割断它。对于第 $j$ 个气球，小明需要花费 $a_j$ 的力气来戳破它。

小明最多能使出 $W$ 点力气，他想知道他最多能拿走多少个气球。

输入格式

第一行包含两个整数 $n,W$，代表有 $n$ 个气球, 小明最多能使出 $W$ 点力气。（$1\leq n,W \leq 5000$）。

接下来一行包含 $n$ 个整数 $a_1,a_2,…,a_n$，表示戳破每个气球需要的力气。（$1\le a_i\le 5\times10^3$）。

接下来 $n-1$ 行每行包含 $2$ 个整数 $\lbrace u_i,w_i\rbrace$ , 表示编号为 $i+1$ 的气球上端连着第 $u_i$ 个气球，割断这根绳子需要 $w_i$ 点力气。（$1\le u_i\le n,1\le w_i\le 5\times 10^3$）。

输出格式

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

样例输入

8 6
9 6 1 2 1 1 2 1
1 5
1 1
1 5
2 2
2 1
4 1
4 2

样例输出

5

说明

花 $2$ 点力气割断第气球 $2$ 和气球 $5$ 之间的绳子，获得 $5$ 这一个气球。

花 $1$ 点力气割断第气球 $2$ 和气球 $6$ 之间的绳子，获得 $6$ 这一个气球。

花 $1$ 点力气割断第气球 $1$ 和气球 $3$ 之间的绳子，获得 $3$ 这一个气球。

花 $2$ 点力气割戳破气球 $4$，获得 $7$ 和 $8$ 两个气球。

故样例输出 $5$ 。

T9. 最后的加 k【算法赛】

问题描述

现在有一个正整数 $n$ ，你需要对他进行 $k$ 次操作，每次操作需要在其十进制每一位上加上 $x$ 形成一个新的数。

例如 $n=114,k=2,x=3$ ，第一次 $n=447$ ，第二次 $n=7710$，$10$ 是由 $7+3$ 得来的。

现在给定你 $n,k,x$，你需要求出操作结束后这个数的长度，由于这个结果很大，你需要对 $1000000007$ 取模。

输入格式

第一行输入两个正整数 $t，x$ ，表示测试案例的组数以及十进制每一位需要加的数。 （$1\le t\le 2\times 10^4,1\le x\le 10^9$）。

接下来 $t$ 行，每行输入两个正整数 $n,k$ ，表示给定的正整数 $n$ 以及操作次数 $k$。（$1\le n,k\le 10^9$）。

输出格式

输出 $t$ 行，每行一个正整数 ，为对 $1000000007$ 取模后的结果。

样例输入

3 2
1234 1
5 4
114 514

样例输出

4
2
621940455

说明

$1234$ 经过 $1$ 次变换成为 $3456$。

$5$ 经过 $4$ 次变换成为 $33$，$5\rightarrow 7 \rightarrow 9\rightarrow 11 \rightarrow33$。