CF1956E2 Nene vs. Monsters (Hard Version)
Kingna
·
·
题解
如果连续四只怪物的血量为 x,y,z,w ，并且它们在 t 回合后没有死亡，那么 y 将受到至少 t 点伤害， z 将受到至少 (t-1) +(t-2)+\cdots=O(t^2) 点伤害， w 将受到至少 O(t^3) 点伤害。
设 V=\max_{i=1}^n a_i。在 O(\sqrt[3]{V}) 个回合后， x,y,z,w 中至少会有一个怪死亡。
坑点注意：处理的连通块的时候要连通首尾。比如：$x,y,0,\dots,z$ 这个数列，若最开始只处理 $x,y$ 连通块，$y$ 就会变成 $0$。但实际操作中，$z$ 可能会将 $x$ 变为 $0$，然后 $y$ 如果特别大则 $x$ 根本无法将 $y$ 变为 $0$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
const int N = 2e5 + 5;
int n, a[N], b[N], c[N];
vector<int> ans, ans1;
int get(int x) {
if (x + 1 <= n) return x + 1;
if (x == n) return 1;
}
signed main() {
int T = 0;
cin >> T;
while (T--) {
ans.clear();
cin >> n;
int maxn = 0;
_for(i, 1, n) cin >> a[i], c[i] = a[i], maxn = max(maxn, a[i]);
int t = cbrt(maxn) * 2 + 20;
_for(j, 1, t) {
_for(i, 2, n) a[i] = max(0ll, a[i] - a[i - 1]);
a[1] = max(a[1] - a[n], 0ll);
}
int id = 0;
_for(i, 1, n) {
if (!a[i]) {
id = i;
break;
}
}
_for(i, 2, id) a[i] = max(0ll, a[i] - a[i - 1]); // 为了避免上述情况，先将开头手动处理
int i = id;
_for(w, 1, 2 * n) {
int x = get(i), y = get(x);
if (!a[i]) {
i = get(i);
continue;
}
if (a[x]) {
a[y] = max(0ll, a[y] - (a[x] / a[i]) * a[x] + a[i] * (1 + a[x] / a[i]) * (a[x] / a[i]) / 2);
a[x] = 0;
}
i = get(i);
}
_for(i, 1, n) if (a[i]) ans.push_back(i);
cout << ans.size() << endl;
for (auto v : ans) cout << v << ' ';
puts("");
}
}
```