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

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

T1. thanks,mom【算法赛】

问题描述

母爱是宇宙中最柔和的力量，是一种无私奉献的奇迹。它如同一束温暖的阳光，照亮着我们前行的道路。母爱是一首催人泪下的歌曲，奏响着无尽的关怀和呵护。它如同一幅绚丽的画卷，展现着无限的包容和理解。

母爱是一种奇迹，它孕育着生命，滋养着希望。母亲用无私的爱将我们抚养成人，用坚定的支持给予我们力量。她们默默付出，从不求回报，只为了我们能幸福成长。母爱是一种力量，它赋予我们勇气去追逐梦想，给予我们安全感和温暖的怀抱。

让我们感谢母亲的辛勤付出和无私奉献，向那些为了我们的幸福而默默奉献的母亲们表达崇高的敬意。她们是我们生命中最重要的人，是我们永远的依靠和支持。让我们珍惜与母亲在一起的每一刻时光，用爱和感激回报她们的付出。

昨天是三八妇女节，请你输出 thanks,mom 向自己的母亲表示感激。

因为网络波动原因，本场赛后会对此题重新评测。感谢各位的参与，加油！

输入格式

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

输出格式

输出一个字符串表示答案。

T2. 霓虹【算法赛】

问题描述

晚上，小蓝正无聊的走在大路上，小蓝所在的街区是一个带有赛博朋克风格的街区。

他抬头一看，看到了很多霓虹灯牌。在其中的某一个店铺前，挂着一排的数字灯牌，每一个数字的显示都依靠 $7$ 段 LED 管，亮着的灯管组成数字，具体来说如下图所示：

图片描述

小蓝刚学过数字电路，他知道具体的工作原理如下：

图片描述

在思考的过程中，他发现数字发生了变化。他想要知道，在数字变化的过程中，总共有多少根灯管的状态产生了变化？

例如，从显示数字 $0$ 到显示数字 $6$，会有一个灯管熄灭，一个灯管点亮，那么总共有两根灯管发生了变化。

具体来说，当前的数字串是 $A$，一秒钟之后，数字串变成了 $B$，小蓝想知道，在数字跳转的过程中，有多少个灯管的状态发生了变化。

输入格式

输入共两行，包含两个等长字符串。

第一行包含一个字符串 $S$（$|S| \le 10^5$），代表一开始的数字串。

第二行包含一个字符串 $T$（$|T| \le 10^5$），代表跳变后的数字串。

输出格式

一个整数，代表跳变过程中变化的灯管数量。

样例输入

01
56

样例输出

9

说明

跳变过程如题干中的图片。

$0 \to 5$ 变化了 $3$ 根灯管，$1 \to 6$ 变化了 $6$ 根灯管，共变化 $9$ 根灯管。

T3. 奇偶排序【算法赛】

问题描述

小蓝所在的王国名为偶数王国，在他们王国中数字的比较通常按以下步骤进行：

• 如果两个数字的奇偶性不同，那么偶数一定大于奇数。
• 如果两个数字的奇偶性相同，则比较它们的实际数值大小。

现在给你一个正整数数组 $A$，请你输出按照偶数王国规则从小到大排序后的 $A$。

输入格式

第一行输入一个整数 $N(1 \leq N \leq 10^3)$ 表示数组 $A$ 的长度。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 10^5)$ 表示数组 $A$。

输出格式

输出一行 $N$ 个整数表示答案。

样例输入

5
1 2 3 4 5

样例输出

1 3 5 2 4

T4. 可结合的元素对【算法赛】

问题描述

小蓝和小桥是蓝桥学院中学业成绩最好的两位同学。一天，小蓝向小桥提出了一个问题，希望小桥能够展示她最新学到的知识。问题是这样的：

给定一个长度为 $N$ 的数组 $A$，如果一对下标 $(i, j)$ 满足以下规则，那么称它们为可结合的元素对：

• $1 \leq i < j \leq N$。
• $\text{lowbit}(a_i + a_j) = a_i + a_j$ ，其中 $\text{lowbit}(x)$ 表示 $x$ 的二进制表示中最低位的 $1$ 的值。

小蓝希望小桥能够计算出数组 $A$ 中可结合的元素对的数量，但小桥无法解决这个问题，只能请你帮忙了。

输入格式

第一行输入一个整数 $N(2 \leq N \leq 10^5)$ 表示数组 $A$ 的长度。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 10^9)$ 表示数组 $A$。

输出格式

输出一个整数表示答案。

样例输入

5
2 4 6 7 8

样例输出

1

样例说明

只有下标对 $(1,3)$ 符合条件。

T5. 兽之泪【算法赛】

问题描述

图片描述

在蓝桥王国，流传着一个古老的传说：在怪兽谷，有一笔由神圣骑士留下的宝藏。

小蓝是一位年轻而勇敢的冒险家，他决定去寻找宝藏。根据远古卷轴的提示，如果要找到宝藏，那么需要集齐 $n$ 滴兽之泪，同时卷轴中也记载了，每击败一次怪物，就能够收集一滴兽之泪。

小蓝知道，这些怪物并非泛泛之辈，每一只都拥有强大的力量和狡猾的技巧。每一只怪物都有它独特的弱点和对策，小蓝必须谨慎选择战斗的策略和使用的能量。

在怪兽谷中，有 $k$ 只怪兽。对于第 $i$ 只怪兽，第一次击败他需要 $x_i$ 点能量，后续再击败他需要 $y_i$ 点能量，由于怪兽吃了亏，所以有所准备，可以得到 $y_i \ge x_i$。在挑战过程中，前 $k-1$ 只怪兽可以随意挑战，但是第 $k$ 只怪兽是怪兽之王，如果要挑战第 $k$ 只怪兽，那么对于前 $k-1$ 只怪兽都要击败至少一次。

小蓝想知道，如果要集齐 $n$ 滴兽之泪，那么至少需要多少能量。

输入格式

第一行包含两个整数 $k$ 和 $n$（$2 \le k \le 10^5, 1 \le n \le 2 \times 10^5$），表示怪物的数量和需要收集的兽之泪的数量。

接下来 $k$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le y_i \le 10^9$），表示第 $i$ 只怪物第一次和后续击败所需的能量。

输出格式

输出一个整数，表示小蓝至少需要多少点能量才能收集完成。

样例输入

3 4
2 4
4 5
1 1

样例输出

8

说明

一种可行的方案是：

1. 第一次选择 $1$ 号怪物，消耗能量 $2$。
2. 第二次选择 $2$ 号怪物，消耗能量 $4$。
3. 由于 $1,2$ 都已经击败一次，所以可以选择 $3$ 号，第三次选择 $3$ 号怪物，消耗能量 $1$。
4. 第四次选择 $3$ 号怪物，消耗能量 $1$。

T6. 矩阵 X【算法赛】

问题描述

小蓝面对一个 $n \times m$ 的矩形 $D$，其中每个位置 $(i, j)$ 上都有一个元素 $x_{i,j}$。

我们定义两个函数 $f(D)$、$g(D)$，$f(D)$ 的值为矩阵 $D$ 的所有元素的和值，$g(D)$ 为矩阵 $D$ 的极差，即矩阵中的最大值减去最小值。

他需要在这个矩形中选择一个 $n' \times m'$ 的连续子矩阵，记为矩阵 $D'$，他希望选择的连续子矩阵 $D'$ 能够使得 $f(D') \times g(D')$ 最大化。

小蓝知道你很聪明，于是他把问题交给了你，希望你回答他最大化的值是多少。

连续子矩阵：是在原矩阵选取部分连续行、连续列所组成的新矩阵。

输入格式

第一行包含四个整数 $n,m,n',m'$（$n\times m \le 10^6, 1 \le n' \le n, 1 \le m' \le m$），表示矩形的行数和列数，以及你需要选择的子矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示矩形中每个位置的元素值 $x_{i,j}$（$1 \le x_{i,j} \le 10^6$）。

输入量较大，建议采用较快的输入输出方式。

输出格式

一个整数，代表最大化的值。

样例输入

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

样例输出

78

说明

选择的连续子矩阵如下图黄色部分所示：

$f(D')=13, g(D')=6$。

图片描述

T7. 独特的串【算法赛】

问题描述

在神奇的蓝桥大陆，有一个古老的国家，蓝桥国。

国王是一个十分讲究的人，他准备为他的光辉一生留下一本回忆录（大致就是，国王做了什么为国为民的好事云云）。当然，国王是十分忙碌的，所以他将这个任务交给了撰文大臣，也就是你。

国王有 $m$ 个需要避讳的词汇，每个词汇用一个仅包含小写字母的字符串表示，国王如果看到这些词汇，就会非常的不开心。

但是这并不代表你的撰文中不能出现这些词汇，由于国王是一个很大度的人，所以如果你的撰文中仅仅只出现了一次避讳的词汇，那么国王也不会怪罪你。

这天是你的休息日，你还是收到了国王的任务，于是你十分的不开心，打算敷衍一下国王。你知道每篇撰文需要 $n$ 个字符，并且只包含小写字母。你想要随写一通，然后交给国王即可。这时候你开始思考，你最多可能写多少篇不同的撰文，以满足国王的要求。

具体来说，给一个包含 $m$ 个互不相同的字符串集合 $\lbrace s_1, s_2, ..., s_m \rbrace$ ，你需要构造一个长度为 $n$ 的字符串，使得在该串中最多只出现一次集合中的词汇，请问能构造出多少个不同的字符串。答案可能很大，请对 $998244353$ 取模。

输入格式

第一行包含两个整数 $m$ 和 $n$（$1 \le m \le 10^3, 1 \le n \le 5 \times 10^3$ ），表示字符串集合中字符串的数量和要构造的字符串的长度。 接下来 $m$ 行，每行包含一个字符串 $s_i$，表示字符串集合中的一个字符串。 数据保证 $\sum |s_i| \le 10^3$。

输出格式

输出一个整数，表示满足条件的不同字符串的数量，答案可能很大，请对 $998244353$ 取模。

样例输入

2 2
a
b

样例输出

672

说明

不合法的字符串：$\lbrace aa, bb, ab, ba \rbrace$。

所以答案为 $26 \times 26 - 4 = 672$。

T8. 食堂【算法赛】

问题描述

小蓝是个节俭而有品味的年轻人，每当他进入学校食堂，总是小心翼翼地选择着自己的菜肴。今天，他来到了一家新开的食堂，据说这里提供了各种美味的菜肴，而且还有一项特别的活动。

这家食堂共有 $k$ 种菜，每一种菜都有其独特的风味和口感。对于第 $i$ 种菜，价格是 $p_i$ 元每盘，而小蓝想要的份数是 $s_i$ 盘。不仅如此，食堂还举办了一个吸引人的活动：每购买 $2$ 盘同种菜，都会额外赠送一种异种菜。当然，小蓝可以选择不接受赠送的异种菜。

例如，食堂有 $3$ 种菜，小蓝可以每购买 $2$ 盘一号菜，可以选择赠送 $1$ 盘二号或者三号菜，同时，也可以选择不接受赠送。

注意，赠送的菜不能够参与买赠活动。

作为一个节俭的人，小蓝希望花费尽可能少的钱，但同时也不能有任何冗余的菜肴。他想知道，至少需要多少钱才能满足自己的需求。

输入格式

本题包含多个测试样例：

第一行输入一个整数 $T$（ $1\leq T \le 200$），代表测试数据组数。

每组测试数据包含以下部分：

第一行包含一个整数 $k_t$（$1 \le k_t \le 50$），表示食堂提供的菜肴种类数。

接下来 $k_t$ 行，每行包含两个整数 $p_i$ 和 $s_i$（$1 \le s_i \le 100, \sum\limits_{i=1}^{k_t} s_i \le 300, 1 \le p_i \le 10^5$），表示第 $i$ 种菜的价格每盘和小蓝想要的份数。

保证所有测试组的 $s_i$ 之和不超过 $2000$，即 $\sum\limits_{t=1}^T \sum\limits_{i=1}^{k_t} s_i \leq 2000$。

输出格式

对于每组测试样例，输出一行，包含一个整数，表示小蓝至少需要花费多少钱才能满足自己的需求。

样例输入

1
3
5 2
6 3
4 1

样例输出

22

说明

一种购买方案为：

买 $2$ 盘一号菜，送 $1$ 盘二号菜。

买 $2$ 盘二号菜，送 $1$ 盘三号菜。

费用为 $22$ 元。

T9. 打折【算法赛】

问题描述

小蓝今天兴致勃勃地去商场逛街，他心里已经有了一份购物清单，准备购买 $n$ 个物品。然而，他知道节省每一分钱都很重要，所以他带着 $m$ 种不同类型的优惠券，第 $i$ 种优惠券共有 $s_i$ 张。

每个物品都有一个价格 $p_i$，而小蓝手上的优惠券则分为两种类型：减满券和折扣券。对于第 $i$ 种优惠券，它可以减少小蓝购买某件物品的价格。如果是减满券，则某件物品金额大于等于 $A_i$ 元时，该物品可以减少 $B_i$ 元的支付金额；如果是折扣券，则可以享受 $X_i$ 折的优惠，即折后价格为 $\lceil \frac{p_i \times X_i}{100} \rceil$。

小蓝可以随意安排优惠券的使用，但每种物品只能使用一张优惠券，并且每张优惠券只能使用一次。请问小蓝最少需要付多少钱。

$\lceil \rceil$ 符号代表向上取整，例如 $\lceil 1.5 \rceil = 2,\lceil 2 \rceil = 2$。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示物品的数量和优惠券的种类数。$1 \le n, m \le 200$。

接下来一行包含 $n$ 个整数，表示每个物品的价格 $p_i$。$1 \le p_i \le 10^5$，单位为元。

接下来 $m$ 行，每行描述一种优惠券。包含 $3$ 个整数，$s_i, A_i, B_i/X_i$，代表该类优惠券数量是 $s_i$ 张，$B_i/X_i$ 代表输入是 $B_i$ 或者是 $X_i$，具体取决于 $A_i$ 的值：

1. 如果 $A_i$ 为 $0$，代表是折扣券，折扣为 $X_i$。
2. 如果 $A_i$ 不为 $0$，代表是减满券，购物金额达到 $A_i$ 元后，可以减少 $B_i$ 元。

$1 \le s_i \le n$，当 $A_i = 0$ 时，$1 \le X_i \le 100$，否则 $1 \le B_i \le A_i \le 10^5$。

输出格式

输出一个整数，表示小蓝最少需要付多少钱。

样例输入

3 2
10 20 30
1 10 5
2 0 50

样例输出

30

说明

在这个样例中，小蓝购买的第一个物品价格为 $10$，第二个物品价格为 $20$，第三个物品价格为 $30$。

他可以选择使用第一种优惠券，将第一个物品的价格减少 $5$ 元，第二、三个物品使用折扣券，打 $50\%$ 的折扣，最后的总价为 $10 - 5 + (30 + 20) \times 50\% = 30$ 元。