20250726模拟赛T1
题目描述
小 Soup 最近迷上了一款游戏：世界征服者。在剧本模式里面，他总是因为没有把控好回合限制导致翻车。现在他模拟了一次简化版的世界征服者局面，要求你求出将敌军所有部队打死的回合最少是多少。
在一开始，小 Soup 有 2 个单位，第 1 个单位每回合可以发动一次攻击造成 a 伤害，第 2 个单位每回合可以发动一次攻击造成 b 伤害。对手有 \(n\)个单位，每个单位的血量为 \(h_i\)。求把这 \(n\) 个单位全部打死（血量降到 0 及以下）的最小回合数 \(ans\)。
输入格式
本题包含多组数据。
第一行一个整数 \(t\)，代表数据组数。
对于每组数据，第一行三个整数：\(n,a,b\)。
接下来一行\(n\)个数，第 ii 个数代表 \(h_i\)。
输出格式
仅一个数，代表回合数 \(ans\)。
输入输出样例
输入数据 1
2
3 1 2
4 3 2
6 2 3
1 1 4 5 1 4
输出数据 1
3
5
样例 1 解释
以下是对于第一组数据的解释。
第一回合：我方 1 号单位攻击敌方 2 号单位，我方 2 号单位攻击敌方 3 号单位。
第二回合：我方 1 号单位攻击敌方 2 号单位，我方 2 号单位攻击敌方 1 号单位。
第三回合：我方 1 号单位攻击敌方 2 号单位，我方 2 号单位攻击敌方 1 号单位，敌方全军覆没。
样例 2 输入输出
见选手目录下的 conqueror2.in 与 conqueror2.ans。
数据规模
设输出的答案为 ansan**s，保证 \(1≤n,a,b,h_i≤10^3,ans≤5×10^3,t≤4,1≤n,a,b,h_i≤10^3,ans≤5×10^3,t≤4\)
| 测试点 | n≤ | ans≤ | 其他限制 | 分值 |
|---|---|---|---|---|
| 1 | 10 | 50 | \(a,b,h_i≤10\) | 5 |
| 2 | 100 | 500 | \(a,b,h_i≤10\) | 5 |
| 3~4 | 200 | 1000 | \(a,b,h_i≤10\) | 10 |
| 5~7 | 200 | 1000 | 无 | 15 |
| 8~11 | 1000 | 5000 | \(a,b,h_i≤10\) | 20 |
| 12~20 | 1000 | 5000 | 无 | 45 |
题目描述
给定两个固定伤害值 \(a\) 和 \(b\)，以及 \(n\) 个敌方单位各自的血量 \(h_i\)，每回合可分配这两个伤害源的攻击到任意单位，求消灭所有敌方单位的最小回合数 \(T\)。
考场思路做法
当时一开始看到了两个东西打怪兽，完成任务，有次数限制（求次数最小值），就想到了之前做的一道状态设计惊艳我一整天的进程dp：luogu P2224
所以当时第一瞬间就把 \(a\) 用了多少次计入状态，\(b\) 最少用了多少次作为维护的值，另一维度是干掉了前 \(i\) 个也立马可以作为状态，但是当时做到这一步，就想的是设 \(f_{i,j}\) 指干掉前 \(i\) 个怪物，用了 \(j\) 个 \(a\) 时用的 \(b\) 的数量的最小值，然后就想转移。
当时想转移只能多一层枚举 \(k\) 也就是说大概要和当前这个怪用了 \(k\) 个 \(a\) 这玩意有关系，而且不能被覆盖，所以转移是 \(O(ans)\) 的，那么总时间复杂度应该是 \(O(ans^2 \times n \times T)\) 算下来 \(1e10\) 已经爆炸了，然后就想能不能 \(O(1)\) 转移，就想到了多设一维当前怪物的剩余血量就能 \(O(1)\) 转移。然后就以为自己想到了正解就写了，写完之后跑大样例发现怎么 \(a,b,h_i\) 是好几百，然后仔细一看体面发现我把最后一个特殊性质看成了整个题的数据范围，也就是我以为 \(a,b,h_i \le 10\) 的，然后就不会优化了
正解及反思
其实考场上已经基本上想出来正解了，就是第一个想法，然后观察转移方程式，拆开它就可以发现有一个东西可以用线段树维护，把转移做到 \(O(log_2\,n)\) 级别的，然后可以刚刚卡过。还有一个小孩哥的奇妙快速做法，薄纱std，我要先研究一下再来写
这道题我没有优化出来的根本原因是我设计的状态完全无法支持优化。状态总数都是 \(o(n^3)\) 级别的，再怎么优化转移也做不到优化，且三个维度之间完全独立，无法像之前的洛谷P5664那道题可以把两维作差优化到1维。
而且这次考试中我式子推出来了，但大样例一直有一个点有问题，最后才发现是边界问题，遍历少了一点，所以说之后写dp的时候一定要注意转移时的边界问题！