0420 第 2 场 算法季度赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/season-2/
• 题解回放：https://www.bilibili.com/video/BV1F1421R7F2/

T1. 疯狂星期六【算法赛】

问题描述

麦肯鸡是一家名声在外的汉堡店，他们最近推出了一份名为 vivo50 的套餐，只需要在门口大声喊出 vivo50，就能够获得这个套餐。

现在，请你打印 vivo50，告诉计算机你想要这个套餐。虽然计算机无法为你提供这个套餐，但它可以帮助你通过本题。

输入格式

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

输出格式

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

T2. 忙碌的售票员【算法赛】

问题描述

小蓝是一家旅行社的售票员，他每天都很忙碌。

为什么呢？原因是这样的，当地文旅局与旅行社合作，所以旅行社能够以更加低廉的价格拿到票，然后旅行社再将这些票配套导游服务一起卖给顾客。虽然看起来十分划算，但是这可苦了我们的售票员小蓝。因为即使能够拿到更低价的票，但是票仍然需要从机器中打印出，文旅局的机器十分的老旧，但是旅行社的订单又十分的多，这就导致了小蓝需要耗费大量的时间来打印票据。

文旅局共有三台打票机，每台机器每次只能打印一张票，打印一张票的时间是 $x$ 分钟（即需要操作机器 $x$ 分钟），但是机器每打完一张票后，都需要停机 $y$ 分钟，不然的话，机器会过热宕机，俗称 “冷却”。

小蓝共有 $a$ 张票需要打，同一时刻只能操作一台机器。他想知道，他最少需要多长时间才能打完所有的票。

输入格式

第一行输出一个整数 $T$（$1\leq T \le 10^4$），代表测试数据组数。

接下来 $T$ 行，每行三个整数 $x, y, a$（$1 \le x,y,a \le 10^7$），代表打票时间 $x$ 分钟，冷却 $y$ 分钟，共有 $a$ 张票需要打。

输出格式

输出 $T$ 行，每行一个整数，代表最少需要多长时间能够打完票，单位为分钟。

样例输入

2
3 1 4
2 6 4

样例输出

12
10

说明

小蓝的操作时间区间如下：

第一组样例：

时间区间	机器编号
$1 \sim 3$ 秒	1
$4 \sim 6$ 秒	2
$7 \sim 9$ 秒	1
$10 \sim 12$ 秒	2

第二组样例：

时间区间	机器编号
$1 \sim 2$ 秒	1
$3 \sim 4$ 秒	2
$5 \sim 6$ 秒	3
$9 \sim 10$ 秒	1

T3. 兽之泪 II【算法赛】

问题描述

图片描述

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

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

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

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

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

输入格式

第一行包含一个整数 $T,(T \le 10^5)$，代表测试组数。

每组数据包含如下部分：

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

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

保证 $\sum k \le 10^5$。

输出格式

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

样例输入

1
3 4
2 2
4 2
1 1

样例输出

8

说明

注意，$x_i, y_i$ 并不保证谁大谁小。

一种可行的方案是：

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

另外一种方案是：

四次都选择 $1$ 号怪兽，消耗的能量是 $8$。

T4. 超级数【算法赛】

问题描述

小蓝总是以为自己对数字很敏感，于是小桥给他出了道题，当然，他知道小蓝一定不会，于是简化了一下问题。

有一个 $M$ ($M = 2^{30}$) 进制的超大的数 $N$，共有 $len$ 个数位，同时给出一个超大的区间 $[L,R]$，问在 $N$ 的子数中，有多少个子数在区间内。由于进制超大，我们用空格将大数的每一位区分开。

子数的定义： 删除一些 $N$ 的前缀(可能为空)和后缀(可能为空)，剩下来的部分组成的数，注意，只要是删除的前缀不同，或者后缀不同，就算不同的子数，例如 $\lbrace 1, 2, 2, 2, 3 \rbrace$，子段 $[2, 3]$ 形成的数 $\lbrace 2, 2 \rbrace$ 和子段 $[3, 4]$ 形成的数 $\lbrace 2, 2 \rbrace$ 视为不同的数。

当然，为了简化问题，小桥保证 $N$ 的每一位是有序的，并且告诉你是单调不减的。

输入格式

第一行输入一个数 $len$，代表大数的长度。

第二行，输入 $len$ 个数，表示大数 $N$ 的每一位 $\lbrace n_1, n_2, ..., n_{len} \rbrace$，每个数用空格隔开。

第三行输入一个数 $len_l$，代表区间左端点的长度。

第四行输入 $len_l$ 个数，代表 $L$ 的每一位 $\lbrace l_1, l_2, ..., l_{len_l} \rbrace$，每个数用空格隔开。

第五行输入一个数 $len_r$，代表区间右端点的长度。

第六行，输入 $len_r$ 个数，代表 $R$ 的每一位 $\lbrace r_1, r_2, ..., r_{len_r} \rbrace$，每个数用空格隔开。

$1 \le lenl \le lenr \le len \le 2 \times 10^5$。

$1 \le L \le R \le N, 0 \le n_i, l_i, r_i \lt 2^{30}$。

超大数 $L,R,N$ 的输入不存在前导 $0$。

注意：在大数 $N$ 的描述中，$n_1$ 是高位，$n_{len_n}$ 是低位，其他大数类似。

输出格式

输出一行一个整数 $ans$，代表有 $ans$ 个子数在区间内。

样例输入

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

样例输出

8

说明

由于输入的数都没有超过 $10$，我们当作 $10$ 进制看待，$N=12345$，$L=20$，$R=10000$。

符合条件的数为 $\lbrace 23,34,45,123,234,345,1234,2345 \rbrace$ 共计 $8$ 个。

T5. 仪仗队【算法赛】

问题描述

为了迎接蓝桥王国一年一度的盛大庆典，国王组建了一支仪仗队，由 $N$ 位士兵组成，每位士兵都有自己的礼仪值 $A_i$。

然而，蓝桥国民对庆典的热情超乎国王的预期，报名参加的人数远远超过了广场的容量。面对这一情况，国王不得不做出艰难的决定，削减仪仗队的人数，淘汰 $K$ 位士兵。

国王希望最大限度地保留仪仗队的总礼仪值，但又不希望直接淘汰掉礼仪值较低的 $K$ 位士兵，以避免引起不满和抱怨。

为此，国王决定进行 $K$ 次操作。每次操作，他会随机选择两个整数 $l$ 和 $r$，然后淘汰当前仪仗队中第 $l$ 名到第 $r$ 名（包括 $l$ 和 $r$）礼仪值最低的士兵。如果存在多个礼仪值最低的士兵，将淘汰其中最左边的士兵。

现在，请来计算国王完成操作后仪仗队的总礼仪值。

注意：每次操作后仪仗队人数会减去 $1$。

输入格式

第一行包含一个整数 $N(2\leq N \leq 5\times 10^5)$，表示仪仗队初始成员数。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots，A_N(1 \leq A_i \leq 10^9)$，$A_i$ 表示第 $i$​ 名士兵的礼仪值。

第三行输入一个整数 $K(1 \leq K <N)$ 表示国王的操作次数。

接下来 $K$ 行每行输入两个整数 $l,r( 1\le l \leq r \leq M)$ 表示国王的操作区间，其中 $M$ 表示操作时仪仗队成员数（对于第 $i$ 次操作，$M = n - i + 1$）。

输出格式

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

样例输入

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

样例输出

9

说明

对于给定的样例，初始仪仗队的士兵礼仪值依次为 $[1, 2, 4, 5, 4]$。

在国王的第一次操作中，他选择了区间 $[2, 4]$，该区间内的最小值为 $2$。因此，礼仪值为 $2$ 的士兵被淘汰，新的仪仗队变为 $[1, 4, 5, 4]$。

接着，国王进行了第二次操作，选择了区间 $[1, 4, 5]$，其中最小值为 $1$。于是，礼仪值为 $1$ 的士兵被淘汰，最新的仪仗队变为 $[4, 5, 4]$。

最后一次操作国王选择区间 $[4, 5, 4]$，该区间的最小值为 $4$。由于区间内存在多个礼仪值为 $4$ 的士兵，国王选择淘汰其中最左边的士兵，因此仪仗队最终变为 $[5, 4]$。

因此，最终仪仗队的总礼仪值是 $5 + 4 = 9$。

T6. 修整道路【算法赛】

问题描述

蓝桥村的道路图可以看成一幅联通树形图（数据结构中的"树"），其中村政府所在的位置是 $1$ 号点，也就是根节点。每家每户都可以看成一个节点。总共有 $n$ 个节点，$n- 1$ 条边，每条边就是一条道路，每条道路会有一个长度 $t$，从节点 $a$ 到 $b$ 的时间等于$a,b$ 之间最短路径上的长度之和。

现在村政府获得了一笔经费，这笔经费可以足够整改 $k$ 次道路，每一次整改可以将这条道路的长度减少 $\lfloor \frac{t}{2} \rfloor$。也就是说，对一条长度为 $t$ 的道路进行一次整改，它的长度由 $t$ 变为 $\lceil \frac{t}{2} \rceil$ ，并且一条道路可以经历多次整改。注意区分"道路"与"路径"的区别，道路只指一条边。

我们设 $f(x)$ 为从 $1$ 号点到 $x$ 点需要的时间，由于村政府需要长期发布一些通知，所以村长想知道经历整改后可以使得 $\sum _{i=2}^n{f(i)}$ 最小为多少?

$\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数，即向下取整。$\lceil x \rceil$ 表示不小于 $x$ 的最小整数，即向上取整。

形式化的说：给定一棵 $n$ 个节点的带权树形图，你有 $k$ 次机会，每次你可以选择一条边，使得它的边权从 $t_i$ 变为 $\lceil \frac{t_i}{2} \rceil$，询问你所有点到根节点的路径和最小是多少？

输入格式

第一行一个数字 $T$ ，代表测试组数。

对于每组输入，由以下部分组成：

第一行两个整数 $n, k$，保证 $2 \le n \le 10^4,0 \le k \le 10^9$。

接下来 $n - 1$ 行，每行三个整数 $u_i, v_i, t_i$ ，表示 $u_i$ 和 $v_i$ 之间有一条长度为 $t_i$ 的道路。$u_i,v_i \in [1,n],t_i \in [1,10^9]$

数据保证是一棵树。并且 $\sum{n} \le 10^5$。

输出格式

输出 $T$ 行，每行一个整数 $W$ ，表示路径和。

样例输入

1
3 2
1 2 4
1 3 5

样例输出

5

说明

$(1, 2)$ 之间整修一次，$(1,3)$ 之间整修一次。

T7. 小蓝的密码【算法赛】

问题描述

小蓝是一个安全意识很强的男生，他绝对不允许别人动他的电脑，于是他给自己的电脑设置了一个密码（$PIN$）。$PIN$ 只由十进制数字 $0$ 到 $9$ 组成，但是由于硬盘太小，于是他就只设置了一个 $n(n \le 5000)$ 位的 $PIN$。

这一天，他想要打开电脑的时候，他发现他忘记了 $PIN$，但是幸好他设置了提示，是一个 $10$ 位的字符串，分别代表每一位数字是否存在于 $PIN$ 的状态。

我们定义字符串 $s*{0} s*{1} ... s\_{9}$

1. 如果 $s_i$ 为 o ，代表数字 $i$ 存在于 $PIN$ 中；

2. 如果 $s_i$ 为 ? ，代表数字 $i$ 可能存在于 $PIN$ 中；

3. 如果 $s_i$ 为 x ，代表数字 $i$ 不存在于 $PIN$ 中；

小蓝想要询问，可能的 $PIN$ 有多少种，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$，保证 $n \le 5000$。

第二行是一个长度为 $10$ 的字符串，保证只出现 x，o，? 三种字符。

输出格式

一个整数，代表密码的种类数量，答案对 $998244353$ 取模。

样例输入

5
ooxxxxxxxx

样例输出

30

说明

密码必须只包含 $0,1$，并且不能全为 $0$ 或者全为 $1$。

所以答案为：$2^5 - 2 = 30$。

T8. 外卖员的小爱好【算法赛】

问题描述

小桥是一名外卖小哥，他收到很多的订单需要送。

他所在城市的地图可以看成一幅无向连通图，其中有 $n$ 个节点，编号为 $1 \sim n$，有 $m$ 条边。

每一笔订单由两个参数 $(s_i,t_i)$ 组成，表示他需要从 $s_i$ 点出发，将外卖送到 $t_i$ 点。小桥可以随意规定他的路线，但是为了追求效率，在每一笔订单中，每条边只能经过一遍。

同时小桥是一个相信幸运的人，城市的某些路上装配了一些刮刮乐彩票机，小桥想知道在他的每笔订单中，是否有机会买彩票。

注意，每笔订单是独立的，每笔订单的过程只计算从 $s_i$ 出发到 $t_i$ 结束，你无须关注从 $t_i$ 到 $s_{i+1}$ 的过程。

输入格式

第一行输出一个整数 $T$，表示有 $T$ 组数据。

每组数据由以下部分组成：

第一行输入三个整数 $n,m,q$，$n$ 代表城市节点的数量，$m$ 代表边的数量，$q$ 代表订单的数量。

接下来 $m$ 行描述道路，三个整数 $v_i, u_i, f_i$，表示存在一条 $(v_i, u_i)$ 的道路，$f_i$ 为 $1$ 时表示这条路上装配了刮刮乐彩票机，$f_i$ 为 $0$ 时表示这条路上未装配彩票机。

接下来 $q$ 行描述订单，两个整数 $(s_i, t_i)$ ，表示他需要从 $s_i$ 点出发，将外卖送到 $t_i$ 点。（由于是连通图，所有一定能到达）。

数据规模约定：

$1 \le n,q\le10^5, 0 \le m \le 2 \times10^5, \sum n \le 10^6,\sum m \le 2 \times 10^6,\sum q \le 10^6, f_i \in \lbrace 0,1\rbrace, 1\le T \le 10^6$。

$v_i,u_i,s_i,t_i \in [1, n]$。

图中可以存在重边，自环。

输出格式

对于每个询问，输出一个字符串：

如果可以买彩票，输出：Yes。

如果不可以，输出：No。

样例输入

1
4 4 2
1 2 0
1 3 0
2 3 0
3 4 1
1 4
1 3

样例输出

Yes
No

说明

$1 \to 4$ 能够经过带有彩票的道路（红色边）。

$1 \to 3$ 不能够经过带有彩票的道路。

图片描述