0113 第 3 场 小白入门赛/强者挑战赛

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

T1. 召唤神坤【算法赛】

问题描述

现有 $N$ 个帅气逼人的偶像练习生成员，每个成员都有其舞力值 $W_i$。我们需要选出三名成员 $i,j,k$ $(i <j<k)$ 组成舞团出道，舞团的舞力值计算规则为 $\lfloor \dfrac{W_i+W_k}{W_j} \rfloor$，其中 $\lfloor \rfloor$ 表示下取整。

当成功选出舞力值最大的团体组合时，就可以召唤神坤，请你计算出可能选出的最大团队舞力值。

输入格式

第一行输入一个正整数 $N$ 表示偶像练习生成员个数。

第二行输入 $N$ 个整数 $W_1,W_2,W_3, \cdots W_n$ 表示成员的舞力值。

输出格式

输出一个整数，表示可能选出的最大团队舞力值。

样例输入

6
1 2 3 4 5 6

样例输出

3

说明

一种可能的选择方案为选择 $[1,2,6]$，可以得到最大团队舞力值。

评测数据范围

$3 \leq N \leq 10^5$，$1 \leq a_i \leq 10^9$。

T2. 聪明的交换策略【算法赛】

问题描述

小蓝面前有 $n$ 个排成一行的盒子，每个盒子要么是蓝色要么是红色。这些盒子的颜色通过一个长度为 $n$ 的字符串 $s$ 表示，其中字符 1 和 0 分别代表蓝色和红色盒子。

小蓝的任务是通过相邻盒子之间的交换，使得最多只有一对相邻盒子的颜色不同，请你帮忙计算最少的交换次数。

输入格式

第一行输入一个整数 $n$ ，表示盒子的个数。

输入包含一个字符串 $s$，表示盒子的初始颜色排列。

输出格式

输出一个整数，表示完成任务所需的最小交换次数。

样例输入

5
01010

样例输出

3

评测数据规模

$1 \le n \le 10^5$。

T3. 怪兽突击【算法赛】

问题描述

怪兽终极班开班了！

小蓝作为新晋的怪兽终结者，现在它需要总共击败 $k$ 次怪兽来完成老师布置的任务。总共有 $n$ 只怪兽供他选择，每只怪兽都可以无限挑战，攻击需要满足以下条件：

• 对于第 $i$ 只怪兽，首次击败它需要消耗 $a_i$ 点体力，后续每次击败都消耗 $a_i + b_i$ 点体力。
• 只有当编号 $[1,i-1]$ 的怪兽都被你起码击败过一次，你才能挑战编号为 $i$ 的怪兽。当然编号为 $1$ 的怪兽你可以直接挑战。

现在，请你帮小蓝计算累计击败 $k$ 次怪兽最少需要消耗多少体力。

输入格式

第一行输入两个正整数 $n,k$ 表示怪兽个数和小蓝需要击败的怪兽次数。

第二行输入 $n$ 个整数 $a_1,a_2,a_3, \cdots a_n$，含义如题面所示。

第三行输入 $n$ 个整数 $b_1,b_2,b_3,\cdots,b_n$，含义如题面所示。

输出格式

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

样例输入

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

样例输出

30

评测数据范围

$1 \leq n,a_i,b_i \leq 10^5$，$1 \leq k \leq 10^9$。

T4. 蓝桥快打【算法赛】

问题描述

小蓝和小桥又在玩电动啦！

最近出了一款新的游戏，“蓝桥快打”。两位玩家分别控制一位格斗家，每个格斗家有两个属性：体力值和攻击力。

他们轮流攻击对方，小蓝先进行攻击，然后是小桥，然后轮到小蓝，以此类推。

每一次进行攻击，被攻击的一方都会减少体力值，减少的体力值等于攻击方的攻击力，当某一方的体力值小于等于 $0$，那么游戏结束，体力值先小于等于 $0$ 的一方输。

小蓝是一个计算机高手，他知道了小桥的体力值和攻击力，他决定调整自己的攻击力，以保证自己一定能赢，但是他又不想太明显，以至于被小桥发现，所以他决定调整自己的攻击力为保证自己一定能赢的最小值。

请你告诉他，应该将自己的攻击力调整为多少。

输入格式

输入包含多个测试组。

第一行输入一个整数 $T$（$1 \le T \le 10^4$），表示测试组的数量。

接下来 $T$ 行，每行输入三个整数，$A,B,C$（$1 \le A, B, C \le 10^9$），$A$ 为小蓝的体力值，$B$ 为小桥的体力值，$C$ 为小桥的攻击力。

输出格式

输出 $T$ 行，每行一个值，表示小蓝能赢的最小攻击力。

样例输入

3
5 6 1
10 16 10
8 8 3

样例输出

2
16
3

说明

第一组样例，如果小蓝的攻击力为 $1$，那么在轮流攻击 $5$ 次后，就会输掉，所以最小是 $2$。

第二组样例，小蓝必须一击必杀。

T5. 奇怪的段【算法赛】

问题描述

在数学课上，小桥开始突发奇想，思考各种各样的数学问题，他想到了这么一个问题。

给定一个长度为 $n$ 的序列 $\lbrace a_1, a_2, a_3, ..., a_n \rbrace$，以及一个长度为 $k$ 的序列 $\lbrace p_1, p_2, ..., p_k \rbrace$。

需要划分出 $k$ 个区间$\lbrace [l_1, r_1], [l_2, r_2], ... ,[l_k, r_k] \rbrace$，满足以下要求：

1. $l_1 = 1$ 以及 $r_k = n$。
2. $l_i \le r_i$。
3. 当 $i \lt k$ 时，$r_i + 1 = l_{i+1}$。

我们定义每个区间的权值为这个区间的和值，即：$W_x = \sum_{i=l_x} ^{r_x} a_i$。

我们需要使得加权和值 $\sum _{i=1} ^k (W_i \times p_i)$ 最大。小桥将问题抛给了同桌小蓝，小蓝思考了之后仍然不会，他又把问题抛给了你。

你只思考了两秒钟，就知道了答案，你需要告诉小蓝答案是多少。

输入格式

第一行输入两个整数 $n, k$。（$1 \le n \le 10^5, 1 \le k \le \min(n, 200)$）。

第二行输入 $n$ 个整数 $a_1, a_2, a_3, ..., a_n$。（$-1 0^6 \le a_i \le 10^6$）。

第三行输入 $k$ 个整数 $p_1, p_2, ..., p_k$。（$-10^6 \le p_i \le 10^6$）。

输出格式

输出一个整数，代表最大加权和值。

样例输入

5 2
1 -2 4 3 -9
-1 4

样例输出

-7

说明

一种划分方法为：$\lbrace [1, 2], [3, 5] \rbrace$

T6. 暖气冰场【算法赛】

问题描述

冬天到了，一起快乐的滑冰吧！

蓝桥冰场是一个 $n \times m$ 的矩形，可以看成 $n$ 行 $m$ 列的小矩形组成。

第 $i$ 行第 $j$ 列的位置被描述成 $(i,j)$。

为了防止滑冰场内太冷，滑冰场的老板小蓝在 $t$ 个位置放置了暖气炉，由于蓝桥冰场的冰是特殊材质，所以你并不用担心冰会融化。

每个暖气炉会产生暖气。在放置时，放置的位置就已经被暖气覆盖。每经过一秒，存在暖气的格子会传播暖气到周围的格子。具体来说，如果 $(x, y)$ 存在暖气，那么一秒之后，$(x-1, y),(x+1, y),(x, y-1),(x, y+1),(x-1, y-1),(x-1, y+1),(x+1, y-1),(x+1, y+1)$ 八个位置也会被暖气覆盖。

需要注意的是，超过边界的位置不会被暖气覆盖，多余的暖气也不会传播到其他格子（具体见样例说明）。

小蓝告诉你，他放置暖气炉的位置 $(x_1, y_1), (x_2, y_2), ..., (x_t, y_t)$，你需要告诉小蓝，经过多久之后，整个冰场都会被暖气覆盖。

如果你成功回答问题，小蓝就会送给你一张蓝桥冰场的优惠券。

输入格式

第一行输入三个整数 $n, m, t$。（$1 \le n , m \le 10^3,1 \le t \le n\times m$）。

接下来 $t$ 行，每行两个整数 $x_i, y_i$，代表每个暖气炉的位置，保证每个位置不会出现两次。（$1 \le x_i \le n, 1 \le y_i \le m$）。

输出格式

输出一个整数，代表暖气覆盖冰场的最小时间，单位为秒。

样例输入

4 4 2
1 1
3 3

样例输出

2

说明

我们用 $0$ 表示未覆盖暖气，$1$ 表示已覆盖暖气。

$$\left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} \right] \underset{1s}{\Longrightarrow} \left[ \begin{matrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix} \right] \underset{2s}{\Longrightarrow} \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} \right]$$

T7. 小蓝的反击【算法赛】

问题描述

又是一节数论课，老师在黑板上写了 $n$ 个数字 $a_1, a_2, a_3, ..., a_n$。

小蓝在被小桥问了一个很难的问题后，决定考验一下小桥，问题是这样的：

给定了两个整数 $A, B$，请问有多少个区间 $[l, r]$ 满足：$\prod _{i=l}^r a_i$ 是 $A$ 的倍数，但是不是 $B$ 的倍数。

我们定义：

$$\prod_{i=l}^ra_i=a_l\times a_{l+1}\times a_{l+2}\cdots\times a_r$$

小桥比小蓝聪明多了，只用了两秒钟就回答出了答案。于是小桥开始来考验你，你需要回答他的问题。

输入格式

第一行输入三个整数 $n, A, B$。（$1 \le n \le 10^6,1 \le A, B \le 10^9$）。

第二行输入 $n$ 个整数 $a_1, a_2, a_3, ..., a_n$。（$1 \le a_i \le 10^9$）。

输出格式

一个整数，代表合法的区间数量。

样例输入

4 6 9
3 2 3 2

样例输出

4

说明

$\lbrace [1,2], [2,3], [2,4], [3, 4] \rbrace$

数据量较大，请使用比较快的输入输出方式。

T8. 逃跑【算法赛】

问题描述

小桥被小蓝的数学题考验之后，变得十分愤怒。于是他想要抓住小蓝，并狂暴输出一万个数学题来考验小蓝。

他们所在的世界可以看成是由 $n$ 个节点，$n-1$ 条边组成的一副树形图，小桥在 $1$ 号点，小蓝会等概率的出现在 $1 \sim n$ 中的某一个点。

每一秒，两人都能移动到他们当前位置相邻的节点，或者也可以选择不移动。当小蓝和小桥处于同一个位置时，可以认为小桥抓住了小蓝。

注意：两人的移动是线性的，他们会沿着边等速移动，所以他们也可能在路中间相遇。

小蓝，小桥都是很聪明的，无论出现在哪一个点，小蓝总会逃跑尽可能长的时间，以坚持最长的时间不被小桥抓住，而小桥也会尽可能以最短的时间抓出小蓝。

现在，请你计算一下小蓝能坚持的最长时间的期望是多少？答案可能不是整数，请对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$。（$2 \le n \le 10^6$）。

接下来 $n - 1$ 行，每行输入 $2$ 个整数 $u_i, v_i$，表示存在一条边连接 $(u_i, v_i)$。（$ 1 \le u_i, v_i \le n$）。

保证数据是一棵树。

输出格式

输出一个整数，表示期望能坚持的最长时间。答案对 $998244353$ 取模。

如果答案是 $\frac {a}{b}$ 的形式，你需要输出 $a \times b^{-1} \mod 998244353$，$b^{-1}$ 是 $b$ 在模 $998244353$ 下的逆元，题目保证答案一定存在。

样例输入

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

样例输出

3

说明

图片描述

1. 出现在 $1$ 点，最晚 $0$ 秒时被抓住。
2. 出现在 $2$ 点，最晚 $1$ 秒时被抓住。
3. 出现在 $3$ 点，最晚 $4$ 秒时被抓住。
4. 出现在 $4$ 点，最晚 $4$ 秒时被抓住。
5. 出现在 $5$ 点，最晚 $4$ 秒时被抓住。
6. 出现在 $6$ 点，最晚 $4$ 秒时被抓住。
7. 出现在 $7$ 点，最晚 $4$ 秒时被抓住。

所以期望是 $3$ 秒被抓住。

T9. 选糖果【算法赛】

问题描述

小桥最终还是抓到了小蓝，但是他还是有一颗仁慈之心，他给了小蓝一次机会。

只要能够回答这个问题，那么小桥就不会给小蓝一万道数学题来折磨小蓝，而是会大发慈悲放他一马。

问题是这样的，小桥拿出了 $n$ 颗糖果，编号 $1 \sim n$。每颗糖果都有自己的种类，共有 $k$ 种不同的种类，编号 $1 \sim k$，小桥规定第 $i$ 种糖果不能取超过 $s_i$ 颗。每次小桥询问一个区间 $[l, r]$，代表小蓝需要在糖果编号在 $[l, r]$ 的区间中取糖果，请问小蓝最多能取多少颗糖果。

为了验证小蓝不是蒙出来的答案，小桥会询问 $m$ 次。

小蓝当然不会，于是又来求助你了。你需要回答小桥的所有问题。

输入格式

第一行输入三个整数 $n, k, m$。（$1 \le n, k, m \le 10^5$）。

第二行输入 $n$ 个整数 $p_1, p_2, p_3, ..., p_n$，代表每个糖果的种类。（$1 \le p_i \le k$）。

第三行输入 $k$ 个整数 $s_1, s_2, s_3, ..., s_k$，代表每种糖果的限制。（$0 \le s_i \le n$）。

接下来 $m$，每行输入两个整数 $t_i, x_i$，代表每次询问区间的特殊值，我们定义 $l = (t_i \otimes ans_{last}), r = (x_i \otimes ans_{last})$。询问的区间为 $[l, r]$。（$1 \le l \le r \le n$）。

$ans_{last}$ 为上一个询问的答案，初始的值为 $0$，$\otimes$ 代表按位异或。

输出格式

输出 $m$ 个整数，每行一个整数，代表询问的答案。

样例输入

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

样例输出

2
3
2

说明

询问区间为：$[1,2],[2,6],[5,6]$。

询问为 $[1,2]$ 时，由于 $1,2$ 号糖果都只有一个，所以答案为 $2$。

询问为 $[2,6]$ 时，由于 $1,2$ 号糖果分别为 $3, 2$ 个，但是限制 $1$ 类有最多有 $2$ 个，$2$ 类最多只能 $1$ 个，所以答案为 $3$。

询问为 $[5,6]$ 时，由于 $1$ 号糖果只有两个，所以答案为 $2$。