1102 第 21 场 小白入门赛/强者挑战赛

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

T1. 动态密码【算法赛】

问题描述

双十一这天，小蓝熬夜到凌晨，就为了抢购限量版机械键盘。困得眼睛都睁不开的他，终于把键盘添加到了购物车，就差最后一步：付款！

然而，当他颤抖着手指准备输入支付密码时，却发现$\dots$他不记得密码了？！😱

好吧这并不要紧，因为小蓝此前设置了动态密码。动态密码是将当天的日期（八位数字格式）转换成二进制表示形式（不含前导零）。

对小蓝来说，今天是 2024 年 11 月 11 日（八位数字格式为：20241111）。现在，请你帮他计算出动态密码，帮他完成支付。

输入格式

无。

输出格式

输出一个数字字符串，表示动态密码。

T2. 购物车里的宝贝【算法赛】

问题描述

双十一前夕，小蓝的购物车里已经塞满了 $n$ 件宝贝，价格分别是 $a_1, a_2, \dots, a_n$。为了在双十一当天顺利付款，小蓝决定把这些宝贝分成两批下单。

只是，小蓝最近学习了“异或运算”，她希望这两批订单里，宝贝价格的异或和都完全一样！

具体来说，她要将这 $n$ 个宝贝分成两个集合 $S_1, S_2$，使得集合 $S_1$ 中所有元素（宝贝价格）的异或和等于集合 $S_2$ 中所有元素（宝贝价格）的异或和。

现在，请你帮小蓝判断一下，她购物车里的宝贝能否这样划分？如果可以，输出 YES；否则，就输出 NO。

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示有 $n$ 件宝贝。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\leq a_i \leq 10^5$），分别表示 $n$ 件宝贝的价格。

输出格式

输出一行，包含一个字符串 YES 或 NO。

样例输入

3
1 2 3

样例输出

YES

样例说明

将 $1$、$2$ 划分至 $S_1$，将 $3$ 划分至 $S_2$。

T3. 代金券【算法赛】

问题描述

双十一前夕，小蓝凭借高超的技术手段（其实是发现了系统的 BUG），薅到了无数张面值为 $M$ 元的无门槛、可叠加使用的代金券。这意味着只要购买商品的总价是 $M$ 的倍数，就能将商品免费带回家。

小蓝的购物车里已经塞满了各种心仪的宝贝，总价为 $N$ 元，恰好 $M$ 的倍数。 只是，他觉得这样的薅羊毛还不够极致。于是，他决定在确认订单时，修改总价（可以在 $N$ 的开头、结尾或中间插入一个新数字）。例如，如果原总价 $N$ 是 $123$ 元，那么他可以修改成 $4123$ 元，$1243$ 元，$1234$ 元等等。虽然实际支付的金额仍然是 $0$ 元（使用无限的代金券），但更高的总价意味着可以获得更高的积分、更高级的会员等级。

不过，小蓝也担心修改后的总价过高会触发系统的安全警报，导致 BUG 被修复。因此，他想找到一个比 $N$ 大的最小数字，这个数字是由在 $N$ 的数字之间（含头尾）插入一个数字构成的，并且仍然是 $M$ 的倍数。这样，他就能在最大化 BUG 收益的同时，最小化被发现的风险。

现在，请你帮小蓝找出这个最小的数字。

输入格式

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

接下来的 $t$ 行，每行包含两个整数 $N,M$（$1\leq M \leq N \leq 10^9$，保证 $N$ 是 $M$ 的倍数），分别表示小蓝购物车里商品的初始总价和代金券的面值。

输出格式

对于每组测试数据，输出一个整数，表示小蓝能够构造出的比 $N$ 大的最小数字，且该数字是 $M$ 的倍数。如果不存在这样的数字，则输出 $-1$。

样例输入

2
4 2
6 3

样例输出

14
36

T4. 蓝桥商场【算法赛】

问题描述

随着双十一的来临，蓝桥商场迎来了一场狂欢，共有 $n$ 家店铺开展了免费试吃活动。

活动结束后，每家店铺都还剩下一些试吃食物，第 $i$ 家店铺剩下 $a_i$ 份食物未被消耗完。

商场保安小蓝接到指令要处理这些剩余食物，但他觉得浪费太可惜。因此，他决定亲自吃完这些食物。每分钟，小蓝可以选择以下操作之一：

1. 选择一家仍有剩余食物的店铺，吃掉其中的一份食物。在下一分钟，小蓝不能再选择同一家店铺的食物。
2. 休息，不吃任何食物。

请问，小蓝需要多少分钟才能吃完所有店铺剩余的食物呢？

输入格式

第一行输入一个整数 $n(1 \leq n \leq 10^5)$ 表示店铺的数量。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(1 \leq a_i \leq 10^5)$ 表示每家店铺剩余的食物数量。

输出格式

输出一个整数表示答案。

样例输入

3
1 1 3

样例输出

5

T5. 蓝桥派对【算法赛】

问题描述

双十一来临，蓝桥公司为了感谢用户，举办了一场游戏派对，共邀请了 $n$ 位同学参加。

在派对上共设有 $m$ 个游戏摊位。第 $i$ 位同学从第 $a_i$ 个摊位开始参与游戏，然后依次参与第 $a_i+1, a_i+2, \ldots, b_i$ 个摊位。

起初，这些同学互不相识。他们达成了一个约定：只要两人至少共同参与了一个游戏摊位，他们就会成为朋友。

现在，您需要帮助每位同学确定他们可以结交的朋友数量。

注意：自己和自己无法结交为朋友。

输入格式

第 $1$ 行输入两个整数 $n,m(1 \leq n \leq 2\times 10^5,1 \leq m \leq 10^9)$ 表示同学的数量和游戏摊位的数量。

接下来第 $2 \sim n+1$ 行，每行输入两个整数 $a_i,b_i(1 \leq a_i \leq b_i \leq m)$ 表示第 $i$ 位同学的游玩摊位区间。

输出格式

输出 $n$ 行，第 $i$ 行表示第 $i$ 位同学可以结交的朋友数量。

样例输入

5 6
1 1
1 3
3 4
1 6
5 6

样例输出

2
3
2
4
1

T6. 薅羊毛【算法赛】

问题描述

双十一购物节来了！作为精打细算的买家，小蓝正忙着薅各种羊毛。这次，她盯上了各大电商平台的“签到送积分”活动——每日签到，必得积分！

通过观察小蓝发现，从第 $L$ 天到第 $R$ 天，每天送的签到积分都有规律可循：

• 第 $L$ 天，签到会送 $L^L$ 积分。
• 第 $L+1$ 天，签到会送 $(L+1)^{L+1}$ 积分。
• $\cdots$
• 第 $R$ 天，签到会送 $R^R$ 积分。

此外，小蓝还发现平台藏有一个隐藏的签到规则：连续两天的签到积分可以合并。合并的方式是取两天签到积分的最小公倍数（$\text{lcm}$）。例如，第 $L$ 天和第 $L+1$ 天的积分合并为 $\text{lcm}(L^L, (L+1)^{L+1})$，第 $L+1$ 天和第 $L + 2$ 天返回积分可以合并 $\text{lcm}((L+1)^{L+1}, (L+2)^{L+2})$，以此类推。

现在小蓝想要知道，从第 $L$ 天到第 $R$ 天，所有连续两天的签到积分合并后的总和（即下方式子的计算结果）会是多少？

$$\text{lcm}( L^L, (L+1)^{L+1} ) + \text{lcm}( (L+1)^{L+1}, (L+2)^{L+2} ) + \cdots + \text{lcm}( (R-1)^{R-1}, R^R )$$

请你帮小蓝完成计算。由于答案可能很大，你只需要给出答案对 $10^9 + 7$ 取模的结果即可。

输入格式

输入仅一行，包含两个整数 $L$ 和 $R$（$1\leq L < R \leq 10^9$，$|R - L| \leq 10^5$），分别表示签到的起始天数和结束天数。

输出格式

输出一个整数，表示从第 $L$ 天到第 $R$ 天，所有连续两天签到积分合并后的总和对 $10^9 + 7$ 取模的结果。

样例输入

1 2

样例输出

4

T7. 中奖编号【算法赛】

问题描述

双十一，某快乐肥宅水品牌举办了一个线上抽奖活动。参与方式很简单：输入一个 $n$ 位数的编号，就有机会获得巨额奖金！

作为该品牌的核心员工，小蓝从一个可靠的渠道得知了一个内部消息：只要输入的 $n$ 位数编号的各位数字仅由两种不同的非零数字组成，就能百分百中奖。

例如，$n=4$，那么“$1122$”、“$3355$”、“$6669$”都是中奖编号）。

小蓝掌握了这个中奖秘诀，他想要估算潜在的总奖金（总奖金与所有中奖编号的总和相等）。

对此，请你帮他计算出所有中奖编号的总和。由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模后的结果即可。

输入格式

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

接下来的 $t$ 行，每行包含一个正整数 $n$（$2\leq n \leq 2\times 10^5$），表示编号的位数。

输出格式

对于每个测试用例，输出一个整数，表示所有 $n$ 位中奖编号的总和。

样例输入

1
2

样例输出

3960

T8. 凑单返现【算法赛】

问题描述

双十一购物节，小蓝相中了 $n$ 件商品，正当他准备下单时，看到商家推出一个诱人的“双十一凑单返现”活动！原来，商家为了冲刺销售额，希望顾客多买东西凑单，于是设计了以下活动：

如果用户额外购买了 $x$ 件商品来凑单，并且原计划购买的商品数量 $n$ 和额外购买的商品数量 $x$ 满足：$\frac{(x + 1)(x + 2)(x + 3)\cdots(x + n)}{x}$ 的结果是整数，那么将全额返还额外购买的这 $x$ 件凑单商品的钱。

小蓝是个精明的消费者，他想要计算所有能够让他获得全额返现的凑单商品数量 $x$。现在，请你帮助小蓝解决这个问题，即计算所有满足条件的 $x$ 的个数。由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模的结果即可。

输入格式

输入一个正整数 $n$（$1\leq n\leq 10^5$），表示小蓝计划购买的商品数量。

输出格式

输出一个整数，表示所有能够让小蓝获得全额返现的凑单商品数量 $x$ 的个数对 $10^9+7$ 取模后的结果。

样例输入

3

样例输出

4

样例说明

当 $n = 3$ 时，满足条件的 $x$ 有：$1,2,3,6$。

T9. 商铺评分【算法赛】

问题描述

在双十一活动期间，有 $n$ 家店铺参与了商铺大战。活动开始时，每家店铺的初始评价分均视为 $0$。

共有 $m$ 位用户受邀为这些店铺进行点评。对于第 $i$ 位用户，他会给定三个整数 $l_i, r_i, x_i$，表示给第 $l_i$ 到第 $r_i$ 家店铺增加评价分 $x_i$。

为了评估用户点评的合理性，购物网站会提出 $q$ 个查询操作。每次查询的操作如下：

• 给定三个整数 $k, s, t$，可以任意选择两个整数 $l$ 和 $r$（满足 $s \leq l \leq r \leq t$），在采纳第 $l,l+1,l+2,\cdots,r$ 位用户的点评后，第 $k$ 家店铺可能达到的最大评价分是多少？

请注意，每个查询都是独立的。现在，请你帮助解决这个问题。

输入格式

第一行输入两个整数 $n, m$（$1 \leq n, m \leq 10^5$），表示店铺和用户数量。

接下来 $m$ 行，每行包含三个整数 $l_i, r_i, x_i$（$1 \leq l_i \leq r_i \leq n, -10^5 \leq x_i \leq 10^5$），表示第 $i$ 个用户的评分操作。

接下来一行输入一个整数 $q$（$1 \leq q \leq 10^5$），表示购物网站的查询次数。

接下来 $q$ 行，每行包含三个整数 $k, s, t$（$1 \leq k \leq n, 1 \leq s \leq t \leq m)$ 表示一次查询。

输出格式

对于每次查询输出一个整数表示答案。

样例输入

3 5
1 2 2
1 1 0
1 3 1
1 3 -3
1 2 5
2
2 1 2
1 1 4

样例输出

2
3

说明

对于第二次查询，我们可以选择采纳用户 $1,2,3$ 的评分，这样第一家店铺获得最高总评分为 $3$。