1125 第 4 场算法双周赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/challenge-4/
• 题解回放：https://www.bilibili.com/video/BV17G411i7tE/

T1. 验题人的生日

问题描述

滑大稽了！验题人亲自上场出题了。

执梗在 $12$ 月要过生日了，作为验题人的他打算告诉所有人他的生日。

具体地说，他的生日是 $12$ 月 $X$ 日，这个 $X$ 既是一个偶数又是一个质数，请你猜猜他的生日是几号吧。

PS：如果你在评论区留下祝福，那么执梗会祝福你 $AK$ 本场比赛。

注：使用阿拉伯数字表示答案。

输入格式

本题无输入。

输出格式

输出一个整数，表示 $X$ 的值。

T2. 蓝桥小课堂—海伦公式【算法赛】

问题描述

蓝桥小课堂开课啦！

海伦公式（Heron's formula），也称为海伦-秦九韶公式，是用于计算三角形面积的一种公式，它可以通过三条边的长度来确定三角形的面积，而无需知道三角形的高度。

海伦公式的形式如下：

假设三角形的三条边长度分别为 $a$、$b$ 和 $c$，半周长（即三边之和的一半）为 $s$，那么三角形的面积 $A$ 可以通过以下公式计算：

$$A = \sqrt{s \cdot (s-a) \cdot (s-b) \cdot (s-c)}$$

其中，$\sqrt{x}$ 表示计算 $x$ 的平方根。

海伦公式可以用于计算任意三角形的面积，无论三角形是锐角、直角还是钝角三角形。它的原理是基于三角形面积与三角形的边长之间的关系。

使用海伦公式计算三角形的面积时，需要确保三个边长满足构成三角形的条件，即任意两边之和大于第三边。否则，如果输入的边长不能构成一个三角形，海伦公式将无法计算有效的面积。

现在，学习完海伦公式后你需要接受小蓝的考验了。给定三条边 $a,b,c$，假设这三边组成的三角形面积为 $S$，请你回答 $S^2$ 的值是多少。

若 $a,b,c$ 无法围成三角形则输出 $-1$。

输入格式

输入一行三个整数 $a,b,c$ 表示三条边。

输出格式

输出一个整数表示答案。

样例输入

3 4 5

样例输出

36

评测数据范围

$1 \leq a,b,c \leq 300$。

保证 $(a+b+c)$ 为偶数。

T3. 压缩矩阵【算法赛】

问题描述

小蓝最近在学矩阵，小桥作为他的好朋友，给了他一个挑战。

给定一个规模为 $n \times n$ 的矩阵 $a$，叫做带状矩阵，下标范围位 $1 \sim n$。

$a_{i,j}$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的元素，满足以下限制：

1. 当 $1\lt i \lt n$ 时，仅有 $a_{i,i-1},a_{i,i},a_{i,i+1}$ 为正值。
2. 当 $i=1$ 时，仅有 $a_{1,1},a_{1,2}$ 为正值。
3. 当 $i=n$ 时，仅有 $a_{n,n-1},a_{n,n}$ 为正整数。
4. 除了上述位置，其他位置都为 $0$。

具体排布如下：

$$\left[ \begin{matrix} a_{1,1} & a_{1,2} & 0 & 0 & 0 & \cdots & 0 & 0 \\\\ a_{2,1} & a_{2,2} & a_{2,3} & 0 & 0 & \cdots & 0 & 0 \\\\ 0 & a_{3,2} & a_{3,3} & a_{3,4} & 0 & \cdots & 0 & 0 \\\\ 0 & 0 & a_{4,3} & a_{4,4} & a_{4,4} & \cdots & 0 & 0 \\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\\\ 0 & 0 & 0 & 0 & 0 & \cdots & a_{n,n-1} & a_{n,n} \end{matrix} \right]$$

小桥是计算机系的，他想要压缩这个矩阵。具体来说，由于很多位置都是 $0$，所以他想要一个一维数组来存储这个矩阵。

小桥的方案是：将 $0$ 值都抛弃，只存储整数，在一维数组 $b$ 中存储这些值，一位数组从下标 $0$ 开始。矩阵从第一行开始从左到右扫描，遇到正整数，就依次放到一维数组中，以次类推。

最后得到数组中的对应关系如下所示：

$$\begin{matrix} a_{1,1} & a_{1,2} & a_{2,1} & a_{2,2} & a_{2,3} & \cdots & a_{n,n-1} & a_{n,n} \\\\ \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \\\\ b_0 & b_1 & b_2 & b_3 & b_4 & \cdots & b_{3n-4} & b_{3n-3} \end{matrix}$$

存储完成之后，需要满足一些询问要求，小桥会询问数组中的某个位置（从 $0$ 下标开始），然后你需要回答他该位置的值还原到矩阵中时，它的位置是多少，用两个整数 $(u,v)$ 表示它原来在矩阵中第 $u$ 行 $v$ 列。

小蓝一时间觉得十分麻烦，于是请你帮他解决这个问题。

输入格式

第一行输入两个整数 $n, q$，代表矩阵的规模和询问的次数。

接下来 $q$ 行，每行一个整数 $x$，代表询问数组 $b$ 中下标为 $x$ 的位置的值还原到矩阵中的位置。

输出格式

输出 $q$ 行，每行两个整数 $u,v$，用空格隔开，代表询问数组 $b$ 中下标为 $x$ 的位置的值还原到矩阵中是第 $u$ 行 $v$ 列。

样例输入

3 4
5
6
3
0

样例输出

3 2
3 3
2 2
1 1

说明

我们用 $b$ 数组表示压缩后一维数组的元素，还原到矩阵中就是：

$$\left[ \begin{matrix} a_{1,1} & a_{1,2} & 0 \\\\ a_{2,1} & a_{2,2} & a_{2,3} \\\\ 0 & a_{3,2} & a_{3,3} \end{matrix} \right] \Longleftrightarrow \left[ \begin{matrix} b_0 & b_1 & 0 \\\\ b_2 & b_3 & b_4 \\\\ 0 & b_5 & b_6 \end{matrix} \right]$$

评测数据范围

$3 \le n \le 10^{12}, 1 \le q \le 10^5$。

保证询问的 $x$ 在一维数组中一定存在。

T4. 恒纪元【算法赛】

问题描述

三体世界中，有恒纪元和乱纪元。

经过无数天的测试，伟大的科学家小蓝终于发现了三个神奇的数：$x,y,z$，当年份 $T$ 可以表示为 $T=x^a+y^b+z^c$ 时，（$a,b,c$ 为非负整数），我们称 $T$ 就是乱纪元，其他年份我们称之为恒纪元。

现在处于公元 $S$ 年，正处于乱纪元，小蓝要向三体的领袖周文王预测下一个恒纪元是什么时候，并且能够持续多少年？小蓝实在太累了，于是他将这个问题交给了你。

由于有很多平行宇宙，所以存在多次询问。

输入格式

第一行输入三个整数 $x,y,z$。

第二行输入一个整数 $q$，代表询问次数。

接下来 $q$ 行，每行一个正整数 $S$，代表小蓝询问的年份。

输出格式

输出 $q$ 行。

对于每一个询问，输出两个整数 $A, B$，代表下一个恒纪元从公元 $A$ 年开始，并且持续 $B$ 年。

样例输入

1 2 3
2
3
14

样例输出

7 1
15 3

说明

区间 $[1, 18]$ 中的恒纪元分别为 $1,2,7,9,13,15,16,17$。

区间 $[1, 18]$ 中的乱纪元分别为 $3,4,5,6,8,10,11,12,14,18$。

公元 $3$ 年后,第一个恒纪元是公元 $7$ 年，持续 $1$ 年。

公元 $14$ 年后,第一个恒纪元是公元 $15$ 年，持续 $3$ 年。

评测数据范围

$1 \le x,y,z \le 10^5, 1 \le S \le 10^{12}, 1 \le q \le 10^4$。

保证 $S$ 一定是乱纪元。

保证 $x,y,z$ 不同时为 $1$。

T5. 充能计划【算法赛】

问题描述

小蓝在星际旅行，他降落在蓝桥行星上后，惊奇地发现自己的飞船能源耗尽了。

小蓝的飞船共有 $n$ 个引擎需要充能，编号分别为 $1 \sim n$，所有的引擎能量都归零了。

蓝桥星上有很多稀有的宝石，可以为引擎充能。每个宝石有自己的种类 $p_i$，并且有自己的能量值 $s_i$，代表这个宝石可以为编号连续的 $s_i$ 个引擎充 $1$ 点能量。但是每个引擎对于同一种类的宝石，只能吸收 $1$ 点能量。

例如，存在一个种类为 $2$ 号的宝石，他的能量为 $3$，那么他可以为编号 $[1,3]$ 的引擎充能，或者为 $[2,4]$ 的引擎充能，依此类推。如果有两个 $2$ 类宝石为 $i$ 号引擎充了两次能，那么 $i$ 号引擎只能接受 $1$ 点能量；但是如果有两个 $2$ 类宝石和一个 $3$ 类宝石为 $i$ 号引擎充能，$i$ 号引擎能接受 $2$ 点能量，分别是来自 $2$ 类的 $1$ 点能量和 $3$ 类的 $1$ 点能量。

小蓝非常懒惰，他不想计算这些，他只是将开采的宝石对着引擎随意的一扔。如果对于第 $i$ 个宝石，它落到了第 $k$ 个位置，那么这个宝石会对 $[k, \min(k + s_i -1 , n)]$ 的引擎区间充能。

小蓝扔完之后，他想知道所有引擎的能量。作为小蓝的副手，你需要汇报每个引擎的能量值。

输入格式

第一行输入三个整数 $n,m,q$，代表飞船引擎数量，宝石的种类数量，小蓝开采的宝石数量。

第二行输入 $m$ 个整数 $s_1, s_2, s_3,...,s_i...,s_m$，代表每种宝石的能量，$s_i$ 表示第 $i$ 种宝石的能量。

接下来输入 $q$ 行，每行两个整数 $p, k$，代表小蓝将一个种类为 $p$ 的宝石扔到了第 $k$ 个引擎上。

输出格式

输出一行，$n$ 个整数，整数之间用一个空格隔开，表示充能结束后，每个引擎的能量。

样例输入

5 2 3
2 4
1 1
2 3
1 2

样例输出

1 1 2 1 1

说明

第一次，种类 $1$ 的宝石为区间 $[1,2]$ 充能，得到的能量为 $\lbrace 1, 1, 0, 0, 0\rbrace$。

第二次，种类 $2$ 的宝石为区间 $[3,5]$ 充能，得到的能量为 $\lbrace 1, 1, 1, 1, 1\rbrace$。

第三次，种类 $1$ 的宝石为区间 $[2,3]$ 充能，由于 $2$ 号引擎已经被 $1$ 类宝石充能过了，所以仅有 $3$ 号引擎被充能，得到的能量为 $\lbrace 1, 1, 2, 1, 1\rbrace$。

评测数据范围

$1 \le n ,m \le 10^5, 1 \le s_i \le 10^5, 1 \le p \le m, 1 \le k \le n$。

T6. 大风起兮【算法赛】

问题描述

大风起兮云飞扬。威加海内兮归故乡。安得猛士兮守四方！

小蓝站在家乡的山上，感受着来自于西西伯利亚的风，回忆着汉楚那悲壮的历史。

突然，一排气球引起了小蓝的注意。山崖上有一排栅栏，每个栅栏上都绑上了一个气球，我们可以按照从左到右的顺序给每个气球编号 $1 \sim n$，每个气球上都有一个数字 $p_i$。

小蓝知道，那是古老的祭祀仪式，用来缅怀逝去的亲人，当每一个气球被风吹走时，就代表亲人随风去到了天堂。

小蓝是个善于思考的人，他想到了一个问题，当一个气球飞走后，剩下的气球中，中位数是多少？

具体来说，初始存在 $n$ 个气球，编号为 $1 \sim n$，每个气球有一个权值 $p_i$，每一秒，会有一个编号为 $x_i$ 的气球随风飘走，小蓝想知道每飘走一个气球，剩下的气球按照权值排序后，中位数是多少？

中位数：对于一个长度为 $n$，并且已经排好序的序列 $a$ 来说，如果 $n$ 为奇数，那么中位数为 $a_{\frac {n+1} {2}}$；如果 $n$ 为偶数，那么中位数为 $\frac {a_{\frac {n} {2}} + a_{\frac {n} {2} + 1}} {2}$。

输入格式

第一行输入一个整数 $n$，表示气球的数量。

第二行输入 $n$ 个整数 $p_1, p_2, p_3, ... , p_i , ... p_n$，代表每个气球的权值。

第三行一个整数 $q$，代表会有 $q$ 个气球飘走。

第四行输入 $q$ 个整数 $x_1, x_2, ..., x_q$，代表第 $i$ 秒编号为 $x_i$ 的气球会飘走。

输出格式

输出一行，包含 $q$ 个浮点数 $a_1, a_2, a_3, ..., a_q$，代表第 $x_i$ 个气球飘走后，剩下的气球经过排序后，中位数是 $a_i$。每个数保留一位小数，每两个数之间用一个空格隔开。

样例输入

6
1 8 3 4 6 2
3
2 4 3

样例输出

3.0 2.5 2.0

说明

• 第一秒后，第 $2$ 个气球飘走，剩下的气球经过排序后：$1,2,3,4,6$。
• 第二秒后，第 $4$ 个气球飘走，剩下的气球经过排序后：$1,2,3,6$。
• 第三秒后，第 $3$ 个气球飘走，剩下的气球经过排序后：$1,2,6$。

评测数据范围

$1 \le q \lt n \le 2 \times 10^5, 1 \le p_i \le 10^9, 1 \le x_i \le n$。

保证 $x_i$ 各不相同。

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

T7. 时空追捕【算法赛】

问题描述

时空局的一周有 $11$ 天，这一天，时空局发布紧急任务，有一个时空战犯在今后 $n$ 天的时间线中进行逃窜，由于时空的独特性，我们可以把时间看成节点，也就是每一天看成一个节点。每一天会有一个能量值 $g_i$，我们定义函数 $h(x)$ 为 $x$ 在十进制下的数位和，例如 $h(192) = 1 + 9 + 2 = 12$，同时定义 $f(x)$：

$$f(x) = \begin{cases} x \quad (x \lt 10) \\\\ f(h(x)) \quad (x \ge 10) \end{cases}$$

当两个时间节点满足 $f(g')$ 相同时，那么这两个时间可以相互传送；或者两个时间点恰好相隔一周时，也可以相互传送。

一个战犯在 $1 \sim n$ 的时间节点中逃窜，时空局会派出若干的时空战警，每个战警会选择一个任意节点 $S_t$ 作为起始节点然后选择一些时间节点开始巡逻，具体来说，需要满足以下性质，假设该时空战警巡逻的点为 $a_1,a_2,a_3,...,a_k$，那么需要满足以下条件：

1. $a_1 \lt a_2 \lt a_3 \lt ... \lt a_k$。
2. 对于 $i \gt 1$，需要满足 $f(g_{a_i}) = f(g_{a_{i-1}})$ 或者满足 $|g_{a_i}$ - $g_{a_{i-1}}| = 11$。

同时由于时空串扰的关系，每两个时空战警之间巡逻的时空节点之间不能存在相同的点，例如：$A$ 战警巡逻 $\lbrace 1, 4, 5\rbrace$，$B$ 战警巡逻 $\lbrace 2, 3, 6\rbrace$，这是合法的；但是如果$B$ 战警巡逻 $\lbrace 2, 3, 4\rbrace$，就会发生时空串扰，产生不可预料的后果。

时空局都是一群很聪明的人，他们想要派出最少的人，使得每一个时空节点都会至少有一个时空战警巡逻到。

于是时空局伟大的机器 Timer 开始计算，当派出 $1$ 个人的时候，最多可以巡逻到多少个点？当派出 $2$ 个人的时候，最多可以巡逻多少个点？ ······ 当派出 $n$ 个人的时候最多可以巡逻多少个点？

突然，时空光圈发出巨大的光芒，你回过神来发现，你变成了 Timer，你开始执行这些计算任务。

具体来说，你需要回答当派出 $1 \sim n$ 个人时，分别最多可以巡逻到多少个时空节点。

输入格式

第一行输入一个整数 $n$，表示时空节点的数量。

第二行输入 $n$ 个整数 $g_1, g_2, g_3, ..., g_i ,..., g_n$，表示第 $i$ 天的能量值。

输出格式

输出一行，包含 $n$ 个整数 $t_1, t_2, t_3, ..., t_n$，用空格隔开，表示在派出 $i$ 个人时可以巡逻的最多的节点数量。

样例输入

4
9 29 45 32

样例输出

2 3 4 4

说明

• 派出一个人时，一种最多的巡逻方案是：$\lbrace 1,3 \rbrace$。
• 派出两个人时，一种最多的巡逻方案是：$\lbrace 1,3 \rbrace, \lbrace 2 \rbrace$。
• 派出三个人时，一种最多的巡逻方案是：$\lbrace 1,3 \rbrace, \lbrace 2 \rbrace, \lbrace 4 \rbrace$。
• 派出四个人时，一种最多的巡逻方案是：$\lbrace 1 \rbrace,\lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace$。

评测数据范围

$1 \le n \le 5000, 1 \le g_i \le 10^9$。