20261020

ABC369 G - As far as possible 黄

https://atcoder.jp/contests/abc369/tasks/abc369_g

其实等价于选择 i 个点，最大化最短走法路径

所以我们可以考虑一棵树，显然先选长链总是不亏的，而选完长链后，再选与之前选过的链上的支链，产生的贡献应该是除去原本选过部分的。

如果这里直接写的话，显然是树链剖分的题，think twice

于是可以维护每一个点到最远的叶子的最长距离 $f_u$，而搜索 $u$ 子树时候其他的所有新链，可以简单的维护成增量，存储到一个地方，最后别忘了传入 $f_0$。

排序直接贪心的从大到小选即可

这里要注意，搜完 $u$ 的时候，为什么不传入 $f_u$，因为此时 $f_u$ 是还具有传递性的，因为他的父亲节点还要继续使用其向上传递，此时不能结算，不然会算重贡献。

namespace XK {

  void solve() {
  	ll N; rd(N);
  	V<V<pair<int, int>>> e(N);
  	rep(i, N - 1) {
  		int u, v, w; rd(u, v, w); -- u, -- v;
  		e[u].pb({v, w});
  		e[v].pb({u, w});
  	}

  	V<int> ord, fa(N, -1);
  	auto dfs = [&](this auto dfs, int u, int pa) -> void {
  		fa[u] = pa;
  		ord.pb(u);
  		for(auto [v, w] : e[u]) if(v != pa) {
  			dfs(v, u);
  		}
  	};
  	dfs(0, -1);
  	
  	V<int> cst, f(N);
  	rrep(i, 0, N) {
  		int u = ord[i];
  		ll now = 0;
  		for(auto [v, w] : e[u]) if(v != fa[u]) {
  			ll x = f[v] + w;
  			if(x > now) swap(x, now);
  			if(x > 0) cst.pb(x);
  		}
  		f[u] = now;
  	}
  	cst.pb(f[0]);

  	sort(all(cst)); reverse(all(cst));

  	ll ans = 0;
  	rep(i, N) {
  		if(i < sz(cst)) ans += cst[i];
  		wt(ans * 2);
  	}

  }
};

AGC058 B - Adjacent Chmax 黄

https://atcoder.jp/contests/agc058/tasks/agc058_b

考虑每个点的管辖范围，也就是笛卡尔树

但是这题不需要显式表示

考虑每个点的区间 $[L_i, R_i)$，你可以变或不变，不变就是继承之前的选法，变就是之前的选法在新选法上累加，也就是 $f_{i,j} = \sum_{j\gt k\ge L_i}f_{i-1,k}$

为什么是累加的呢，因为 当你 枚举 $j$ 的时候，其之前的 满足 $L_i \le k \lt j$ 的位置，都可以作为转移到当前边界的次数，这里不区分边界是因为，无论是左右边界，本质都是边界，不影响后续的点选择，因为点权值满足排列。

  void solve() {
  	ll N; rd(N);
  	V<ll> A(N); rd(A); rep(i, N) -- A[i];
  	V<ll> L(N), R(N);
  	rep(i, N) {
  		L[i] = i, R[i] = i + 1;
  	}
  	// cerr << "?" << endl;
  	rep(i, N) {
  		int j = i;
  		while(j > 0 && A[i] > A[j - 1]) L[i] --, j --;
  		j = i + 1;
  		while(j < N && A[i] > A[j]) R[i] ++, j ++;
  	}

#ifdef DEBUG 
  	rep(i, N) {
  		wt(i,":","[",L[i],":",R[i],"]");
  	}	
#endif

  	V<mm> f(N + 1, 0);
  	f[0] = 1;
  	rep(i, N) {
  		V<mm> nf = f;
  		mm n = 0;
  		Rep(j, L[i], R[i]) {
  			n += f[j];
  			nf[j + 1] += n;
  		}
  		f.swap(nf);
  	}
  	wt(f[N].x);
  }

EDPC **M - Candies ** （个人预估：青色）

https://atcoder.jp/contests/dp/tasks/dp_m

显然设计有 $f_{i,j} :=$ 第 $i$ 个点，一共选了 $j$ 蜡烛的方案数.

显然是 $f_{i,j} := \sum_{0\le x \le a_i} f_{i-1,j - x}$，对于 $x\in [0, a_i]$，那这里

其实就是背包转移 套一个 前缀和

  void solve() {
  	ll N, K; rd(N, K);
  	V<mm> f(K + 1, 0);
  	f[0] = 1;
  	rep(_, N) {
  		ll A; rd(A);
  		V<mm> pre(K + 2, 0); pre[0] = 0;
  		rep(i, K + 1) pre[i + 1] = pre[i] + f[i];
  		V<mm> nf(K + 1);
  		rep(i, K + 1) {
  			nf[i] = pre[i + 1];
  			if(i - A >= 0) nf[i] -= pre[i - A]; 
  		}
  		f.swap(nf);
  	}
  	wt(f[K].x);
  }

ABC253 G - Swap Many Times （黄色偏弱，个人预估：蓝色偏弱）

https://atcoder.jp/contests/abc253/tasks/abc253_g

好纯粹的打表题

注意到如果一个连续操作

$(1,2) ... (1, N)$ 的话，实际上等价于变成 $\set{N,1,2,\ldots,N-1}$

所以只要看两边不完整的操作，中间全部按照这个等价操作简化即可，复杂度是 $O(N)$ 的

当然这个连续操作你很容易就能通过打表看出来。