1209 第 1 场 小白入门赛/强者挑战赛

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

T1. 蘑菇炸弹【算法赛】

问题描述

题莫作为 《 XX 联盟》 最受欢迎的人气英雄，用其独有的技能机制荣获光荣头衔 —— 团战可以输，题莫必须死。

具体地说，题莫种下了 $n$ 个蘑菇炸弹，其中第 $i(i\in[1,n])$ 个蘑菇的爆炸能力为 $a_i$。为此，瓦罗兰大陆著名的拆弹专家及格撕，受命来拆除这 $n$ 个蘑菇炸弹，但他时间有限，只愿拆除那些高爆蘑菇炸弹。

若一个蘑菇炸弹满足以下条件则被称为高爆蘑菇炸弹。

• $2 \leq i \leq n-1$。
• $a_i \ge a_{i-1}+a_{i+1}$。

请你帮及格撕求出高爆蘑菇炸弹的数量。

输入格式

第一行输入一个整数 $n$，表示题莫种下的蘑菇炸弹的数量。

第二行输入 $n$ 个整数 $a_1,a_2,a_3, \cdots,a_n$，表示每个蘑菇炸弹的爆炸能力。

输出格式

输出一个数字，表示高爆蘑菇炸弹的数量。

样例输入

5
1 2 4 2 1

样例输出

1

说明

样例中只有第三个蘑菇炸弹可以被称为高爆蘑菇炸弹。

评测数据范围

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

T2. 小蓝的金牌梦【算法赛】

问题描述

刚上大一的小蓝，励志成为一名成功的 $\text{acmer}$，斩获金牌。

最近，小蓝刚学习了经典问题中的最大子数组和问题。最大子数组和问题是 ACM 竞赛选手入门必学的一个问题，它要求在给定数组 $a$ 中选取一段连续子数组，使得该子数组的元素和达到最大值。

当然小蓝对自己的要求比较高，恰巧他刚学习了质数的知识，他想知道如果选取的子数组长度必须为质数的情况下，最大的子数组和能是多少呢？

请你帮忙解决这个问题。

输入格式

第一行输入一个正整数 $n$ 表示数组长度。

第二行输入 $n$ 个整数 $a_1,a_2,a_3, \cdots,a_n$。

输出格式

输出一个整数，表示长度为质数的最大子数组和。

样例输入

6
1 2 3 4 5 6

样例输出

20

说明

样例选取长度为 $5$ 的子数组 $[2,3,4,5,6]$，可以得到最大子数组和为 $20$。

评测数据范围

$2 \leq n \leq 10^5$，$-10^5 \leq a_i \leq 10^5$。

T3. 构造数字【算法赛】

问题描述

在一个宁静的早晨，迪迦奥特曼突然发现了一个奇特的物体。这个物体是一个来自未知星球的超级数字计算器。这个计算器拥有强大的功能，可以计算出任何数字的结果，甚至可以解析出数字之间的深层次联系和规律。

随着时间的推移，迪迦奥特曼的数字能力变得越来越强大。他不仅可以快速计算出复杂的数字结果，还可以理解数字背后的深层含义和规律。他的这种能力让他可以在战斗中更好地应对各种挑战，因为数字和规律往往可以揭示出敌人的弱点和突破口。

现在迪迦奥特曼有一个十进制下的 $N$ 位正整数，但他忘记这个数的具体数值，只记得每一位的数码之和不超过 $M$，他想知道在所有可能中，这个数最大可能是多少。即用 $f(x)$ 表示十进制下 $x$ 每位数码之和，例如 $f(114)=1+1+4=6$，给定 $N,M$，求最大的 $N$ 位十进制数 $x$，满足 $f(x) \leq M$。

输入格式

第一行包含 $2$ 个正整数 $N,M$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案。

样例输入

3 1

样例输出

100

评测数据规模

对于所有测评数据，$1 \leq N,M \leq 10^6$。

T4. 数对统计【算法赛】

问题描述

在奥特曼的世界中，也存在着很多选拔性考试，其中在一门名叫奥特曼数理基础的课程中，异或位运算和加法运算是赛文奥特曼每天都要面对的问题。他发现，这两种运算虽然看起来完全不同，但实际上它们之间存在着一种深度的联系。赛文奥特曼对异或运算和加法运算之间的联系非常好奇，他总觉得二者之间隐隐有某种联系，所以他想让你求解下列关于异或和加法的问题。

给定长度为 $N$ 的序列 $\\{a\\}$，求有多少对 $(i,j)$ 满足 $1 \leq i,j \leq n$，且 $a_i ⊕ a_j=a_i+a_j$，其中 $⊕$ 表示异或操作。

输入格式

第一行包含 $1$ 个正整数 $N$。

第二行包含 $N$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案。

样例输入

3
0 1 3

样例输出

5

样例解释

合法解有 $(1,1),(1,2),(2,1),(1,3),(3,1)$。

评测数据规模

对于所有测评数据，$1 \leq N \leq 10^6,0 \leq a_i < 2^{20}$。

T5. 合并石子加强版【算法赛】

问题描述

迪迦奥特曼，这位跨越宇宙的守护者，除了在战斗中展现出色的英勇和力量外，还有一个颇为奇特的兴趣 —— 他对石子情有独钟。

迪迦奥特曼从不仅仅将石子视为普通的地质材料，而是将它们看作一种富有哲学深度的存在。在他的眼中，每一块石子都是自然演化的产物，承载着地球的岁月和历史。他迷恋于石头表面的纹理、颜色以及它们在自然界中的形成过程。

现在有 $n$ 堆石子围成一个环，第 $i$ 堆有 $a_i$ 个石子，每次迪迦奥特曼可以选择相邻的 $2$ 堆石子，将这两堆石子合并，合并后的石子个数为两堆石子个数之和，合并的代价为两堆石子个数之积，迪迦奥特曼想知道将这 $n$ 堆石子合并成 $1$ 堆的最小代价。

以下给出两堆石子相邻的解释：

假设现在有 $n$ 堆石子 $(n \geq 2)$ ，石子两堆石子 $i,j$ 是相邻的，当且仅当 $|i - j|=1$ 或 $|i-j|=n-1$。

输入格式

第一行包含 $1$ 个正整数 $n$。

第二行有 $n$ 个正整数，第 $i$ 个表示权值 $a_i$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案。

样例输入

3
1 2 1

样例输出

5

评测数据规模

对于所有测评数据，$1 \leq n \leq 3\times 10^4, 1 \leq a_i \leq 2 \times 10^5$。

T6. 简单的 LIS 问题【算法赛】

问题描述

最长上升子序列（Longest Increasing Subsequence），简称 LIS，指的是一个序列中最长的一个子序列，满足其单调递增。

例如，对于一个序列 $a_1, a_2, a_3, a_4,...,a_i,...,a_n$，存在一个序列 $b_1, b_2,..., b_m$，满足：

1. $1 \le b_1 \lt b_2 \lt ... \lt b_m \le n$。
2. $a_{b_1} \lt a_{b_2} \lt ... \lt a_{b_m}$。

那么我们称 $\lbrace a_{b_1} , a_{b_2} , ... , a_{b_m} \rbrace$ 为 $\lbrace a_i \rbrace$ 的一个上升子序列。

最长的上升子序列就是最长（元素数量最多）的一个上升子序列。

小蓝学到了这个知识点，并且学会一些用来计算 LIS 的常见算法。

于是小蓝向邻居小桥炫耀他学到的新知识，但是小桥显然不会让小蓝如此得意，于是他提出了一个新的问题：

给定一个长度为 $n$ 的序列 $\lbrace a_i \rbrace$，小蓝可以选择其中的一个位置，修改为 $0 \sim 10^{100}$ 中的任何一个整数。具体来说，小蓝可以选择一个位置 $p(p \in [1, n])$，将 $a_p$ 重新赋值为 $0 \sim 10^{100}$ 中的任意一个整数。请问修改过后，最长上升子序列的长度是多少？

小蓝看到这个问题，两眼一抹黑，于是请你帮他解决这个问题。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_i, ... ,a_n$，用来表示序列 $a$ 的每个值。

输出格式

输出一个整数，表示修改后的最长上升子序列长度。

样例输入

5
2 5 4 3 7

样例输出

4

说明

修改 $3$ 为 $5$，得到 $2,5,4,5,7$，得到最长上升子序列为 $2,4,5,7$。

评测数据范围

$1 \le n \le 5 \times 10^3, 0 \le a_i \le 10^9$。

T7. 期望次数【算法赛】

问题描述

戴拿奥特曼，这位来自“光之国”的宇宙守护者，以保卫地球免受邪恶怪兽侵袭而闻名。然而，除了他在战斗中的英勇表现，戴拿奥特曼也是一个对概率类问题极感兴趣的奇特存在。

在与怪兽的战斗中，戴拿奥特曼经常需要面对各种各样的不确定性和随机性。例如，他不知道下一个怪兽会从哪里出现，以及它具有什么样的力量和攻击方式。这种不确定性使得戴拿奥特曼必须在战斗中做出迅速而准确的决策，以最大程度地提高战胜怪兽的概率。

现在戴拿奥特曼遇到了一个非常棘手的概率问题，请你帮助他解决。

给定长度为 $N$ 的序列 $\\{p\\}$，初始时有一个正整数 $x=1$，不断进行如下操作：

1. 若 $x \geq M$，则操作结束

2. 否则以 $\frac{p_i}{\sum_{j=1}^N p_i}$ 的概率，使得 $x$ 变为 $x \times i$

请你求出期望进行的步骤 $2$ 的次数，答案对 $998244353$ 取模。

输入格式

第一行包含 $2$ 个正整数 $N,M$。

第二行有 $N$ 个正整数，第 $i$ 个表示权值 $p_i$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入

4 10
1 1 1 1

样例输出

529932191

评测数据规模

对于所有测评数据，$2 \leq N,M \leq 10^5, 1 \leq p_i,\sum_{i=1}^N p_i < 998244353$。

T8. 小球碰撞【算法赛】

问题描述

在奥特曼的世界中，物理是一门解释宇宙规律和自然现象的学科，它为奥特曼提供了理解和掌控力量的钥匙。对物理的深入理解和研究，使奥特曼能够更好地掌握自己的力量，并运用这些力量来保护地球和宇宙的和平。

梦比优斯奥特曼对物理的兴趣始于他对宇宙奥秘的探索。他发现，物理中的力学、电磁学、光学、量子力学等理论，可以解释他在战斗中所遇到的各种现象。例如，他利用力学原理来理解宇宙中的重力、加速度和惯性等力量，这些力量在他的战斗中起着关键作用。

现在，梦比优斯奥特曼希望你求解以下物理问题。

数轴上有 $N$ 个小球，小球可看作质点，第 $i$ 个小球初始时位于 $p_i$，且每秒以 $v_i$ 的速度运动，当 $v_i>0$ 时表示小球以每秒 $|v_i|$ 的速度向右运动，当 $v_i<0$ 时表示小球以每秒 $|v_i|$ 的速度向左运动，否则表示小球静止。

初始时你可以选择 $K$ 个小球从数轴上移去，此时记作时间 $T=0$，，你需要找到最大的时间 $T'$，使得满足一种移除 $K$ 个小球的方案，在 $T\in[0,T']$ 内均无小球发生碰撞，答案下取整保留为整数，特别地，如果 $T'=+∞$，输出 $-1$。

输入格式

第一行包含 $2$ 个正整数 $N,K$。

之后 $N$ 行，每行有 $2$ 个整数，表示权值 $p_i,v_i$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案。

样例输入

4 1
1 3
13 2
25 1
37 2

样例输出

11

评测数据规模

对于所有测评数据，$1 \leq K < N \leq 10^5,\forall 1 < i < j \leq N,p_i ≠ p_j,-10^9 \leq p_i,v_i \leq 10^9$。