1130 第 23 场 小白入门赛/强者挑战赛

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

T1. 三体时间【算法赛】

问题描述

罗辑在担任面壁者期间，常常语出惊人。有一天，他对记者们宣布：“我的计划是，训练一群哈巴狗去征服宇宙！它们适应力超强，甚至能在三体行星上生存！”

记者们听得一头雾水：“三体行星？那里的时间系统和地球不一样啊，哈巴狗怎么适应？”

罗辑神秘一笑：“嘿嘿！我发明了一种时间转换装置，能把三体时间转换成地球时间。三体时间每过 1 个单位，相当于地球时间过了 26 个小时。我已经设置好装置，让哈巴狗们按照地球时间生活。”

他顿了顿，向一位记者提问：“考考你，如果三体时间过了 999 个单位，相当于地球时间过了几天几小时？”

为了简化计算，我们假设地球上每天都是 24 小时。

现在，请你帮助这位记者作答，将地球时间以 “d h” 的格式输出，其中 d 表示天数，h 表示小时数。例如，2 天 5 小时，输出 "2 5"。

输入格式

无

输出格式

输出一个字符串，格式为 "d h"，其中 d 表示天数，h 表示小时数。

输入格式

无

输出格式

输出两个整数，格式为 "d h"，其中 $d$ 表示天数，$h$ 表示小时数。

T2. 存储晶体【算法赛】

问题描述

威慑纪元 2230 年，人类联邦在与三体文明的对抗中，为了强化飞船的能源储备，决定收集能量晶体。飞船的储存空间呈矩形，边长分别为 $a$ 和 $b$。对于一个能量晶体，只有当它的长度小于或等于存储空间的对角线长度时，它才能被安全地放入飞船中。

现在，人类联邦总共收集了 $n$ 个能量晶体。你的任务是判断每根能量晶体是否可以放入飞船。

输入格式

第一行包含两个整数 $a$ 和 $b$（$1\leq b \leq a \leq 10^3$），表示飞船储存空间的长和宽。

接下来一行包含一个整数 $n$（$1\leq n \leq 10^3$），表示能量晶体的数量。

再接下来 $n$ 行，每行包含一个整数 $c$（$1\leq c \leq 10^4$），表示每根能量晶体的长度。

输出格式

对于每根能量晶体，输出一行：

• 如果该晶体可以放入，输出 YES。
• 如果该晶体不能放入，输出 NO。

样例输入

10 10
3
5
10
20

样例输出

YES
YES
NO

T3. 屏蔽信号【算法赛】

问题描述

在与三体文明的对抗中，人类联邦探测到了两个重要的信号源，分别用非负整数 $a$ 和 $b$ 来表示。

为了抵御三体舰队的入侵，科学家们制定出一项关键策略——屏蔽信号，目标是要让 $a$、$b$ 这两个信号源其中之一的数值归零。 在实施屏蔽操作时，有着一套既定规则：每次操作，科学家们需要先对比两个信号源的数值大小，然后用较大的那个数减去较小的数，得出差值之后，再把原本较大的那个数替换成这个差值。就这样反复操作，一轮一轮进行下去。

现在，请你来帮忙计算一下，按照这样的操作方式，要想实现将两个信号源之中任意一个变为零，所需要进行的最少操作次数是多少呢？

输入格式

第一行包含一个整数 $t$ （$1 \leq t \leq 10^3$），表示测试数据的数量。

接下来的 $t$ 行，每行包含两个非负整数 $a$ 和 $b$ （$0 \leq a, b \leq 10^9$），表示两个关键的信号源。

输出格式

对于每组测试数据，输出一个整数，表示将其中一个信号源变为零所需的最小操作次数，每个结果占一行。

样例输入

3
0 3
2 5
3 6

样例输出

0
4
2

T4. 掩体计划【算法赛】

问题描述

危机纪元 2211 年，由罗辑领导的雪地工程正式进入部署，雪地工程中布置了大量的核弹，整个工程由信号中转站和起爆装置构成，形成了一棵具有 $n$ 个点 $n-1$ 条边的有根树，$1$ 号点为根节点，树边为 $(u_i , v_i)$ 。

起爆装置为度为 $1$ 并且不是根的节点，其余节点为信号中转站，预先在 $m$ 个起爆装置上面布置有核弹，为了引爆核弹，会在 $1$ 号节点施加一个引爆信号，在信号中转站上，该信号会随机向某一个子节点传输，为了避免核弹不被引爆，你可以在信号中转站上面安装控制器，使得引爆信号只会往指定的子节点传输，为了减少开销，你能帮帮罗辑计算最少需要安装的控制器数量吗？

输入格式

第 $1$ 行包含一个正整数 $n$（$2\leq n \leq 10^5$），表示树点的数量。

第 $2\sim n+1$ 行每行包含 $2$ 个正整数 $u_i,v_i$（$1 \leq u_i,v_i \leq n$），分别表示树边的两个端点。

接下来 $1$ 行包含一个正整数 $m$ ($1\leq m \leq$ 叶子数量) ，表示含有核弹的起爆装置的数量。

再接下来 $1$ 行包含 $m$ 个整数 ， 表示具有核弹起爆装置的节点编号。

输出格式

输出一个数字，表示需要放置的最小控制器数量。

样例输入

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

样例输出

1

T5. 智商检测【算法赛】

问题描述

威慑纪元 2275 年，人类联邦选出来新的执剑人程心，在黑暗森林的另一角，三体舰队首席执行官为了检测新执剑人的智商，通过具象扫描仪，扫描出了程心的精神模型，并且向执剑人提出了这样的问题：

给一个长度为 $n$ 的数组，要求删除恰好 $k$ 个数字，使得数组剩余数字的的 $\gcd$ 最大。

那么，最大的 $\gcd$ 会是多少呢？

输入格式

第 $1$ 行包含两个正整数 $n , k$（$2\leq n \leq 10^5$，$1\leq k \leq min(n-1,10^2)$），分别表示数组的长度和需要删除的数字的数量。

第 $2$ 行包含 $n$ 个整数 $a_1, a_2, \cdots,a_{n-1} ,a_n$（$1 \leq a_i \leq 10^9$），分别表示数组中的 $n$ 个数字。

保证 $a_i$ 是由随机数据 $c_i$（随机生成的数值）乘以一个系数（系数的取值范围在 $1\sim 10^5$）所得。

输出格式

输出一个数字，表示删除恰好 $k$ 个数字之后的最大 $\gcd$。

样例输入

6 2
2 4 5 3 8 10

样例输出

2

T6. 高能粒子【算法赛】

问题描述

威慑纪元 2233 年，人类地球联邦为了突破质子科技封锁，决定在太阳系的黄道平面上建造大量高能粒子对撞机，与普通高能粒子对撞机不同的是，可以将黄道平面抽象为一个二维平面。

一共有 $n$ 个 $\alpha$ 高能粒子和 $m$ 个 $\beta$ 高能粒子，$\alpha$ 高能粒子的运动轨迹可以被描述为直线 $y_i = a_i \times x_i + b_i$，$\beta$ 高能粒子的运动轨迹可以被描述为直线 $x = c_i$。

因为越靠近对撞中心的粒子，其被质子干扰的程度越低，所以为了获得最准确的数据，我们需要选取一个合适的 $\beta$ 粒子的运动轨迹，使得其与 $\alpha$ 粒子运动轨迹的交点的 $y$ 值的中位数最大。

输入格式

输入第 $1$ 行包含一个正整数 $n$（$1\leq n \leq 10^5$），表示 $\alpha$ 粒子的数量，保证 $n$ 为奇数。

第 $2\sim n+1$ 行每行包含 $2$ 个正整数 $a_i,b_i$ （$-10^9 \leq a_i,b_i \leq 10^9$），分别表示 $\alpha$ 高能粒子的直线轨迹方程的两个参数。

接下来 $1$ 行包含一个正整数 $m$（$1\leq m \leq 5\times 10^5$），表示 $\beta$ 粒子的数量。

再接下来 $1$ 行包含 $m$ 个整数，表示 $\beta$ 粒子的轨迹方程的参数 $c_1,c_2,...,c_m$（$1 \leq c_i \leq 10^9$）。

保证 $\alpha$ 粒子的运动轨迹两两不同，$\beta$ 粒子的运动轨迹两两不同。

输出格式

输出两个数字，表示选择的 $\beta$ 粒子的下标编号 $id$ 和最大化的中位数。

下标编号 $id$ 从 $1$ 开始。

样例输入

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

样例输出

1 2

样例解释

第 $1$ 个 $\beta$ 粒子的运动轨迹与 $\alpha$ 粒子相交了 $5$ 个点，对应的 $y$ 值分别为 $-2,7,-7,6,2$，中位数为 $2$ 。

T7. 曲率驱动【算法赛】

问题描述

广播纪元 2283 年，掩体工程启动。星环集团开始着手建造星环城作为曲率驱动的研究基地。

曲率驱动可以描述为在一张 $n$ 个点 $m$ 条边的无向图中进行运动，图的每条边可以描述为 $(u_i,v_i,w_i)$，分别为边的两个端点和边的长度。

有 $k$ 个修改操作，每个操作对应一个整数 $c$。在每次操作中，图中所有边的长度将通过以下方式更新：$w_i = w_i \oplus c$。修改操作必须按照给定的顺序依次进行。

现在，为了工程能顺利开展，你需要从 $1$ 号点出发，计算到达每个点的最短距离。如果无法到达，则将最短距离标记为 $-1$。

举个例子：

假设在原始情况下，从 $1$ 号点到 $2$ 号点的距离为 $3$，从 $2$ 号点到 $3$ 号点的距离为 $6$。当进行一次修改操作后，从 $1$ 到 $2$ 的距离将变为 $4$，从 $2$ 到 $3$ 的距离将变为 $1$。

那么在计算从 $1$ 到 $3$ 的最短距离时：可以在修改操作进行前，先从 $1$ 到 $2$（距离为 $3$），然后等修改操作进行后，再从 $2$ 到 $3$（此时距离为 $1$）。因此，从 $1$ 到 $3$ 的最短路径为 $3 + 1 = 4$。

输入格式

第 $1$ 行包含两个正整数 $n , m$（$1\leq n , m \leq 10^3$） ，表示无向图的点的数量和边的数量。

第 $2\sim m+1$ 行每行包含 $3$ 个正整数 $u_i,v_i,w_i$（$1 \leq u_i,v_i \leq n$ ，$1 \leq w_i \leq 10^9$）, 分别表示每条边的两个端点和边权。

接下来输入 $1$ 行包含一个正整数 $k$（ $1\leq k \leq 10^3$ ），表示可以修改路径长度的次数。

再接下来输入 $k$ 个整数 $c_1,c_2,...,c_{k-1},c_{k}$（$1 \leq c_i \leq 10^9$），分别表示修改的参数。

数据保证图中无重边、无自环。

输出格式

输出 $n$ 个数字，表示从 $1$ 号点出发，到达每个点的最短距离，如果无法到达，输出 $-1$ 。

样例输入

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

样例输出

0 2 2 1 1

T8. 银河纪元【算法赛】

问题描述

在银河纪元 2689 年，云天明和艾 AA 被困在蓝色星球上。为了消磨时间，艾 AA 出了一道题考考云天明。

给定一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，其中每个元素的值为 $1$ 或 $-1$。

现有 $q$ 次操作或询问：

1. 操作：给定两个整数 $l$ 和 $r$，执行翻转操作，即对于区间 $[l, r]$ 内的所有元素，将 $a_i$ 更新为 $-a_i$。

2. 询问：给定两个整数 $x$ 和 $y$，计算并返回 $z$ 的值。

$z$ 值的计算方法：

1. 初始化 $z$ 为 $0$。
2. 从 $1$ 遍历到 $n$，处理序列中的每个元素 $a_i$，执行以下操作：
   • 如果 $a_i = 1$： - $y \ eq 0$，则将 $y$ 减 1； - 否则，将 $x$ 加 1，$z$ 加 1。
   • 如果 $a_i = -1$： - $x \ eq 0$，则将 $x$ 减 1； - 否则，将 $y$ 加 1，$z$ 加 1。

遍历结束后，得到的 $z$ 值即为询问所需的答案。

输入格式

第 $1$ 行包含一个正整数 $n$（$1\leq n \leq 10^5$），表示序列的长度。

第 $2$ 行包含 $n$ 个正整数 $a_1, a_2, \cdots , a_n$，$a_i \in \lbrace-1, 1\rbrace$。

第 $3$ 行包含一个正整数 $q$（$1\leq q \leq 10^5$），表示操作、询问的总次数。

接下来 $q$ 行每行包含三个整数 $type,l,r$ 或 $type,x,y$ ，表示操作或询问的参数。

$type\in \lbrace{1,2\rbrace}$ ，$1 \leq l,r \leq n$，$0 \leq x,y \leq 2\times 10^5$ 。

• $type = 1$ 代表这是一次修改。

• $type = 2$ 代表这是一次询问。

数据保证至少有一次询问。

输出格式

对于每个询问输出一行，包含一个整数，表示询问所需 $z$ 的值。

样例输入

8
1 1 1 -1 1 1 -1 -1
15
2 5 1
2 2 3
2 0 0
2 0 3
2 0 3
2 3 2
2 1 2
1 1 7
1 3 8
1 4 8
1 2 5
2 2 2
2 4 1
1 1 8
2 1 1

样例输出

4
2
5
3
3
3
3
3
2
4

T9. 降维打击【算法赛】

问题描述

掩体纪元 2403 年，太阳系被哥者文明随手扔的二向箔进行二维化，使太阳系从三维空间降为二维平面，高度将不复存在。

如果在合适的角度观察太阳系，将只会看见一维的太阳系，可以将太阳系形式化地描述为 $01$ 组成的世界。为了更加优雅地描述这个 $01$ 世界，“善于思考”的观察者文明尝试用询问的方法描述这个新产生的世界：

给定一个 $01$ 串 $s$ ，有 $q$ 次询问，每次询问给出 $p_i,l_i,r_i$ ，求

$$\sum_{k \in [l_i,r_i],k \in \mathbb{Z}}{f(s[p:k]) \times g(s[p:k])}$$

其中 $f(t)$ 表示 $t$ 在 $s$ 中出现的次数，$g(t)$ 表示字符串 $t$ 中 $1$ 的数量，$s[l:r]$ 表示 $s_l,s_{l+1},...,s_{r-1},s_r$。

输入格式

第 $1$ 行包含一个正整数 $n$，$q$（$1\leq n , q \leq 10^5$），分别表示字符串的长度和询问的次数。

第 $2$ 行包含一个长度为 $n$、由 $01$ 组成的字符串 $s$ 。

接下来 $q$ 行，每行包含三个数字 $p_i,l_i,r_i$（$1 \leq p_i \leq l_i \leq r_i \leq n$），表示每次询问的三个参数。

保证所有询问的 $\sum({r_i-l_i+1}) \leq 10^7$。

输出格式

每个询问输出 $1$ 行，包含 $1$ 个数字，表示 $\sum_{k \in [l_i,r_i],k \in \mathbb{Z}}{f(s[p:k]) \times g(s[p:k])}$ 的值 。

样例输入

6 2
100100
1 3 4
2 3 5

样例输出

4
2