2025.9.1

· · 个人记录

T1

一眼 dp，f_{i,0/1} 表示到第 i 个点，第 i 个点选/不选环上,转移是容易的。

赛后咋挂成 9 了，完了。原来是第一遍 dp 应该不选，写成选了。该罚。

T2

一开始想的是线段树上维护每一块肉，然后选，发现不太好做。

想离线，找每块肉被那个人选走，发现直接把每个线段搞到端点上，维护下区间最小值，表示被那个人选走，直接就做完了。然后就做完了。

T3

一眼会了 O(n^3)。然后想考虑每次插入算贡献，但是不会做。想了大约 1h，果断写暴力。

正解是要注意到选的点一定是连续的单调字段的端点，然后就可以算贡献了。

T4

正解要注意到有一些点是必须选的，然后处理一下就行。 ### T5 会了暴力和字符集只有 {a,b}，然后注意到为了连续一定要是形如一段 a，一段 b，一段 c... 然后又不会了。 正解是先把所有的退成 a 然后每次将一个后缀变大，然后有线段树维护一下贡献就行了。