0615 第 13 场 小白入门赛/强者挑战赛

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

T1. 延续端午【算法赛】

问题描述

五月初五，粽叶飘香，龙舟竞渡，热闹非凡。端午节，是传承千年的传统节日。 粽情端午，欢乐共享。正是这悠久的历史文化，造就了我们丰富多彩的民俗。

尽管此刻已经过了端午节，但那份欢乐的氛围和传统的魅力仍然令人难以忘怀。对此，蓝桥云课专门准备了一份礼物，来延续端午节的美好记忆。

请你输出 55，领取这份礼物！

输入格式

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

输出格式

输出一个数字，领取礼物。

T2. 宣读数字【算法赛】

问题描述

小蓝和小桥决定用一个数学游戏来比拼出谁的数学更好。游戏规则是围绕一个给定的正整数 $N$ 展开的，小蓝首先开始，两人轮流进行以下操作：

• 从 $N$ 的正约数中选择一个还未被宣读过的数并宣读它，即不能选择已经被对方或自己宣读过的数。

率先宣读出数字 $N$ 的玩家将被判定为输家。

请问，在双方都采取最优策略的情况下，谁会是最终的输家。

输入格式

输入的第一行是一个整数 $T$（$1 \leq T \leq 1000$），表示测试数据的组数。

接下来的 $T$ 行，每行包含一个整数 $N$（$1 \leq N \leq 10^{18}$）。

输出格式

对于每组测试数据，输出一个字符 L 或 Q，L 表示小蓝会输，Q 表示小桥会输。

样例输入

2
1
2

样例输出

L
Q

样例说明

在第一组样例中，$N = 1$，小蓝只能宣读 $1$，因此小蓝输了。

在第二组数据中，$N = 2$，小蓝可以宣读 $1$，而后小桥只能宣言 $2$，因此小桥输了。

T3. 最大质因子个数【算法赛】

问题描述

给定一个正整数 $N$，请你在 $2$ 到 $N$ 之间找到拥有不同质因子个数最多的整数，并求出该整数的不同质因子的个数。

输入格式

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

接下来 $T$ 行，每行包含一个正整数 $N$（$2 \leq N \leq 10^{18}$），表示要求解的范围。

输出格式

对于每个测试用例，输出一个整数，表示在 $2$ 到 $N$ 之间拥有最多不同质因子的整数的质因子个数。

样例输入

1
7

样例输出

2

样例说明

在 $2\sim 7$ 中：

• $2$ 的质因子有： $[2]$。

• $3$ 的质因子有： $[3]$。

• $4$ 的质因子有：$[2]$。

• $5$ 的质因子有：$[5]$。

• $6$ 的质因子有：$[2,3]$。

• $7$ 的质因子有：$[7]$。

因此，$6$ 是 $2\sim 7$ 中不同质因子个数最多的整数，其拥有的不同质因子个数为 $2$。

T4. 物流选址【算法赛】

问题描述

在全球化的商业环境中，蓝蓝公司与桥桥公司正寻求通过合作来优化其供应链管理。其中，蓝蓝公司位于地点 $P$，而桥桥公司位于地点 $Q$。

由于地理和政策限制，两公司不能直接进行货物交换。因此，他们计划通过一个第三方物流中心，来协调物流活动。为了确保物流效率，他们希望该物流中心的地点位置（记为 $Y$） 能够满足：$Q + Y$ 是 $P + Y$ 的倍数。

请帮助蓝蓝公司和桥桥公司找到满足条件的最小非负整数 $Y$。如果不存在这样的 $Y$，则输出 $-1$。

输入格式

第一行包含一个整数 $T$（$1\leq T \leq 100$），表示测试用例的数量。

对于每个测试用例，包含一行两个整数 $P$ 和 $Q$（$1\leq P \leq Q \leq 10^9$），表示蓝蓝公司和桥桥公司所在的地点编号。

输出格式

对于每个测试用例，输出一个非负整数，表示满足条件的最小 $Y$ 值。如果不存在这样的 $Y$，则输出 $-1$。

样例输入

3
2 3
3 7
5 10

样例输出

-1
1
0

T5. 小蓝的 MEX 问题【算法赛】

问题描述

对于一个给定的整数集合 $S$，$\text{MEX(S)}$ 定义为不属于 $S$​ 的最小非负整数。

例如：对于集合 $S=\lbrace 0,1,2,4 \rbrace$，$\text{MEX(S)} = 3$，因为 $3$ 是最小的未出现在集合 $S$​ 中的非负整数。

现在小蓝有一个大小为 $N$ 的可重集 $S$，同时他会给出 $Q$ 个询问，每次询问将会给出一个整数 $K$，请你回答有多少个不同的非空集合 $A$ 满足以下要求：

• $\text{MEX(A)}=K$。
• $A$ 是 $S$ 的子集，即满足 $A \subseteq S$​​​。

由于答案可能很大，你需要将答案对 $998244353$​ 取模后进行输出。

注意：若两个集合的数在 $S$ 中所属的下标不同，则视为不同的集合。

输入格式

第一行输入两个整数 $N,Q(1 \leq N,Q \leq 10^5)$ 表示集合 $S$ 的大小和询问的数量。

第二行输入 $N$ 个整数 $S_1,S_2,S_3,\cdots ,S_n(0 \leq S_i \leq N-1)$ 表示集合 $S$。

接下来 $Q$ 行，每行输入一个整数 $K(0 \leq K \leq N)$ 表示询问。

输出格式

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

输入样例

5 3
0 1 2 3 3
2
4
5

输出样例

4
3
0

说明

对于第二个查询 $K=4$ 时，集合 $\lbrace S_1,S_2,S_3,S_4\rbrace$，$\lbrace S_1,S_2,S_3,S_5\rbrace$，$\lbrace S_1,S_2,S_3,S_4,S_5\rbrace$ 符合条件。

T6. 平摊购买费用【算法赛】

问题描述

小蓝和小桥是两位购物狂热者，常常一起探索城市中的各种商店。这一天，他们来到了一家新开张的艺术画廊，画廊里摆放着 $n$ 幅不同的绘画作品，每幅作品都有其售价 $c_i$。

小蓝和小桥决定一同购买 $m$ 幅绘画作品，为了平摊购买费用，小桥提出了一种支付方案：

• 如果一幅绘画作品的售价低于 $k$ 元，小蓝将全额支付。
• 如果一幅绘画作品的售价高于或等于 $k$ 元，小蓝支付 $k$ 元，小桥支付剩余的部分（即 $c_i - k$ 元）。

设 $l$ 为小蓝需要支付的总金额，$f$ 为小桥需要支付的总金额。由于，小蓝对小桥的支付方案感到不满，因此她希望通过巧妙地选择绘画作品，使得表达式 $l - f$ 的值尽可能小，以减轻彼此的负担。

现在，请帮助小蓝选择绘画作品，并计算在给定 $q$ 个不同的支付方案（由数对 $k_i$ 和 $m_i$ 组成）的情况下，表达式 $l - f$ 的最小值。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n, q \leq 10^5)$，分别表示绘画作品的数量和支付方案的次数。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$ $(1 \leq c_i \leq 10^9)$，表示每幅绘画作品的售价。

接下来的 $q$ 行，每行包含两个整数 $k_i$ 和 $m_i$ $(1 \leq k_i \leq 10^9, 1 \leq m_i \leq n)$，表示每种支付方案中的支付界限和购买的绘画作品数量。

输出格式

输出 $q$ 行，每行对应一个支付方案的结果，即在该方案情况下的最小 $l - f$ 值。

样例输入

3 1
3 5 8
5 1

样例输出

2

T7. 电力之城【算法赛】

问题描述

电力之城是蓝桥王国的核心城市，因为它产生的电能供给所有的城市使用。

电力之城的发电原理十分简单：城市中心总共摆放了 $N$ 根电力之柱，电力之柱有激活和关闭两种状态。如果相邻电力之柱的状态不一致，就会产生势能差，从而产生 $1$ 点电力，否则不产生电力。电力之城的总电能等于所有相邻电力之柱所产生的电力之和。

小蓝和小桥是电力之城的电力战士，负责提高电力之城的总电能。他们分别可以进行一种称为“翻转”的操作：

• 选择一个区间 $[L, R](1 \le L\le R \le N)$，并翻转该区间内所有电力之柱的状态（激活变为关闭，关闭变为激活）。

但是，两人必须保证每次操作后电力之城的总电能 增加。

由于这项工作非常枯燥，现在小蓝和小桥想知道，如果由小蓝先手，两人都采取最优策略进行“翻转”操作，率先无法进行操作的玩家将失败，那么谁将获胜？

请你帮忙解决这个问题。如果小蓝最终获胜则输出 lan，否则输出 qiao。

输入格式

第一行输入一个整数 $T(1 \leq T \le 1000)$ 表示测试用例的数量。

对于每个测试用例：

第一行输入一个整数 $N(1 \leq N \leq 1000)$​ 表示电力之柱的数量。

第二行输入一个长度为 $N$ 的二进制字符串 $S(S_i\in[0,1])$，若 $S_i$ 为 1 表示第 $i$ 根电力之柱为激活状态，若为 0 则为关闭状态。

输出格式

输出 $T$ 行，每行一个字符串表示答案。

输入样例

3
5
10010
3
111
1
0

输出样例

lan
lan
qiao

说明

对于第二个样例，电力之柱初始状态为 $111$，小蓝可以操作区间 $[2,2]$ 使得电力之柱状态变为 $101$，小桥无法继续进行 "翻转" 操作，小蓝获胜。

T8. 价值共性度【算法赛】

问题描述

在一座历史悠久的城市中，有一条名为 "历史大道" 的街道，沿街排列着 $n$ 座历史建筑，每座建筑的历史价值可以用一个整数来衡量，分别为 $a_1, a_2, \ldots, a_n$。

城市的文化部长决定为这条街道制作一本精美的纪念册，希望能够选取一段连续的建筑群，使得这些建筑的历史价值和共性最能体现这条街的特色。

为了评估一段建筑群的历史共性，文化部长提出了一个指标：建筑群的价值共性度。这个价值共性度由建筑历史价值的最大公约数 $g$ 和建筑历史价值的总和共同决定，计算公式为 $g \cdot (a_l + \ldots + a_r)$，其中 $l$ 和 $r$ 分别是选定建筑群的起始和结束位置。同时，为了保证纪念册的丰富性，文化部长要求至少选择 $k$ 座建筑。

现在，请你帮助文化部长找出一段连续建筑群，使得其价值共性度最大。

输入格式

第一行包含两个整数 $n, k \left(1 \leq k \leq n \leq 10^6\right)$，分别表示街道上建筑的数量和至少需要选择的建筑数量。

第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n \left(1 \leq h_i \leq 10^6\right)$，表示每座建筑的历史价值。

输出格式

输出一个整数，表示最大的价值共性度。

样例输入

3 2
2 2 1

样例输出

8

样例说明

最大的价值共性度为 $2 \times (2 + 2) = 8$。

T9. 小蓝的逆序对问题【算法赛】

问题描述

逆序对 指的是数组 $a$ 中满足以下条件的任意一对元素：

• 元素在数组中的位置分别为 $i,j$，且 $i< j$。
• 元素的值：$a_i > a_j$。

给定一个长度为 $n$ 的数组 $a$，小桥可以轻易地求出数组 $a$ 中的逆序对数量。然而，小蓝决定给小桥增加难度。

小蓝会给出 $q$ 次询问，每次询问包含两个下标 $(i, j)$。他想知道如果将下标 $i$ 和 $j$ 上的元素交换，数组 $a$​ 的逆序对数量会是多少？

这一下就将小桥问倒了，现在小桥请你来帮她解决这个问题。

注意：每次询问并不会真正交换下标 $i$ 和 $j$​ 上的元素。

输入格式

第一行输入两个整数 $n,q(1 \leq n,q \leq 2 \times10^5)$ 表示 $a$ 的长度和小蓝的询问次数。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(1 \leq a_i \leq 10^9)$ 表示数组 $a$​。

接下来 $q$ 行，每行输入两个整数 $i,j(1 \leq i \leq j \leq n)$ 表示一次询问。

输出格式

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

输入样例

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

输出样例

6
8
0