NOI2015

程序自动分析(并查集)

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)是否等于第一问的最优解,如果等于则表示这一条路需要轧路机。

找到了这些边,然后我们需要求每一条边至少经过一次的最小次数。不难发现这就是一个有源汇有上下界最小流问题,直接做就可以了。

细节比较多,代码比较长,要细心一些~

代码

原文地址:https://www.cnblogs.com/Itst/p/10808633.html