1111 第 3 场算法双周赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/challenge-3/
• 题解回放：https://bilibili.com/video/BV1j94y137rZ/

T1. 双十一的祈祷【算法赛】

问题描述

双十一，不仅是购物狂欢节，更有 "光棍节" 之称。这源于 $11:11$ 由四个 $1$ 构成，象征着单身。

作为大学生的小蓝也想经历甜甜的校园恋爱，于是他找到了爱神丘比特，向他祈祷能为自己带来一段邂逅。

丘比特是乐于助人的，他承诺小蓝只要回答出一个简单的数学问题，就完成小蓝的愿望。

问题是： $11^{1111}$ 的 个位数 是多少？

作为小蓝的好朋友，为了小蓝的幸福，请你帮忙解决这个问题。

注意：使用阿拉伯数字作答。

输入格式

本题为填空题，无需输入即可作答（当然如果你单身，你也可以读入一个字符串看看是否有惊喜）。

输出格式

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

提示

$1 \times 1 =1$。

T2. 疯狂的促销【算法赛】

问题描述

双十一到了，各大电商平台开始了促销活动的筹备。

作为购物狂人，小蓝提前在购物车里准备了 $N$ 件商品，每件商品都有一个售价 $w$ （在双十一之前，对于同一商品，各个平台的售价均相同）。

在双十一期间，三大电商平台（某猫，某东，某音）都推出了各自的折扣规则：

• 某猫：若某件商品的售价满足 $w \ge 500$，则购买该商品时减免 $\lfloor \dfrac{w}{10} \rfloor$ 。
• 某东：若某件商品的售价满足 $w \ge 1000$，则购买该商品时减免 $150$。
• 某音：购买任意商品时均可直接减免 $\lfloor \dfrac{w}{20} \rfloor$。特别地，当某件商品的售价（减免前）等于 $1111$ 时，该商品可以直接免单。

$\lfloor \rfloor$ 表示下取整，例如 $\lfloor \dfrac{1234}{10} \rfloor=123$。

小蓝可以在任意平台购买任意商品，请你帮他计算买齐全部商品的最少花费。

输入格式

第一行输入一个整数 $N$，表示小蓝想购买的商品总数。

第二行输入 $N$ 个空格分割的整数 $w_1,w_2,\cdots w_N$ 表示每件商品的价格。

输出格式

输出一个整数，表示小蓝买齐全部商品的最少花费。

样例输入

3
666 1200 1111

样例输出

1650

说明

第一件商品在某猫买，第二件商品在某东买，第三件商品在某音买，可以得到最低价：

$$(666-\lfloor\dfrac{666}{10}\rfloor)+(1200-150)+0=1650$$

评测数据范围

$1 \leq N \leq 10000$。

$20 \leq w_i \leq 2000$。

T3. 被替换的身份证【算法赛】

问题描述

由于沐风在前两次蓝桥杯周赛中表现不佳，因此被浅梦戏称为 Joker。现在，浅梦取来了两幅扑克牌，但将其中的大小王（大王 $\rightarrow$ Red Joker，小王 $\rightarrow$ Black Joker）替换成了沐风的身份证与身份证复印件。

于是现在扑克牌里的 Red Joker 变成：

图片描述

Black Joker 变成：

图片描述

扑克牌的游戏规则如下：

1. 单张扑克牌的大小顺序为：3<4<5<6<7<8<9<X<J<Q<K<A<2<M<F。
2. 两张相同的牌可以组成 '对子'，对子只能与对子比较，对子和单张无法互相响应，对子的大小关系为 33<44<55<66<77<88<99<XX<JJ<QQ<KK<AA<22<MM<FF。
3. MF 是最大的牌，也被称作 '王炸'，它能大于所有的对子和单张。
4. 当轮到某一方出牌时，出的牌必须比对手出的牌要大。如果无法响应对手出的牌，则由对手继续出牌。
5. 每一次出牌，玩家可以出单张、对子或王炸中的一种，但必须符合 $1,2,3,4$ 号规则。

现在浅梦和沐风从两副扑克牌中随机抽取两张牌，由浅梦先手。两人都采用最优策略出牌，最先出完所有牌的人获胜。若浅梦获胜，输出 ShallowDream；若沐风获胜，输出 Joker。你能判断谁会获胜吗？

输入格式

第 $1$ 行输入一个正整数 $T$，表示测试用例数量。

接来下 $T$ 行，每行输入 $2$ 个由空格隔开且长度为 $2$ 的字符串，第 $1$ 个字符串代表浅梦随机抽取的 $2$ 张牌，第 $2$ 个字符串代表沐风随机抽取的 $2$ 张牌。

输出格式

输出 $T$ 行，每行输出 $1$ 个字符串，如果浅梦获胜，则输出 ShallowDream；如果沐风获胜，则输出 Joker。

样例输入

2
22 MF
2X M3

样例输出

ShallowDream
Joker

说明

第一组测试案例：浅梦可以直接出 '对子'，从而出完所有牌获得胜利。

第二组测试案例：无论浅梦先手出哪一张牌，沐风只需使用 M 作为回应，浅梦便无法继续出牌，因此沐风获胜。

评测数据规模

$1\le T\le 15^4$。

数据保证，每个字符均只属于 3，4，5，6，7，8，9，X，J，Q，K，A，2，M，F。

T4. 迷宫逃脱【算法赛】

问题描述

在数学王国中，存在一个大小为 $N \times M$ 的神秘迷宫。第 $i$ 行第 $j$ 个位置坐标为 $(i,j)$，每个位置 $(i, j)$ （$1 \leq i \leq N, 1 \leq j \leq M$）都对应着一个正整数 $A_{i, j}$。迷宫的左上角坐标为 $(1,1)$，右下角坐标为 $(N,M)$。

小蓝初始位于坐标 $(1, 1)$，并携带着 $Q$ 把密匙。他的目标是移动到迷宫的终点，即坐标 $(N, M)$ 处。但是通往迷宫尽头的道路并不是一帆风顺的，在前进的过程中，他遇到了一些奇特的规则。

规则如下：

1. 小蓝每次只能向右移动一个位置或向下移动一个位置。

2. 当小蓝所在位置的数和下一步移动位置的数互质时，会有一扇封闭的铁门，小蓝需要消耗一把密匙来打开铁门，打开铁门后，这把钥匙将被摧毁。如果没有密匙，小蓝将无法移动到该位置。

你需要输出小蓝从起点到终点路径之和的最大值，如果无法从起点到达终点，输出 -1。

输入格式

第一行输入包含 $3$ 个整数 $N, M, Q$，分别为迷宫的大小和密匙的数量。

接下来输入 $N$ 行，每行 $M$ 个整数，为迷宫上的数值 。

输出格式

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

样例输入

3 3 1
2 6 7
1 3 9
5 6 8

样例输出

28

说明

对于样例，最优路径关系如下：

图片描述

在 $9\rightarrow 8$ 时消耗了一把钥匙。

评测数据规模

$1 \leq N, M \leq 1000$。

$0 \leq Q \leq 3$。

$1 \leq A(i, j) \leq 10^9$。

T5. 深秋的苹果【算法赛】

问题描述

当深秋的苹果树丰收时，村庄的居民们兴致勃勃地采摘着红彤彤的苹果。他们将采摘下来的 $N$ 个苹果排成了一排，形成了一个苹果序列 $A$，第 $i$ 个苹果的甜度值为 $A_i$（$1\le i\le N$）。

现在村民需要将苹果序列划分为连续的 $M$ 段，对于分割后的某一段 $A_{l\sim r}$，定义其美味值表示为该段内不同下标的苹果的甜度两两相乘的总和，即 $\sum_{i = l}^{r}\sum_{j =i + 1}^{r}A_i\cdot A_j$。

注：如果某一段只有一个苹果，它的美味值为 $0$。

请问应当如何给苹果分段，才能使得美味值最大的一段尽可能小，你只需要输出这个最大美味值可能的最小值即可。

输入格式

第 $1$ 行输入 $2$ 个正整数 $N, M$，分别为苹果序列的长度和需要分成的段数。

第 $2$ 行输入 $N$ 个空格隔开的正整数，表示苹果序列。

输出格式

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

样例输入

6 3
1 4 7 2 5 8

样例输出

39

说明

我们可以把苹果序列分成 $\text{[1,4,7],[2,5],[8]}$，这样最大的一段美味值为 $39$，是最小的分法。

评测数据规模

$1 \leq M \leq N \leq 200000$。

$1 \leq A_i \leq 10000$。

T6. 鲜花之海【算法赛】

问题描述

在一个幻想的王国中，有一个美丽的花园，花园里开满了各种不同颜色的鲜花。现在花园里一共有 $N^2$ 朵鲜花，这些鲜花都有一个独特且 唯一 的编号，编号由 $(a,b)(1\le a,b\le N)$ 两个数字组成。

这些鲜花按如下规则摆放在花坛中（花坛可以视作一条直线）：

1. 如果第 $X$ 朵鲜花的编号之和 $(X_a+X_b)$ 小于第 $Y$ 朵鲜花编号之和 $(Y_a+Y_b)$ ，则 $X$ 朵鲜花放在 $Y$ 朵鲜花前面。
2. 如果第 $X$ 朵鲜花的编号之和 $(X_a+X_b)$ 等于第 $Y$ 朵鲜花编号之和 $(Y_a+Y_b)$ ，则哪一朵鲜花的编号 $a$ 更小，哪一朵鲜花就摆在前面。

现在小蓝需要找到花园中的第 $K$ 朵鲜花，但鲜花实在是太多了，他不想一朵朵的去找，你可以快速的告诉他第 $K$ 朵鲜花的编号吗。

输入格式

第一行输入一个正整数 $T$，表示 $T$ 组数据。

接下来 $T$ 行，每行输入两个正整数 $N,K$，含义如题所述。

输出格式

输出 $T$ 行，每行包含 $2$ 个由空格隔开的正整数 $(a,b)$，为符合题目要求的第 $K$ 朵鲜花的两个编号。

样例输入

1
2 3

样例输出

2 1

说明

四朵鲜花的编号按顺序排列关系如下：

图片描述

评测数据规模

$1\le T\le 10^5,1\le N \le 10^{9},1\le K\le N^2$。

T7. 斐波拉契跳跃【算法赛】

问题描述

小蓝和小桥在玩一个数学游戏，游戏规则如下：

有一个长度为 $n$ 的 排列 $a$ 和一个棋子，两个人轮流按照游戏规则在排列上移动这个棋子，由小蓝先手，最先不能移动棋子的人判为输。

对于某一次移动，设棋子的移动起点为 $i$ ，移动的终点为 $j$，两人移动棋子均需要满足以下游戏规则：

1. $a_i < a_j$。
2. 移动的步长必须是斐波拉契数。在这道题中我们对斐波拉契数的定义为无穷集合 $1, 2, 3, 5, 8 \cdots$，即满足 $f[1]=1, f[2]=2,...,f[n]=f[n-1]+f[n-2]$。
3. 棋子每次走的步长需满足递增关系。假设上一次移动是从 $i'$ 到 $j'$，那么需要满足关系 $|i-j| >|i'-j'|$。

现在小蓝和小桥要进行 $n$ 轮游戏，第 $i$ 轮棋子的初始位置在 $i$（$1\le i\le n$）。对于每一轮游戏，在双方都采用最佳策略的情况下，你需要确定谁将获胜。请注意，棋子的移动是有限的，意味着最终总会有一方获胜。

排列：对于一个长度为 $n$ 的序列，其中 $1\sim n$ 均出现一次。

输入格式

第 $1$ 行输入一个正整数 $n$，代表小蓝和小桥拥有的排列的长度。

第 $2$ 行输入 $n$ 个正整数，表示 $a_1,a_2,…,a_n$ 排列中的每个数。

输出格式

输出 $n$ 行字符串，第 $i(1\le i\le n)$ 个字符串表示：棋子初始位置为 $i$，如果小蓝必胜有必胜的方式，则输出 "Little Lan"，如果小桥有必胜的方式，则输出 "Little Qiao"。

样例输入 1

8
3 6 5 4 2 7 1 8

样例输出 1

Little Lan
Little Qiao
Little Lan
Little Lan
Little Lan
Little Lan
Little Lan
Little Qiao

说明

对于样例 $1$，开始时，小蓝在 $1$ 号位置，他选择斐波拉契数 $5$ 为移动距离，移动棋子到第 $6$ 个位置，该位置上的数为 $7$，则下个回合小桥无法移动棋子，小蓝胜。

红色部分为小蓝可以选择移动的位置，第一个蓝色部分为小蓝的起点，第二个蓝色部分为小蓝选择可以先手必胜的位置。

图片描述

评测数据规模

对于 $100$% 的评测数据，$1 \leq n \leq 100000$，$1 \leq a_i \leq n$。

此外，不存在一对索引 $i \ eq j$ 使得 $a_i = a_j$。

T8. 星石传送阵【算法赛】

问题描述

有 $n$ 个传送阵，编号为 $1\sim n$，每个传送阵使用若干块 "星石" 作为能源。"星石" 是一种很神奇的物质，一块 "星石" 的 能量值等于它的价值。同时，星石放在一起会激发更强大的能量，例如：有 $3$ 块 "星石" 的能量值分别为 $2,3,4$，则它们放在一起可以提供的能量为 $2\times 3\times4=24$，需要消耗的价值为 $2+3+4=9$。

现在每个传送阵都有一个能量值 $x$， $f(x)$ 是构成 $x$ 的星石最小价值之和对 $n$ 取模加一，换句话说便是 $f(x)=(\text{sum}\bmod n)+1$，$\text{sum}$ 是构成 $x$ 的星石最小价值之和。

例如：

$x=9,n=997,f(x)=(3+3)\bmod 997+1=7$。

而两个传送阵可以相互传送的规则如下：

1. 如果两个传送阵的 $f(x)$ 相等，则两个传送阵可以相互传送。例如 $n>6,x=8,x=9$ 便可以相互传送。
2. 能量值为 $x$ 的传送阵可以和 编号 为 $f(x)$ 的传送阵相互传送。例如 $n>6,a[4]=9$（$a[4]$ 是假设 $4$ 号传送阵能量为 $9$），所以 $4$ 号传送阵可以和 $7$ 号传送阵能相互传送。因为 $4$ 号传送阵的能量值为 $9$，$f(x)=(3+3 \bmod n) +1=7$。

给定每个传送阵都有的能量值 $x$，你需要求出从编号 $a$ 到编号 $b$ 的最少传送次数，若不能到达，请输出 $\text{-}1$。

输入格式

第 $1$ 行输入 $3$ 个正整数，表示 $n,a,b$，含义为传送阵的数量，起点编号与终点编号。

第 $2$ 行输入 $n$ 个正整数 $x$，表示每个传送阵的能量值。

输出格式

输出 $1$ 行，表示 $a$ 到 $b$ 的最少传送次数，若不能从 $a$ 传送到 $b$ 则输出 $\text{-}1$。

样例输入

4 1 4
9 8 7 6

样例输出

2

说明

形成的图如下所示：

图片描述

红色线为 $f(x)$ 相同互相连接，绿色的线为编号为 $f(x)$ 互相连接。

$1$ 号点到 $4$ 号点可以 $1\rightarrow 3\rightarrow 4,1\rightarrow 2\rightarrow 4$，有二种方式可以到达 $4$ 号点，均是最优路径走法。

评测数据规模

$2\le n \le 10^5,2\le x\le10^8,1\le a,b\le n$。