程序自动分析（并查集）
NOI出这种题我还有什么好说的呢……
拆点并查集即可。
软件包管理器（树链剖分、线段树）
一个支持区间赋值和区间和的线段树+树链剖分即可
寿司晚宴（数论、状压DP）
数论题\(n \leq 500\)肯定是什么暴力算法……
注意到每一个数\(> \sqrt{n}\)的因子最多只有一个，这意味着\(> \sqrt{n}\)的因子之间是独立的，而只有\(\leq \sqrt{n}\)的因子之间会相互影响。而\(\leq \sqrt{n}\)的因子只有\(2,3,5,7,11,13,17,19\)总共\(8\)个，所以可以大力状压。
将\(2-n\)之间的所有数质因数分解，记录其中\(<\sqrt{n}\)的因子的出现情况，按照\(> \sqrt{n}\)的因子分类，一组一组地加入并DP。设\(dp_{i,j,k}\)表示第一个人拥有的寿司中\(<\sqrt{n}\)的因子存在情况为\(i\)，第二个人拥有的寿司中\(<\sqrt{n}\)的因子存在情况为\(j\)，当前计算的\(> \sqrt{n}\)的因子的存在情况为\(k\)时的方案数，转移看当前寿司分给第一个人还是第二个人。没有\(> \sqrt{n}\)因子的数先单独做一次。
荷马史诗（Haffman树、贪心）
K进制Haffman树直接贪心。注意需要加入若干个\(0\)使得总元素个数是\(K\)的倍数，否则答案可能不优。
品酒大会（SA、并查集）
跟后缀\(LCP\)长度有关，上\(SA\)。求出\(height\)，考虑如何对于每一个\(r\)的询问快速求出答案。不妨将\(r\)从大到小求解，那么对于某一个后缀\(sa_k\)，满足\(LCP(suffix_{sa_p} , suffix_{sa_k}) \geq r\)的\(p\)一定是一段区间，而且这一段区间随着\(r\)的缩小不断增大。
然后考虑如何拓展区间。考虑对于\(height_k=q\)，当\(r>q\)的时候\(k\)位置两端的区间不会越过\(k-1\)与\(k\)，而当\(r \leq q\)时这两段区间就会合成一段区间。这个显然是可以使用并查集维护的，并且可以比较轻松地在并查集上维护最大价值。
小园丁与老司机（DP、上下界网络流）
第一问不难得到一个DP：设\(f_i\)表示从起点到\(i\)最多能够经过多少棵树。按照\(y\)坐标从小到大DP，对于每一个\(y\)坐标，先考虑它们下面的点的转移，然后再考虑横向的转移。
再考虑第二问。首先我们需要求出可能留下非左右方向车辙印地面。这个可以这样求：设\(g_i\)表示从\(i\)到任意一个终点最多经过多少棵树，转移跟上面的类似，但是这两种转移有一些细微的差别。在DP的过程中，每当找到一条非左右方向的路径\((x,y)\)时，考虑\(f_x + g_y\)是否等于第一问的最优解，如果等于则表示这一条路需要轧路机。
找到了这些边，然后我们需要求每一条边至少经过一次的最小次数。不难发现这就是一个有源汇有上下界最小流问题，直接做就可以了。
细节比较多，代码比较长，要细心一些～