2015 Multi-University Training Contest 2总结

第二场多校题目比较难想,我们场上只过了1002和1006两道水题,第九题由于没有考虑分数,所以5的方案没有构造出来。第一题本来以为可做,但是后来发现少看了一个条件。第四题想了一个非常复杂的贪心,虽然挖掘了一些性质但是最关键的仅会走一整圈这个性质没有考虑到。其他几题都没有读题。

1001. Angry Trees


so hard

1002. Buildings


模拟

题目大意:给出n×m的方格,其中有一个格子是坏的,将其余的格子分成a×b的小矩形,并使每一个小矩形都有一个边位于整个n×m的矩形的边缘。问面积最大的矩形最小是多少。

为了使矩形的面积尽量小,我们一定会将大矩形分为1 × n的小矩形。

如果不考虑坏点,那么我们仅需要考虑位于中间的点向四周延伸至边缘最短为多少,其他矩形都不会超过这个面积。

如果有坏点,他会挡住一些点,使得这些点仅能从一边延伸至边缘,被影响的点共有4个,即位于该点上下左右的四个。我们就考虑这四个点中最小值最大的和中间点可延伸的最小值取一个较大的即可。

1003. Connect the Graph


构造

题目大意:一个图中有黑白两种边,其中每个点的黑边的度和白边的度都仅可能为0,1,2,并且图中没有自环和重边(连接相同两点的不同颜色的边也算重边),给出图中白点度为0、1、2的点分别有多少个以及黑点度为0、1、2的点分别有多少个,求出图的一种构造方案。

如果度为1的点有奇数个,那么显然无解。

如果两种边的和超过了完全图的边数,那么也无解。

除此之外,注意到每种点都大于等于1个,那么就可以仅通过构造许多链来解决这个问题。

对于其中一种颜色的边,可以将1, 2, 3, 4, 5, …, n连成几条链,另一种颜色的边,则将 1, 3, 5, 7, …, n - 1, 2, 4, 6, …, n连成几条链,这样可以保证不会有重边。

1004. Delicious Apples


dp

题目大意:在一个环上有n个苹果树,每个苹果树上有ai个苹果,每个点到起始点的顺时针距离已知,现在有容量为k的篮子,问通过这个篮子将所有苹果送至起始点所要走的最短距离是多少。

我们刚开始看这道题时,想出了一种非常复杂的贪心策略,后来发现需要讨论的情况太多,就没有继续想。

其实,这道题有一个非常重要的结论就是:绕过整个圈来取苹果的情况仅会出现一次。因为如果我绕了两圈,那么我可以从这个圆的中点将路径断开,分别从两边将苹果取回来(两边苹果数量相等),或绕第一圈时将一边的苹果取完,第二次仅需要走不到半圈并原路返回将剩下的苹果取完(两边苹果数不等)。这样会比绕两圈来取苹果更优。

有了这个结论,我们就想到枚举哪几个苹果是在绕一圈的时候取的,那么剩下的苹果都可以仅在半圈里考虑,就可以通过简单的贪心或dp来解决了。

而且绕一圈一定是取的连续的k个,所以我们就枚举这个区间的位置,剩余部分就随便做了。

1005. Eastest Magical Day Seep Group’s Summer


状压dp + 生成树计数

题目大意:给出n个点,m条边的联通图(n <= 16),从中去掉m - n条边,使得剩余的仍是一个连通图,问有几种删边方案。

如果是删掉m - n + 1条边,就变成了求一个图的生成树个数了,多了一条边就相当于是在生成树的基础上加了一条边,变成了一个基环外向树。由于n非常小,我们可以暴力枚举是由那几个点构成的环,这样将环缩点就变成了经典的生成树个数的问题了,通过Kirchhoff矩阵即可求出。

Matrix-Tree定理:

1、G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时,dij=0;当i=j时,dij等于vi的度数。

2、G的邻接矩阵A[G]也是一个n*n的矩阵, 并且满足:如果vi、vj之间有边直接相连,则aij=1,否则为0。

我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G],则Matrix-Tree定理可以描述为:G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。

这样还有一个问题就是这几个点组成的环究竟有多少种情况,这可以通过类似求哈密顿回路的状压dp求出方案数。

1006. Friends


暴力

题目大意:有n个点,m条边的图(n <= 8),现在将边分为两种,要求每个人连的两种边的条数相同,问有几种分边方案。

8个点,最多28条边.如果挑一个点和它相关的边不管,剩下的边都枚举,那么就是21条边.可以直接状态枚举21条边的情况.但是有100组数据. 发现每一个点度数一定是偶数,那么这满足偶数的图,除去一个点之后的边数一定小于21,因为一个点不能向外连7个边,只能连6条. 所以暴力加度数提前判断就好了.

重点:

首先去掉一个点枚举边.然后发现度数是偶数才能对.可以减少情况.

1007. Gorgeous Sequence


神奇的数据结构题。

题目大意:一个长为n的数列,有以下三种操作

  1. 将一个区间的数变为它本身和x的最小值
  2. 询问一个区间的最大值
  3. 询问一个区间的sum

不看第一的操作的话就是一颗水水的线段树,操作一会使得该区间的最大值变为x,并且若是需要被修改的区间被一个已经被修改的区间覆盖并且大区间的标记值小于此次修改的值,那么此次修改是不必要的。于是我们得到,大区间的标记值大于子区间的标记值。

1
2
3
4
5
6
struct T
{
int Maxtag,Max,Tag,s,cover;
int Tagtag;
ll sum;
};

在对大区间进行标记的时候,需要对所有子区间标记值大于该标记的部分进行清空。我们维护一个区间标记的最大值,那么当修改值大于这个最大值就不修改返回。这个清空的操作看似会超时。研究题解和标程,我的想法是,因为每一次清空的tag都需要一次附上tag,将一次打tag和删除tag看作一组操作的话,均摊复杂度是logn的。(待考证,题解的没看怎么懂)

计算sum值,需要维护一个cover,表示该节点的除该节点的tag外被控制的节点数,即sum值包含的节点数,这些节点由子树的tag控制,那么属于该树的tag值控制的即为此节点的size-cover,这些值都是tag的值。(好虐)

1008. He is Flying


FFT

题目大意:1≤n≤100000 n个区间,每个区间有一个长度.,也可以看做权值. n个区间是按照实际的顺序给的. 现在一个人,要连续的跑这些区间,跑j-i+1个区间的话,会获得j-i+1的hp值,这个区间长度为s[i]+到+s[j]. 限定给出的所有的s的和0≤s≤50000. 问跑长度为0的段段的所有可能情况的hp值的和,长度为1的…长度为s的 都要输出. 注意s[i]可能为0.

1e5的区间数不能枚举左右端点.我们发现有连续这个要求,因此想到分治.

法一:分治.

左边递归,右边递归. 只剩跨过中间的值. 我们向左统计区间长度是i的种类数,放在numl中,向右统计长度是i的种类数,放在numr中.现在要算出所有的区间长度的每一个区间长度的hp和. 是经典的加扩展的fft算. 左边l,右边r.要算l+r的情况数.

但是本题不是情况数,而是有hp值的加权. 其实是一个经典的问题.我们再处理左边的长度是i的总的hp值放在hpl中,那么这些值对答案的贡献要乘上他们的情况数. 其实就是hpl和numr做fft. 同理 hpr和numl做fft. 这样就算出来了.

但是分治有两个重点:

(1)不是找中点,因为fft的复杂度和他们的最大值s的和值有关,所以找尽量均分s的点作为分治点.

(2)如果s均是0,那么我们每次只会去掉一个.这样是不好的.这样的情况特判或者取中点就好了.

法二:写出来母函数, 之后用fft算.

母函数把hp值看作两次求. 先定为 i到j的hp值为j. 这样写出母函数. 然后再减去母函数 i到jhp值为i-1. 这样就弄好了hp值(因为每种情况的个数两次算法都一样).

重点:

法一:

  1. 连续的区间想分治.
  2. 经典的fft拓展算权值.
  3. 分治不看mid,根据fft划分.
  4. 分析出000的情况.特判

法二:

  1. 母函数写带权值只能带一个数,将hp值重新定义

1009. I Wanna Become A 24-Point Master


构造

题目大意:给出n,问由n个n通过四则运算能否凑出24, 每个数只能用一次

场上这道题坑了两个多小时最终也没调出来。主要是没有考虑会出现分数的情况。

对于n = 1、2、3,很容易证明这是无解的。

对于n = 4, 样例给出了一组解。

对于n >= 12, 由于5个数能凑出4((i + i + i + i)/i = 4), 四个数能凑出3((i + i + i) / i = 3), 三个数能凑出2((i + i) / i)。因此12个数就可凑出24,如果有再多的数就可通过+ (i - i) * i ^ (n - 14) 这样的操作来保证结果为24。

那么仅需要将小于12的情况构造出来(上述构造方法还不能解决13,也需要单独构造)

比较坑的就是5的构造方法:(5 - 5 / 5 / 5) × 5

1010. JRY is Fighting


二分+dp乱搞

题目大意:一开始有一个初始的生命值m,之后每一秒都会掉a[i] 的血,另外有一个血瓶,在打完每只怪物后都会增加k的血量,在这之后你可以选择喝掉所有的血并且回复相同数值的生命值(可以超过原生命值),现在要在尽量不死的基础上使得没最短的相邻两次嗑药的时间差尽可能的大。

首先我们可以得到这么一个性质:我们在第i秒喝了药,那么第i秒得到的血量不受之前喝药情况的影响。

所以在打第I 只怪物前,我们承受了sigma(a[i])的伤害,不吃药的话生命值为m减去上述的值。若为负值表明我们在打怪之前必须要吃药。并且我们最晚一次吃药的数值要使得血量为正数,即f = sigma(a[i])- m + 1, f/k向上取证的值为l,区间[l,i-1]极为打第I只怪之前必须吃药的区间(当然要合法)。

接下来我们要去掉包含的区间,排好区间的序,倒序扫一遍,维护现有区间的最小值,即可去包含区间(保留小区间)。

二分答案最小距离是x,定义dp[i] 为在i点嗑药是否合法,倒着回推,那么i点合法的条件是[i+x,右边紧邻区间的右端点]内有合法的点,O(n)可以实现。