1019 第 20 场 小白入门赛/强者挑战赛

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

T1. 四个亲戚【算法赛】

问题描述

风流倜傥的贾宝玉，拥有四个如花似玉的亲戚：林黛玉、薛宝钗、元春和迎春。

这日，他们组团出国旅游了。为了方便称呼，宝玉给她们取了英文昵称，分别为：Daiyu、Baochai、Yuanchun 和 Yingchun。

但是，宝玉觉得这样还不够亲切！于是他突发奇想，决定给每个昵称都加上一个后缀 'kind'，以彰显她们在他心中的崇高地位。

比如，元春的昵称 Yuanchun，加上后缀后就变成了 Yuanchun'kind'。

现在，请你输出林黛玉英文昵称加上后缀 'kind' 后的结果。

输入格式

无。

输出格式

输出一个字符串，表示林黛玉英文昵称加上后缀 'kind' 后的结果。

T2. 黛玉泡茶【算法赛】

问题描述

话说林黛玉闲来无事，打算在潇湘馆摆个茶局，邀上宝钗、探春她们一起品茗赏花。黛玉素来讲究，用的茶杯也各有不同，大的小的，高的矮的，煞是好看。这不，她从柜子里拿出了 $N$ 只茶杯，这 $N$ 只茶杯的容量分别是 $C_1, C_2, \dots, C_N$ 。为了泡茶，黛玉还特意准备了一个容量为 $M$ 的茶壶。

天气炎热，姐妹们都想着多喝点，所以至少得斟满 $K$ 杯茶才够大家喝。可是这茶壶来回取水太麻烦了，黛玉想尽量少跑几趟。

对此，请你帮黛玉算算，她最少需要用茶壶取多少次水，才能斟满至少 $K$ 杯茶呢？

输入描述

第一行包含三个整数 $N$、$M$ 和 $K$（$1\leq K \leq N \leq 10^3$，$1\leq M \leq 10^3$），分别表示茶杯的数量、茶壶的容量以及黛玉想要斟满的茶杯数量。

第二行包含 $N$ 个整数 $C_1, C_2, \dots, C_N$（$1\leq C_i \leq 10^3$），表示每个茶杯的容量。

输出描述

输出一个整数，表示黛玉最少需要用茶壶取水的次数。

样例输入

2 3 1
5 7

样例输出

2

T3. 宝玉请安【算法赛】

问题描述

一日清晨，贾宝玉睡眼惺忪地从怡红院出来，准备去给长辈们请安。他需要先去凤姐的蘅芜苑请安，再到王夫人的潇湘馆请安（或先去潇湘馆，再到蘅芜苑，顺序不限）。

大观园里的道路是东西走向的。宝玉现在位于大观园正门（朝东方向） $x_1$ 步的位置。蘅芜苑位于距离正门（朝东方向） $x_2$ 步的位置，潇湘馆位于距离正门（朝东方向） $x_3$ 步的位置。

已知宝玉可以向东、向西两个方向行走。现在，请你帮宝玉算算，他最少需要走多少步才能完成这两次请安？

输入格式

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

接下来的 $t$ 行，每行包含三个整数 $x_1$，$x_2$ 和 $x_3$（$1\leq x_1,x_2,x_3\leq 10^9$，$x_1, x_2, x_3$ 互不相同），分别表示宝玉、蘅芜苑和潇湘馆所在位置距离正门的步数。

输出格式

对于每个测试用例，输出一个整数，表示宝玉最少需要走的步数。

样例输入

2
1 2 3
2 1 3

样例输出

2
3

样例说明

对于样例一，宝玉的路线可以是：

$$1 \rightarrow 2 \rightarrow 3$$

总共需要 $2$ 步。

对于样例二，宝玉的路线可以是：

$$2 \rightarrow 1 \rightarrow 2 \rightarrow 3$$

总共需要 $3$ 步。

T4. 贾母祝寿【算法赛】

问题描述

贾母的寿辰即将到来，荣国府为了迎接这个重要的日子，决定将花园布置成贾母最喜欢的样子。

花园中一共摆放了 $N$ 块具有特殊属性的玉石，最开始所有玉石的属性值均为 $0$。贾母会根据自己的喜好进行调整，共会进行 $Q$ 次操作，每次操作为以下两种之一：

1. 1 x y：将前 $x$ 块玉石的属性值增加 $y$。
2. 2 x y：将后 $x$ 块玉石的属性值减少 $y$。

玉石的亮度值由其属性值的绝对值决定。请问在贾母完成所有操作后，玉石中的最大亮度值是多少？

输入格式

第一行输入两个整数 $N,Q( 1\leq N \leq 10^9,1 \leq Q \leq 10^5)$ 表示玉石的数量和贾母的调整次数。

接下来 $Q$ 行，每行三个整数 $t_i,x_i,y_i(1 \leq t_i \leq 2, 1 \leq x_i \leq N, 1\leq y_i \leq 10^9)$ 表示一次操作，若 $t_i =1$ 则表示执行操作 $1$，$t_i =2$ 则执行操作 $2$。

输出格式

输出一个整数表示答案。

样例输入

6 3
1 1 3
2 2 5
1 5 3

样例输出

6

T5. 清洁客房【算法赛】

问题描述

荣国府即将举办一年一度的赏菊盛会，为了迎接来自各方的贵宾，精明的管家探春正为府中 $n$ 间客房的清洁工作制定方案。

每间客房都需要安排一定等级的清洁工作，等级从 $0$ 到 $9$，代表清洁程度（$0$ 代表不进行清洁，$9$ 代表最高级别的清洁）。其中，第一间客房作为府中最重要的迎宾厅，探春要求其清洁等级至少为 $1$，以确保其光洁如新。

此外，探春追求高效精细的管理，希望所有客房的清洁等级尽可能简洁明了。因此，她决定刚好使用三种不同的清洁等级来安排所有客房的清洁工作。

例如，如果 $n=3$，那么 $1-0-2$、$1-2-3$、$2-1-3$ 等都是合法的方案，因为它们都使用了三种不同的清洁等级。而 $1-1-1$、$1-2-2$、$0-1-2$ 则都不是合法的方案。

现在，请你帮助探春算算，总共有多少种符合她要求的清洁方案。由于答案可能很大，你只需要输出方案数对 $10^9 + 7$ 取模的结果即可。

输入格式

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

接下来的 $t$ 行，每行包含一个整数 $n$（$1\leq n \leq 10^5$），表示客房的数量。

输出格式

对于每个测试用例，输出一个整数，表示符合探春要求的方案总数对 $10^9 + 7$ 取模后的结果。

样例输入

2
2
3

样例输出

0
648

T6. 宝玉与黛玉的考验【算法赛】

问题描述

贾府最近新购置了一块 $n \times m$ 的土地，计划用作新的花园。作为新任花园总管，你被贾母赋予了管理这片土地的重任。

宝玉和黛玉对新花园充满了兴趣，想考验一下你的能力：

• 宝玉：对花园的每一行土地表示喜好。他会给你一个长度为 $n$ 的字符串 $S$。如果 $S_i = 1$，表示他喜爱第 $i$ 行的所有土地；如果 $S_i = 0$，则不喜爱。
• 黛玉：对花园的每一列土地表示喜好。她会给你一个长度为 $m$ 的字符串 $T$。如果 $T_j = 1$，表示她喜爱第 $j$ 列的所有土地；如果 $T_j = 0$，则不喜爱。

一块土地 $(i, j)$ 被称为可分配的，当且仅当 $S_i$ 与 $T_j$ 仅有一个值为 $1$，即这块土地恰好被宝玉或黛玉其中一人所喜爱。

他们的问题是：在花园中任意 $k \times k$ 的方格中，最多能有多少块可分配的土地？

你的任务是找到这个最大值。

输入格式

第一行输入三个整数 $n,m,k(1 \leq k \leq n \leq m \leq 2 \times 10^5)$ 表示土地的大小以及可选的方格大小。

第二行输入一个长度为 $n$ 的 $01$ 字符串 $S$ 表示宝玉对每行土地是否喜爱。

第三行输入一个长度为 $m$ 的 $01$ 字符串 $T$ 表示黛玉对每列土地是否喜爱。

输出格式

输出一个整数表示答案。

样例输入

5 6 3
11010
101010

样例输出

5

T7. 小鸡变鸡腿【算法赛】

问题描述

宝玉梦游太虚幻境，来到了一个光怪陆离的厨房。只见一个巨大的铁锅摆放在正中央，锅底熊熊燃烧着奇异的蓝色火焰，散发着阵阵诱人的香气。这铁锅可不是凡物，它有个奇特的功效——小鸡变鸡腿：如果宝玉向其丢入了 $n$ 只小鸡，那么铁锅就会把它们变成 $n^n$ 个大鸡腿。

比方说，如果宝玉向其丢入了 $1$ 只小鸡，那么铁锅就会把这只小鸡变成 $1$ 个大鸡腿；如果宝玉向其丢入了 $2$ 只小鸡，那么铁锅就会把它们变成 $4$ 个大鸡腿。

现在，宝玉想知道：要得到至少 $K$ 种不同的鸡腿组合，至少需要向铁锅丢进多少只小鸡？

鸡腿组合指的是将所有鸡腿进行均分后，所有可能的分法数量。例如，$4$ 个鸡腿可以分成：

1. $1$ 份，每份 $4$ 个鸡腿。
2. $2$ 份，每份 2 个鸡腿。
3. $4$ 份，每份 $1$ 个鸡腿。

所以，$4$ 个鸡腿共有 $3$ 种不同的鸡腿组合。

再例如，$6$ 个鸡腿可以分成：

1. $1$ 份，每份 $6$ 个鸡腿。
2. $2$ 份，每份 $3$ 个鸡腿。
3. $3$ 份，每份 $2$ 个鸡腿。
4. $6$ 份，每份 $1$ 个鸡腿。

所以，$6$ 个鸡腿共有 $4$ 种不同的鸡腿组合。

输入格式

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

接下来的 $t$ 行，每行包含一个正整数 $K$（$1\leq K \leq 10^{18}$），表示宝玉想要的鸡腿组合数量的最小值。

输出格式

对于每个测试用例，输出一个整数，表示宝玉至少需要向铁锅丢进的小鸡数量。

样例输入

2
1
4

样例输出

1
3

T8. 赏花宴【算法赛】

问题描述

荣国府一年一度的赏花宴即将开始，贾母决定为参加宴会的丫鬟们准备精美的头饰，以示恩宠。

荣国府的丫鬟人数众多，可以认为有无限个。她们的编号从 $1$ 开始，按照 $1,2,3,4,5\dots$ 的规律依次递增。负责准备头饰的王熙凤，收到了一份清单，清单上记录了已经准备好的头饰对应的丫鬟编号。只是，这份清单因为各种原因（比如抄写错误、丫鬟请假等）并不完整，也可能存在重复的编号。

时间紧迫，贾母急切地想知道还有哪些丫鬟没有准备好头饰。她会多次询问王熙凤，每次询问都会指定一个数字 $k$，要求王熙凤找出第 $k$ 个尚未在清单中出现的丫鬟编号。这里的“第 $k$ 个”指的是连续的、编号最小的第 $k$ 个尚未在清单中出现的丫鬟编号。

例如，如果清单上记录的丫鬟编号是 $[1, 1, 2, 3, 5, 8, 10]$，那么：

• 如果 $k=1$，则第 $1$ 个还没准备好头饰的丫鬟编号是 $4$。
• 如果 $k=2$，则第 $2$ 个还没准备好头饰的丫鬟编号是 $6$。
• 如果 $k=3$，则第 $3$ 个还没准备好头饰的丫鬟编号是 $7$。
• 如果 $k=5$，则第 $5$ 个还没准备好头饰的丫鬟编号是 $11$。

现在，请你编写程序，帮助王熙凤回答贾母的询问。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1\leq n, q \leq 10^5$），分别表示清单中记录的丫鬟编号的个数和贾母提出的询问次数。

第二行包含 $n$ 个整数 $a_1, a_2,\dots, a_n$（$1\leq a_i \leq 10^9$），表示清单上记录的丫鬟编号。

接下来 $q$ 行，每行一个整数 $k$（$1\leq k \leq 10^9$），表示每次询问想要知道的第 $k$ 个还没准备好头饰的丫鬟的编号。

输出格式

对于每个询问，输出一行，包含一个整数，表示第 $k$ 个还没准备好头饰的丫鬟编号。

样例输入

7 4
1 1 2 3 5 8 10
1
2
3
5

样例输出

4
6
7
11

T9. 宝玉出行【算法赛】

问题描述

宝玉作为贾府的少爷，每次出行可谓是风光无限，出行时随从数量极多，更是坐着象征尊贵的 "玲珑轿"。

贪玩的宝玉有一个初步的出行计划，这可以用一个长度为 $n$ 的字符串 $S$ 表示：如果第 $i$ 天宝玉打算出行，则 $S_i=1$；否则 $S_i=0$。

每次出行，宝玉都需要坐上 "玲珑轿"。如果没有干净的 "玲珑轿"，则他不会出行。宝玉具有一定的洁癖，每次他使用过的 "玲珑轿" 都需要经过 $d$ 天的清洗和整理后才会再次使用。例如，某辆 "玲珑轿" 在第 $x$ 天使用了，那么它最快可以在第 $(x+d)$ 天再次使用。

接下来可能会发生 $q$ 个事件，事件包括以下两种：

1. 贾母对宝玉天天出行游玩早已不满，宝玉为了应对贾母，在某些时刻会更改自己的出行计划。贾母不在府上时，他可能会将某个 $S_x=0$ 变为 $S_x=1$；贾母在府上时也可能会将某个 $S_x=1$ 变为 $S_x=0$。

2. 在不断地修改出行计划同时，宝玉会随时询问作为管家的你，如果最初只有 $k$ 台 "玲珑轿" 可供使用，能否满足当前的出行计划。若能满足则输出 $-1$，否则输出最早无法成功出行的一天。

输入格式

第一行输入两个整数 $n,d$ $(1 \leq d \leq n \leq 2 \times 10^5)$，表示宝玉的出行计划天数和 "玲珑轿" 的使用间隔。

第二行输入一个长度为 $n$ 的 $01$ 字符串 $S$，表示宝玉最开始的出行计划。

第三行输入一个整数 $q$ $(1 \leq q \leq 2 \times 10^5)$，表示事件的数量。

接下来 $q$ 行，每行两个整数 $op,x$ $(1 \leq op \leq 2, 1 \leq x \leq n)$ 表示一次事件。

• 若 $op=1$，则将 $S_x$ 翻转，即 $1$ 变为 $0$，$0$ 变为 $1$。
• 若 $op=2$，则表示 $k=x$ 的一次查询。

输出格式

对于每个 $op=2$ 的查询，输出一行一个整数作为答案。

样例输入

5 2
01010
3
2 1
1 3
2 1

样例输出

-1
3

说明

第一次查询时，可以满足每天的出行需求，输出 $-1$。

第二次查询时，在第 $3$ 天没有 "玲珑轿" 使用。