2026 寒假集训总结

2026-1-31

寒假集训第一天，学习网络流及它的拓展（比如上下界）。

大部分能够听懂，做了其中的 \(7\) 道题目，不过效率可以再加快一点，因为这一天要做的题确实很多。

另外 EK 和 Dinic 算法还需要进一步掌握，模板不能独立打出来，要再打熟练一点。

教辅的组成

网络流的建模。不难发现就是三分图最大匹配。但我们可以用网络流来做，把练习册和源点连接，答案和汇点连接，直接跑最大流。？怎么 WA 了？

因为我们发现书最多也只能有一本，所以要把每本书拆成两个点来看待，第一个点连接练习册，第二个点连接答案，两个点中间也连接一条边，并且所有边的容量均为 \(1\)。这样就可以跑最大流了。

Fotile 模拟赛 L

虽然这不是网络流的题，但是也是今天做的紫题。即使很水

设 \(dp_{i,j}\) 为区间 \([i,j]\) 的答案。不难发现要么这个答案要么从 \(dp_{i+1,j}\) 得到，要么从 \(dp_{i,j-1}\) 得到，要么直接全部选择（用前缀和来记录答案）。询问时直接输出 \(dp_{l,r}\) 即可。负责度 \(\mathcal{O}(n^2)\)。

狼和羊的故事

把每个格子看成一个点。考虑将狼和源点连接，羊和汇点连接，相邻的两个格子进行连接，那么答案就是这张图的最小割。又最小割等于最大流，所以直接求这张图的最大流即可。

2026-2-1

学习分块与莫队的进阶。

众所周知分块和莫队是比较容易的东西，但进阶莫队就不容易了，全是紫题

不过这些紫题都是蓝题的模板+黄绿题的思维难度，整体是很好做的。

还学习了回滚莫队、树上莫队的模板。