0208 第 26 场 蓝桥入门赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/newbie-26/
• 题解回放：

T1. 蛇年大吉【算法赛】

问题描述

“老爸，过年好！今年是蛇年，咱家贴啥春联啊？” 小蓝问。

老爸捋了捋胡子：“贴啥春联？当然要贴和蛇有关的！嗯…让我想想…有了！上联：金蛇狂舞辞旧岁，下联：银蛇飞舞迎新年，横批：蛇年大吉！”

小蓝撇撇嘴：“爸，你这春联也太没创意了吧！能不能来点儿新鲜的？要不，咱们贴个英文的？”

老爸一愣：“英文的？这我可不会啊。要不这样，你给我出一个和蛇有关的英文单词，我把它拆开，每个字母都代表一个祝福，怎么样？”

小蓝坏笑了一下：“好啊！就用 snake 这个词吧！你看看，每个字母都能代表啥祝福？”

老爸挠挠头：“s…s 代表…身体健康！n…n 代表…年年有余！a…a 代表…爱情甜蜜！k…k 代表…开开心心！e…e 代表…呃…嗯…发大财！”

小蓝哈哈大笑：“爸，你这祝福也太牵强了吧！不过，既然你这么努力了，我就勉强接受吧！只不过，为了考验你对蛇的了解，你还得告诉我，如果把 snake 这个单词的字母按照字母表顺序重新排列，组成的新单词是什么？”

输入格式

无。

输出格式

一个字符串，表示重新排列后的单词。

T2. 对联【算法赛】

问题描述

大年三十，小蓝和爷爷一起贴对联。爷爷拿出了两副对联，每副对联都由 $N$ 个 "福" 字组成，每个 "福" 字要么是正的（用 $1$ 表示），要么是倒的（用 $0$ 表示）。

爷爷说："小蓝啊，这两副对联可以随意调整 '福' 字的顺序。我们要让上下联的 '福' 字对应位置的 '福气值' 达到最大。'福气值' 的计算方法是：正正相对得 $0$，正倒相对得 $1$，倒正相对得 $1$，倒倒相对得 $0$。"

小蓝挠了挠头："爷爷，这不就是二进制异或运算吗？"

爷爷笑着点点头："没错！现在给你两串 '福' 字的初始排列，你能算出通过最优调整后，最大的总福气值是多少吗？你只需要告诉爷爷最大的总福气值在二进制情况下 $1$ 的个数即可"

小蓝感觉略微有点困难，于是请你帮忙解决这个问题。

输入格式

第一行输入一个整数 $N(1 \leq N \leq 10^3)$，表示每幅对联中 "福" 的数量。

第二行输入一个长度为 $N$ 的 $01$ 字符串 $S$ 表示第一幅对联的初始排列。

第三行输入一个长度为 $N$ 的 $01$ 字符串 $T$ 表示第二幅对联的初始排列。

输出格式

输出一个整数表示答案。

样例输入

4
0011
1011

样例输出

3

T3. 电子舞龙【算法赛】

问题描述

话说这年头，连舞龙都得电子化！这不，蓝桥村的老程序员王大爷突发奇想，用 LED 灯带和一堆传感器鼓捣出了一条“电子舞龙”，它能根据程序指令在村里的广场上“翩翩起舞”。

广场被王大爷抽象成一个二维坐标系，龙头从坐标原点 $(0, 0)$ 出发，根据接收到的指令移动：

• L - 龙头向左移动一格。
• R - 龙头向右移动一格。
• U - 龙头向上移动一格。
• D - 龙头向下移动一格。

秉承着“龙归故里，新年新气象”的寓意，王大爷希望龙头在完成一系列眼花缭乱的舞动后，能够精准地回到最初的起点 $(0, 0)$。

然而，计划赶不上变化，就在演出即将开始之际，一个熊孩子趁王大爷不注意，偷偷修改了电子舞龙的控制指令！这下可好，原本完美的程序被改得乱七八糟，龙头跳完舞后，估计得跑到隔壁村去拜年了！

王大爷拿到被熊孩子涂改过的指令，他知道其中有一些指令是错误的，需要修改一些指令才能让电子龙回到原点。例如，他可以把 L 指令改成 R，或者把 U 改成 D，诸如此类。

现在，请你帮助王大爷计算出最少需要修改多少次指令，才能让电子龙头顺利回到起始点 $(0, 0)$。如果无论怎么改都无法回到起始点，请输出 $-1$（这意味着今年的电子舞龙表演可能得换成传统的舞狮了 🦁️）。

输入格式

输入一行，包含一个仅由 L、R、U、D 所构成字符串 $S$（$1 \leq |S| \leq 10^5$），表示被熊孩子修改过的错误指令。

输出格式

输出一个整数，表示最少需要修改的指令次数。如果无论如何都无法回到起始点，输出 $-1$。

样例输入

LLUU

样例输出

2

T4. 舞狮【算法赛】

问题描述

舞狮是中国传统民间艺术，起源于汉代，盛行于唐代。它结合了武术、舞蹈和音乐，常在节日和庆典中表演，象征驱邪避灾、带来好运。表演者通过模仿狮子的动作，展现狮子的喜怒哀乐，常伴有锣鼓音乐，增添喜庆氛围。

如果一支舞狮队中，从狮头开始，每位成员的舞狮技能值严格大于其前面所有成员的数量，那么这支舞狮队被称为合理的舞狮队。例如 $[1,2,3,4],[2,3,5]$ 是合法的舞狮队，$[1,3,1],[2,1,3]$ 则不是合法的舞狮队。

新年即将到来，蓝桥村今年的舞狮队共有 $N$ 名成员，第 $i$ 名成员的舞狮技能值为 $A_i$。舞狮队教练小蓝需要将这 $N$ 名成员合理地分组形成舞狮队，他想知道最少需要分成多少队，请你帮忙解决这个问题。

注意：你必须保证每位成员至少被分到一个舞狮队。

输入格式

第一行输入一个整数 $N(1\leq N \leq 10^5)$ 表示舞狮队成员的数量。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq N)$ 表示每位成员的舞狮技能值。

输出格式

输出一个整数表示答案。

样例输入

5
1 3 5 2 1

样例输出

2

说明

对于样例，可以分为 $[1,2,3]$ 和 $[1,5]$，至少需要分成两支舞狮队。

T5. 扑克较量【算法赛】

问题描述

在中国，新年（春节）是最重要的传统节日之一，人们通常会与家人团聚，享受节日的喜庆氛围。除了吃年夜饭、看春晚、放鞭炮等传统活动外，打扑克也是春节期间非常受欢迎的娱乐活动之一。

小蓝最近新学了一个有关扑克牌的新玩法，游戏规则如下：

给定两个整数 $N$ 和 $K$，以及 $N$ 张扑克牌，其中第 $i$ 张牌的数值为 $A_i$。你可以进行任意次操作，每次操作可以选择一张牌并将其数值增加 $K$。在进行了若干次操作（可以为零）后，扑克牌中的最大值减去最小值的差最小为多少？

小蓝希望作为荷官发牌，以测试好友们的计算能力。作为小蓝最聪明的朋友之一，请你尝试编写程序快速计算出答案。

输入格式

第一行包含两个整数 $N(1 \leq N \leq 10^5)$ 和 $K(1 \leq K \leq 10^9)$，分别表示扑克牌的数量和每次增加的数值。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N(1 \leq A_i \leq 10^9)$，表示每张扑克牌的初始数值。

输出格式

输出一个整数表示答案。

样例输入

5 2
1 3 5 7 10

样例输出

1

T6. 春晚魔术【算法赛】

问题描述

在蓝桥卫视春晚的直播现场，魔术师小蓝表演了一个红包魔术。只见他拿出了三个红包，里边分别装有 A、B 和 C 个金币。而后，他挥动魔术棒，念动咒语“福禄寿喜财神到～”，对红包里的金币进行 $N$ 次变换。每次变换，每个红包的金币数量都会变成其他两个红包金币数量的乘积。

例如：

• 初始金币数量 $A=2$，$B=3$，$C=5$，进行 $N=1$ 次变换后，金币数量变为 $15$，$10$，$6$。
• 初始金币数量 $A=1$，$B=2$，$C=3$，进行 $N=2$ 次变换后，金币数量变为 $6$，$12$，$18$。

变换结束后，小蓝得意地问观众：“现在，你们知道三个红包里金币的总乘积是多少吗？” 他飞快地心算了一下，并报出一个数字：“让我来揭晓答案吧！总乘积是…嗯…（不知道算没算对，只知道算得快）”。

作为观众，请你计算 $N$ 次变换后，三个红包金币数量的总乘积。由于结果可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

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

接下来的 $T$ 行，每行包含四个整数 $A$，$B$，$C$ 和 $N$（$1\leq A,B,C,N \leq 10^9$），表示一组数据。

输出格式

对于每组数据，输出一个整数，表示 $N$ 次变换后三个红包金币数量的总乘积。由于结果可能很大，请输出其对 $10^9 + 7$ 取模的结果。

样例输入

2
2 3 5 1
1 2 3 2

样例输出

900
1296