早上7：30，我们来到了这与我们泉州第一中学有长达2个汉字的最长公共子序列的中山纪念中学。
上午
打比赛—-2025.08.03【提高B组】模拟赛
传送门
T1
题目描述
Bitaro 喜欢园艺，现在正在自己的花园种 Biba 草，花园里共
有 N 棵 Biba 草，从西向东排成一行，自西向东编号 1 到 N ,
第 i 棵高度是 A i。
因品种改良，浇一次水对应 Biba 草高度加 1 。Bitaro 浇水
要让改良后高度 B i 满足：存在整数 k(1≤k≤N) ，使 1≤j≤k−1
时 B j B j+1（即高度先递增到
某点 k，再递减 ）。
但 Bitaro 浇水只能选区间 [L,R] （1≤L≤R≤N ），给第 L
到 R 棵浇水，他想最小化浇水次数，需写程序，根据 Biba 草数
量和当前高度，计算满足条件最少浇水次数 。
输入
第一行一个整数N
第二行N个整数Ai
输出
输出一行一个整数，表示浇水的最少次数
赛时思路：
找规律即可
时间复杂度 O(n)
赛时代码:
标程思路：
找规律即可
时间复杂度 O(n)
标程代码:
T2
题目描述
小 D 最近发现一款小游戏，规则如下：
游戏目标是按编号 1 - n 顺序杀掉 n 条巨龙，每条巨龙有初
始生命值a i，还有恢复能力,使用恢复能力时生命值每次加p i,
直至非负，且仅在攻击结束后生命值恰好为 0 时才死亡。
游戏开始玩家有 m 把攻击力已知的剑，每次面对巨龙选一把,
杀死巨龙后剑消失，会获得新剑。
小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得ION
2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关
这款游戏，她写的机器人遵循以下规则：
每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨
龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的
剑,则选择攻击力最低的一把剑作为武器。
机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙
固定的 x 次，使巨龙的生命值减少 x * ATK 。
之后，巨龙会不断使用恢复能力，每次恢复 p i 生命值。若在
使用恢复能力前或某一次恢复后其生命值为 0 ，则巨龙死亡，玩
家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关
键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道
应该将机器人的攻击次数 x 设置为多少，才能用最少的攻击次数
通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出 -1 即可。
输入
第一行是整数 T，代表数据的组数。
接着是 T 组数据，每组数据包含 5 行内容：
每组数据的第一行有两个整数 n 和 m，分别表示巨龙的数量以
及初始剑的数量。
随后一行有 n 个正整数，第 i 个数对应第 i 条巨龙的初始
生命值 a i。
再一行有 n 个正整数，第 i 个数是第 i 条巨龙的恢复能力
p i。
接着一行有 n 个正整数，第 i 个数为杀死第 i 条巨龙后奖
励剑的攻击力。
最后一行有 m 个正整数，代表初始拥有的 m 把剑的攻击力.
输出
输出行数：共 T 行（T 为数据组数 ）
每行内容：第 i 行是第 i 组数据对应的结果，即能让机器人
通关游戏的最小攻击次数 x ；若无法通关，输出 -1 。
赛时思路：
对于测试点 1 ~ 4，用为 p_i=1，所以只要求一个 x 使得 a_i-x \times atk_i \leq 0 即可
时间复杂度 O(n)
对于测试点 8 ~ 13，暴力枚举 x 即可
期望分数 50 分
时间复杂度 O(atk_1)
赛时代码:
标程思路：
中国剩余定理+平衡树+扩展欧几里得
标程代码:
