T4
CSP-S 2023 种树
显然答案有单调性,考虑二分答案 \(t\)。
二分有什么好处呢?就是可以知道每棵树最坏在哪天种才能达到 \(a_i\) 的高度。(不二分是做不到的,因为 \(x\) 是从 \(1\) 开始计数的。)
而这个部分显然又可以通过二分解决,比如说二分了一个 \(l\),只需要 \([l, t]\) 这段时间内长的高度达到 \(a_i\) 即可。分 \(c_i < 0\) 与 \(c_i \ge 0\) 讨论一下,用个等差数列求和公式快速算出。(注意一些爆 int, long long
的地方,题目有好的保证答案 \(\le 10^9\))
bool check(int u, int l, int r) { // u 地块的树,从 l 时刻长到 r 是否够ll vr = b[u] + 1ll * r * v[u]; // v 即题目中的 cll vl = b[u] + 1ll * l * v[u];// 加一些特判if (max(vl, vr) >= a[u]) return 1;if (l > rr[u]) return r - l + 1 >= a[u];if (v[u] >= 0) {return ((i128)(vl + vr) * (r - l + 1) / 2 >= a[u]); // CSP 应该可以用 __int128}int r1 = min(r, rr[u]);return (i128)(vl + b[u] + r1 * v[u]) * (r1 - l + 1) / 2 + r - r1 >= a[u];
}
设第 \(i\) 块地的树最坏在第 \(ti_i\) 天种下。
接下来怎么做呢?考虑一个贪心。
显然 \(ti\) 越小的越紧迫,所有按 \(t_i\) 排序,然后按这个顺序种即可(将 \(i\) 的祖先都种上)。
证明考虑临项交换法应该不难证出来。
时间复杂度:\(O(n \log^2 V)\)。
这个主要要想到二分,求对 \(ti_i\)(两年前太弱了,磕了 \(2h\) 没磕出来),贪心还是挺符合直觉的(想 DP 的话其实是不知道策略的)。