今天依然是上午考 DP，三个小时四道题。
我觉得今天的题目较昨天更简单。考场上就想出了四个题，但是我以为 T1 \(O(n^3)\) 的做法是暴力，想了好久 T1 也没想出更好的做法，于是开写，然后造数据测了测，发现跑得比较快（极限数据应该也是能在我的位置上那台电脑里 1s 内过的）。
结果出分是 330，前三题都 100，T4 我的 map 做法有点傻，空间很大，加上写得劣导致时空消耗大，我被卡到了 30 分。
把在 map 里重复访问的东西丢到同一个变量里，又交了一遍，就有 90 分了。最后一个点空间炸了。
把有一个地方访问的时候改成了 .count() 防止多开空间，结果最后一个点没有炸空间了，变成 TLE 了。（好像是这样的）
都准备写 FHQ-Treap 了，结果把 map 改成 unordered_map 就过了。
下午讲评没多少内容。开始讲的时候大家貌似都改了好多题了。
T1
出题人非常善良地给了图，可以参考图来思考。
容易发现如果环上的两个人碰杯了，那么他们把这个环分成两个部分，这两个部分之间的人互相不能碰杯。
考虑逆时针（顺时针也可，但题目是按逆时针给的）地把每个人的酒写成一个序列，暂时不考虑破环为链。发现上面的限制相当于一个区间，区间内的和区间外的人互相不能碰杯。
发现相当于每两个人形成了一个区间，要选择一些区间，使得它们要么为包含关系，要么不相交。
感觉很像要区间 DP。不用破环为链。
注意到区间 DP 里合法的区间（这里的区间和前面提到的“每两个人形成了一个区间”那个区间不是一个东西）长度必须是偶数。所以区间 DP 的最外层和最内层循环都[要]（还是“可以”？）每次 + 2。而且区间 DP 的三重循环枚举到的东西实际上比 \(n ^ 3\) 个少。因此虽然是 \(O(n ^ 3)\)，但跑得比较快，[能 \(1 s\) 过 \(n = 1000\) 的数据]（？）。
T2
考虑三份权值和相等就是要让三份的权值和都等于总权值和的 1/3（后面我把它成为 sum / 3）。
我的做法（听说题解也是这个）：
考虑切第一刀的时候，分两种情况：
- 子树权值和为 sum / 3，其他部分为 sum / 3 * 2。此时要在其他部分再切一刀，切下一个权值和为 sum / 3 的子树。
- 子树权值和为 sum / 3 * 2，其他部分为 sum / 3。此时要在这棵子树里再切一刀，切下一个权值和为 sum / 3 的子树。
树形 DP 一下就差不多了。第一种情况考虑枚举两个切下的子树的根的 LCA，看这个 LCA 的不同子树。第二种情况我是反过来处理的（先找那个 sum / 3 的，再在它的祖先里找 sum / 3 * 2 的）。注意写法和细节，可以见我代码。
lr 的做法（感觉更简洁，但是正确性感觉有点怪，但是用上面的做法来说明好像很对）：
遇到 sum / 3 的子树就直接把它删掉。
T3
KMP + [线性 DP]（？）板子，比较简单，个人认为是这场最简单的一道。
T4
模仿 LIS 的 DP 做法。设 \(f _ { i, j }\) 表示最后一个位置是 \(i\)，倒数第二个位置是 \(j\) 的最长[斐波那契子序列]（？）的长度。
转移：
\[f _ { i, j } = \max \{ f _ { j, k } \} + 1 \ ( c _ k + c _ j = c _ i ) \]要特殊处理子序列长度为 1 和 2 的情况。
直接枚举 \(k\) 不行，由 \(c _ k + c _ j = c _ i\) 得 \(c _ k = c _ i - c _ j\)。于是对每个 \(i\)，把 \(c _ j\) 相同的 \(f _ { i, j }\) 丢到一个桶里取一下 max 即可优化转移。
但是值域太大，于是用 map 之类的。
但是我好傻，没想到用 map 来做离散化。用 map 离散化的话 map 里只有 \(n\) 这个级别个数的数。而像我对每个 \(i\) 都开个 map，一共存了 \(n ^ 2\) 级别个数。这导致了空间和时间上都消耗较多。
%%% yt 第一个过 T4，并给我[们]（？忘了）讲了 map 离散化的做法。
-
今天胡老师还给我们讲了怎么算空间。
-
另外还有一些同学出错的点。还有我 map 做法挂成 30 分的各种问题。
-
我考场上在草稿本上写了个检查的流程。
上面三条来不及整理了，去睡觉了qwq。
2024.8.31
标签：map,子树,2024.8,31,权值,区间,sum,DP From： https://www.cnblogs.com/huangkxQwQ/p/18390896