[CSP-S 2023] 种树
Part - 1
特殊性质 B
将种树时间设为 \(l\)，结束时间为 \(r\)，则可以把数的高度记作：
\[\sum_{i = l}^r\max(1, b_i + x \times c_i) \]分类讨论：
- \(c_i \ge 0\)
可以表示为 \(b_i \times (r - l + 1) + \frac{(r - l + 1) \times (r + l)}{2} \times c_i\)
- \(c_i < 0\)
先算出多少天之后 \(\max(1, b_i + x \times c_i) = 1\) 也就是 \(b_i + x \times c_i \le 1\)，得到临界点为 \(x = \lfloor \frac{1 - b_i}{c} \rfloor\)。
-
\(x > r\)
\[\sum_{i = l}^r(b_i + x \times c_i) = b_i \times (r - l + 1) + \frac{(r - l + 1) \times (r + l)}{2} \times c_i \]
那么这时无时间段 \(\max(1, b_i + x \times c_i) = 1\)，那么可以得到： -
\(x < l\)
\[r - l + 1 \]
此时从种树的第一天开始都只增加 \(1\)，那么这时很好表示： -
\(l \le x \le r\)
\[b_i \times (maxn - l + 1) + \frac{(maxn - l + 1) \times (maxn + l)}{2} \times c_i \]
首先要算出没有到临界点之前的：再算出临界点之后的：
\[r - maxn \]加起来得到
\[b_i \times (maxn - l + 1) + \frac{(maxn - l + 1) \times (maxn + l)}{2} \times c_i + r - maxn \]
因为是链所以树种下去的时间一定是按照编号递增的，也就是第 \(i\) 天就会种下第 \(i\) 号树，所以我们可以取所有树 \(l = i\)，完成时的 \(r\) 的值的 \(\max\)。
Code
#include <bits/stdc++.h>
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; ++i)
using namespace std;
inline int read(){
int f = 1,x = 0;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-')f = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void print(int x){
if(x > 9)print(x / 10);
putchar(x % 10 + '0');
}
int n, b[100010], c[100010];
long long a[100010];
struct side{
int to, next;
}s[200010];
int head[100010], tot;
inline void add(int from, int to){
s[++tot] = side{to, head[from]};
head[from] = tot;
}
inline bool check(int x, __int128 l, __int128 r){
if(c[x] >= 0)return b[x] * (r - l + 1) + c[x] * (l + r) * (r - l + 1) / 2 >= a[x];
__int128 maxn = (1 - b[x]) / c[x];
if(maxn < l)return r - l + 1 >= a[x];
else if(maxn > r)return b[x] * (r - l + 1) + c[x] * (l + r) * (r - l + 1) / 2 >= a[x];
else return b[x] * (maxn - l + 1) + c[x] * (l + maxn) * (maxn - l + 1) / 2 + r - maxn >= a[x];
}
signed main(){
n = read();
For(i, 1, n)
scanf("%lld", a + i), b[i] = read(), c[i] = read();
For(i, 1, n - 1){
rint u = read(), v = read();
add(u, v);
add(v, u);
}
int ans = 1;
For(i, 1, n){
int l = 1, r = 1e9;
while(l < r){
int mid = l + (r - l) / 2;
if(check(i, i, mid))r = mid;
else l = mid + 1;
}
ans = max(ans, r);
}
cout << ans;
return 0;
}
Part - 2
特殊性质 A
不难发现，此时 \(t_i = \lceil \frac{a_i}{b_i} \rceil\) ，此时有贪心策略，先将 \(t\) 大的满足，此时我们需要将 \(i\) 所有 \(i\) 到 \(1\) 的路径上的所有节点种上树，可以发现是一个从子节点到根节点的过程，同时需要倒序取出，可以使用栈，那么需要的时间就是种树的时间 \(x + t_i\) 的最大值。
Code
#include <bits/stdc++.h>
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; ++i)
using namespace std;
int n;
struct side{
int to, next;
}s[200010];
int head[100010], tot;
inline void add(int from, int to){
s[++tot] = side{to, head[from]};
head[from] = tot;
}
int fa[100010];
inline void dfs(int u, int f){
fa[u] = f;
for(int i = head[u]; i; i = s[i].next){
if(s[i].to != f)dfs(s[i].to, u);
}
}
int p[100010], t[100010];
bool vis[100010];
int stacks[100010], top = 0;
signed main(){
scanf("%d", &n);
For(i, 1, n){
long long a;
int b, c;
scanf("%lld%d%d", &a, &b, &c);
t[i] = a / b;
p[i] = i;
}
For(i, 1, n - 1){
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
cout << 1;
dfs(1, 0);vis[0] = 1;
sort(p + 1, p + 1 + n, [](int a, int b){return t[a] < t[b];});
int ans = 0;
for(int i = 1, x = 0; i <= n; i++){
int now = p[i];
while(!vis[now])vis[stacks[++top] = now] = 1, now = fa[now];
while(tot)ans = max(ans, x++ + t[stacks[top--]]);
}
cout << ans;
return 0;
}
有了以上两个特殊性质，正解就不难想了：
AC Code
#include <bits/stdc++.h>
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; ++i)
using namespace std;
int n, b[100010], c[100010];
long long a[100010];
struct side{
int to, next;
}s[200010];
int head[100010], tot;
inline void add(int from, int to){
s[++tot] = side{to, head[from]};
head[from] = tot;
}
int fa[100010];
inline void dfs(int u, int f){
fa[u] = f;
for(int i = head[u]; i; i = s[i].next){
if(s[i].to != f)dfs(s[i].to, u);
}
}
inline __int128 check(int x, __int128 l, __int128 r){
if(c[x] >= 0)return (r - l + 1) * b[x] + (l + r) * (r - l + 1) / 2 * c[x];
__int128 maxn = (1 - b[x]) / c[x];
if(maxn < l)return r - l + 1;
else if(maxn > r)return (r - l + 1) * b[x] + (l + r) * (r - l + 1) / 2 * c[x];
else return (maxn - l + 1) * b[x] + (l + maxn) * (maxn - l + 1) / 2 * c[x] + r - maxn;
}
int p[100010], t[100010];
bool vis[100010];
int stacks[100010];
inline bool solve(int s){
for(int i = 1; i <= n; i++){
if(check(i, 1, s) < a[i])return 0;
int l = 1, r = n;
while(l < r){
int mid = (l + r + 1) >> 1;
if(check(i, mid, s) >= a[i])l = mid;
else r = mid - 1;
}
p[i] = i, t[i] = l, vis[i] = 0;
}
sort(p + 1, p + 1 + n, [](int a, int b){return t[a] < t[b];});
for(int i = 1, x = 0; i <= n; i++){
int now = p[i], top = 0;
while(!vis[now])vis[stacks[++top] = now] = 1, now = fa[now];
while(top) if(t[stacks[top--]] < ++x) return 0;
}
return 1;
}
signed main(){
scanf("%d", &n);
For(i, 1, n)
scanf("%lld%d%d", a + i, b + i, c + i);
For(i, 1, n - 1){
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
dfs(1, 0);vis[0] = 1;
int l = n, r = 1e9;
while(l < r){
int mid = (l + r) >> 1;
if(solve(mid))r = mid;
else l = mid + 1;
}
cout << r;
return 0;
}