https://qoj.ac/contest/4607。
D
设两人的血量为 \(x,y\)。
注意到 \(x \le 4b\) 时 Cat 不可能赢。其余情况，计算 \(x\) 到 \(4b\) 的剩余轮数，分别用 \(b,2b,4b\) 去消耗，并判断这些轮次后是否有 \(y \le 0\) 即可。容易说明混用两种攻击方式不优。
注意开 int128。
#define int __int128
int a, b, x, y;void _main() {cin >> a >> b >> x >> y;if (x <= 4 * b) return cout << "NO\n", void();int k = (x - 4 * b + b - 1) / b;if (y - k * a > 0) return cout << "NO\n", void();k = (x - 4 * b + 2 * b - 1) / (2 * b);if (y - k * 2 * a > 0) return cout << "NO\n", void();k = (x - 4 * b + 4 * b - 1) / (4 * b);if (y - k * 4 * a > 0) return cout << "NO\n", void();cout << "YES\n";
}
M
题意：给定 \([l_i,r_i]\)，确定 \(a_i \in [l_i,r_i]\) 使得 \(a_1 \sim a_n\) 前缀 \(\max\) 数目最小。
显然决策 \(a_i\) 成为前缀 \(\max\) 时必选定 \(a_i=r_i\)。
考虑从左到右依次决策，若 \(l_i\) 大于前缀 \(\max\) 则必选。否则，从 \(i\) 开始向右暴力扫描，直到最近的 \(l_i\) 大于 \(\max\) 的位置，并记录沿途 \(\max\) 取到的点。钦定这个点即可。
复杂度均摊线性。
const int N = 1e6 + 5, inf = 2e9;
int n, l[N], r[N];
using node = pair;void _main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> l[i] >> r[i];}int cur = -inf, cnt = 0;for (int i = 1; i <= n; i++) {if (l[i] > cur) {cur = r[i], cnt++; continue;}int j = i+1, mx = -inf, p = -1;for (; j <= n; j++) {if (r[j] > mx) mx = r[j], p = j;if (l[j] > cur) break;}if (j == n+1) break;if (r[i] > mx) cur = r[i], cnt++, i = j;else i = p - 1;}cout << cnt << '\n';
}
L
二分答案 \(k\)，只要 \(\forall i, |a_i-b_i| \le k\)。列出 \(a_i-b_i \le k \land b_i-a_i \le k\)，进而 \(b_i \in [a_i-k,a_i+k]\)。
维护 \(S\) 为可行的 \(b_i\) 集合。扫描 \(i=1\to n\)，由 \(|b_i-b_{i-1}| \ge l_i\) 推知 \(b_i \le b_{i-1}-l_i \land b_i \ge b_{i-1}+l_i\)。
只要记录 \(\min S\) 和 \(\max S\)。扫到 \(i\) 时将两个范围取交集，不交则无解。否则更新 \(S\) 的上下界即可。
#define int long long
const int N = 1e5 + 5, inf = 2e9+1;
int n, a[N], l[N];bool check(int k) {int lo = a[1] - k, hi = a[1] + k;for (int i = 2; i <= n; i++) {int x = a[i] - k, y = a[i] + k;bool fl = x <= hi - l[i];bool fr = y >= lo + l[i];if (!fl && !fr) return false;tie(lo, hi) = mkpair(fl ? x : max(x, lo + l[i]),fr ? y : min(y, hi - l[i]));} return true;
}void _main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 2; i <= n; i++) cin >> l[i];int l = 0, r = 2e9, res = -1;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) res = mid, r = mid - 1;else l = mid + 1;}cout << res << '\n';
}