题解 P7095 【[yLOI2020] 不离】
一扶苏一
·
2020-11-22 12:02:39
·
题解
B
Algorithm 1
考虑枚举初始属性。显然初始属性不会高于需求的最大值，然后用全排列爆搜每种穿装备顺序。时间复杂度 O(n! \times a \times b ) 。可以通过前三个子任务，期望得分 30 分。
Algorithm 2
注意到因为要先最小化第一个再最小化第二个，所以两个属性实际上是独立的。也即我们可以不考虑第二个属性，先通过枚举确定第一个属性的最小初始值是多少。然后在此基础上通过枚举确定第二个属性的最小初始值。穿装备的顺序同样可以全排列爆搜。这个算法与第一个算法的区别是，将 a 和 b 分开枚举，而不是乘起来。时间复杂度 O(n! \times \max(a, b)) 。可以通过前四个子任务，期望得分 40 分。
Algorithm 3
从算法 1 的基础上扩展，考虑去掉全排列枚举的部分。我们可以把所有的装备按照 a 值排序。人物的第一个属性增加时，把所有的 a 值不大于当前属性的装备用一个小根堆维护。这个小根堆以 b 为关键字。人物的第二个属性增加时，把堆中所有 b 不大于当前属性的装备取出并穿戴。也即堆里维护的是当前第一个属性符合要求但是第二个属性不符合要求的装备。
枚举初始属性后，每次需要 O(n \log n) 的时间 check 是否合法。总时间复杂度 O(a \times b \times n\log n) 。可以通过子任务 1,2,3,5，期望得分 40 分。
Algorithm 4
把算法 2 同样用算法 3 的方式替换掉全排列的部分，时间复杂度 O(\max(a, b) \times n \log n) ，可以通过前六个子任务，期望得分 60 分。
Algorithm 5
#### Algorithm 6
把装备按照 $a$ 值排序，check 时扫一遍装备就能确定是否合法了。也就是把算法 3 的前半部分拿过来替换算法五的全排列。时间复杂度 $O(n \log n \log a)$，可以通过子任务 7,8，期望得分 20 分。结合算法 4 可以得到 80 分。
#### Algorithm 7
通过算法 3 的结论，两个属性是独立的。因此可以用算法 5 的方式先二分确定第一个值，然后再二分第二个值，全排列 check 即可。时间复杂度 $O(n! \log\max(a, b))$，可以通过子任务 1,2,3,4,7,9，期望得分 60 分。
#### Algorithm 8
如果选手没有发现两个属性相互独立，但是会使用算法 3 的方式维护装备，写二分套二分内层 check 可以得到一个 $O(n \log n \log a \log b)$ 的算法。可以得到 90 分。如果大力卡常，有可能得到 100 分。
#### Algorithm 9
把算法 7 中的全排列 check 用算法 3 中的堆 check 替换，则得到了一个时间复杂度为 $O(n \log n \log\max(a,b))$ 的算法，可以通过全部的测试点，期望得分 100 分。
#### Algorithm 10
事实上可以发现 $a$ 是不需要二分的。把装备按照 $a$ 排序以后，维护一个数组 $t_i$ 表示穿戴完前 $i$ 件装备以后的 $a$ 值最小达到了多少。再对 $a$ 维护一个前缀和 $s_i$。显然 $t_n - s_n$ 就是初始的第一个属性值。在从 $i$ 转移到 $i + 1$ 的过程中，如果 $t_i \geq a_{i + 1}$，那么 $t_{i + 1} = t_i + c_{i + 1}$，否则 $t_{i + 1} = a_{i + 1} + c_i$。时间复杂度为 $O(n \log n \log b)$。可以通过全部的测试点，期望得分 100 分。std 写的是算法 9。
#### Sunmary
- 本题人口普查分 10 分，暴力分 30 分。
- 选手想到二分答案可以得到 50 分。
- 选手发现两个属性相互独立的性质可以得到 50 分。
- 选手会用堆维护可选装备可以得到 50 分。
- 上述三个主要 idea 相互组合，可以得到 $60 \sim 100$ 不等的分数。
- 本题在代码实现上并不困难，std 在 70 行左右，使用堆维护装备需要一点技巧，可以参考 std。
- 总的来说，本题部分分充足，样例良心，题意清晰，码量友好，可以较好的区分签到选手，暴力选手，基本功扎实的选手，善于发现性质的选手和能灵活运用数据结构的选手。是一道优秀的签到题。
```cpp
#include <cstdio>
#include <queue>
#include <algorithm>
const int maxn = 100005;
int T;
int n, ma, mb, fusu, zxy;
int a[maxn], b[maxn], c[maxn], d[maxn], tmp[maxn];
bool check1(long long x);
bool check2(long long x);
inline bool cmp(const int x, const int y) {
return a[x] < a[y];
}
int main() {
// freopen("forever7-1.in", "r", stdin);
// freopen("forever.out", "w", stdout);
scanf("%d%d", &T, &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d%d", a + i, b + i, c + i, d + i);
ma = std::max(ma, a[i]);
mb = std::max(mb, b[i]);
tmp[i] = i;
}
std::sort(tmp + 1, tmp + 1 + n, cmp);
for (int l = 0, r = ma, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (check1(mid)) {
fusu = mid;
r = mid - 1;
} else {
l = mid + 1;
}
for (int l = 0, r = mb, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (check2(mid)) {
zxy = mid;
r = mid - 1;
} else {
l = mid + 1;
}
printf("%d %d\n", fusu, zxy);
}
struct Cmp {
inline bool operator()(const int x, const int y) {
return b[x] > b[y];
}
};
bool check2(long long x) {
std::priority_queue<int, std::vector<int>, Cmp> Q;
int i = 1, j; long long y = fusu;
while (true) {
while ((i <= n) && (a[tmp[i]] <= y)) Q.push(tmp[i++]);
if (Q.empty()) {
return i > n;
}
bool flag = false;
while ((!Q.empty()) && (b[j = Q.top()] <= x)) {
flag = true;
Q.pop();
y += c[j];
x += d[j];
}
if (flag == false) return false;
}
}
bool check1(long long x) {
int i = 1;
while (x >= a[tmp[i]]) {
x += c[tmp[i]];
if (++i > n) return true;
}
return false;
}
```