2023.8.11 nfls集训Day3 考试总结

2023暑nfls

前言：被 F 搞吐了！为啥又只做了 G, F 啊！

result

Progress

开题。

$F$：内向基环树森林，感觉很可做
$G$：相当于多条欧拉路径求并，记得是很经典的 trick，有点小忘了
$H$：带问号的字符串题，看起来不是很好做

开场搞 $G$，先不管那个 trick，胡了个看起来很对的配对，写了写，有分但过不了。

感觉自己没写错，冷静了一下，捏了个数据把配对 hack 了，小寄。

开始回忆一下那个 trick，想了一会想通了，改一改很快就过了，拿下 $G$ 的首杀。

到此一切顺利，感觉很有希望冲三题。

开 $F$，树上拓扑推一下，环上是不是贪心找最小的断环就好了。

稍微玩一下数据，感觉很对，开冲。

然后就开始挂，调，挂，调……直到做了 1.5h $F$ 了，还没过，感觉是不是贪心假了。

想了一下，换成 DP 算也很好算，果断改做法，又写写调调，在最后 $20$ min 时过了。

最后看眼 $H$，感觉很 2-SAT，然后拍到 Trie 树上搞，是不是随便搞一搞就搞完了，不管了反正没时间写了。

讲题，这个 $H$ 建图好像很难的啊，感觉晕晕的，不是很好搞，那也没有那么遗憾了。

$F$ 最简单的做法就是贪心啊！为啥没写对呢，而且为啥 std 这么短啊！！！！

发现自己的内向基环树实现极其拙劣，吐了，又臭又长。

不过回头再看，今天两道题都被 “猜结论” 猜错（虽然 $F$ 好像没错）搞到了。

实际上稍微花时间想想就能得到更有确定性的做法。

猜结论还是应该在思路难以进行的时候做。

F 还钱

写一下 DP 做法。

树上拓扑一下，就只剩环了。

环上的话，如果有点钱够了，就自然的断环了，变回树上的做法。

如果没有的话，把环倍长成链，差分一下，记个前缀和，很容易 $O(1)$ 算出断环后的结果，就可以 DP 了

实际上好像直接贪心也可以。

记一下内向基环树森林的比较好的实现方法

我一直是先找环再拓扑，很丑，实际上直接做拓扑就可以天然的把树干掉，把环找出来

看起来只省了个 dfs，实际上好写很多。

G Miner

套路题。

相当于求多条欧拉路径的并，多条欧拉路径可以考虑转成欧拉回路处理。

具体的，建立一个虚点，向所有奇数度数点连边。

这样就可以跑欧拉回路，构造方案上，如果是从虚点走出去的边，就是 $1$ 边，否则是 $0$ 边。

可以参考 Link 里的 CF1610F

H-Pre P6378 [PA2010] Riddle

传送门

H 涉及到一个不会的东西，前缀优化 2-SAT 建图。

感觉这东西只能用来建 2-SAT ？主要是用到了只有 $0,1$ 两状态的性质。

不是很清楚，但是感觉很聪明。

回到此题，对每个点是否为关键点做 2-SAT，图上边的要求直接建边就好了。

但是每个部分 恰好一个关键点的要求 的建边数量是 $n^2$ 的。

我们需要优化建图，把这个限制换个说法。

对于 $\forall i,j$ 有 $Bool[i][1], Bool[j][1]$ 矛盾。

那这个其实可以写成，对于 $\forall Bool[i][1]$ 与 $Bool[j][0] | j \in [1,i - 1]$ 连边。

可以发现这是个 前缀连边 的形式，可以用一个技巧叫前缀优化建图。

先放个图，它长这样：

具体的，圆点代表单个的点，方点则代表 一段前缀是否有取到 $Bool[j][1]$ 的值

在图上模拟一下很容易知道正确性，这样连边数被优化成 $O(n)$ 。

PS：

线段树优化建图的本质是将一个区间拆成 $O(\log n)$ 个区间。

那前缀优化建图的本质是什么？

以暂时的理解，实际上是利用了前缀之间的变化量是极小的（只有一个新加的点）

而 2-SAT 是个 0/1 状态，所以前缀可以通过或操作，被压缩成一个 “前缀或” 的数？

或许是这样。

H 编码

$H$ 可以看做上题的 树上版本。

由于一个串只有一个 $?$，可以将一个串拆成两个。

暴力判断前缀，连边是 $n^2$ 的，但我们发现此题并不具备线性结构，此时并不能前缀优化建图。

串串的前缀问题，很容易想到把串全拍到 Trie 树上。

那就变成了对于一个串，往祖先上的串连边，暴力仍然是 $n^2$ 的。

但我们发现，此时单独考虑每个串，其要连边的点组成了一个线性结构，那就又变成了一个往所有 “前缀” 连边（这里的前缀实际上是祖先）。

考虑把之前的链上前缀优化拓展到树上。

长这样：

由于一个点可能挂多个串，我们可以在 Trie 树上插串时，最后都多建一个方点对应本串。

这样记得要按长度排序插入，一样的方式建图即可，边数为 $O(n)$

实在是很好的题。