526互联

[CSP-S 2023] 种树

发布时间 2023-12-13 17:49:38作者: Light_starup

[CSP-S 2023] 种树

Part - 1

特殊性质 B

将种树时间设为 \(l\)，结束时间为 \(r\)，则可以把数的高度记作：

\[\sum_{i = l}^r\max(1, b_i + x \times c_i) \]

分类讨论：

  1. \(c_i \ge 0\)

可以表示为 \(b_i \times (r - l + 1) + \frac{(r - l + 1) \times (r + l)}{2} \times c_i\)

  1. \(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\)
    那么这时无时间段 \(\max(1, b_i + x \times c_i) = 1\)，那么可以得到：

    \[\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 \]

  • \(x < l\)
    此时从种树的第一天开始都只增加 \(1\)，那么这时很好表示：

    \[r - l + 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;
}