Codeforce 水题报告(2)

2015年6月10日3410

又水了一发Codeforce ,这次继续发发题解顺便给自己PKUSC攒攒人品吧

CodeForces 438C:The Child and Polygon:

描述:给出一个多边形,求三角剖分的方案数(n<=200)。

首先很明显可能是区间dp,我们可以记f[i][j]为从i到j的这个多边形的三角剖分数,那么f[i][j]=f[i][k]f[j][k](i,j,k是否为1个合格的三角形)

Code:

CodeForces 438D:The Child and Sequence

描述:给一个序列,要求支持区间取模,区间求和,单点修改(n<=10^5)

考虑如何用线段树来搞这个东西,很明显对于所有区间取模操作都必须用搞到点,但是如果我们加入一个小优化(只有区间序列的最大值大于那个区间的话,才往下传递)然后我们就可以解决这个问题啦。

为啥?我们可以发现当一个数取模的时候至少变小一半,因此每个数最多取模log a[i]次,所以总的时间复杂度为$n log^2 n$

Code:

CodeForces 434D:Nanami’s Power Plant

描述:有n个节点,每个节点可以取一个xi(li<=xi<=ri)xi为整数,然后对于每个节点的权值为aix^2+bix同时需要满足某些xu-xv<=w的限制

既然是整数那么我们就可以直接用网络流啦,对每个节点的每个取值拆下,然后连边权为权值的边,然后就是最小割啦。接下来再考虑那些限制的条件,我们可以对所有相邻的东西可以直接连一个x[u]->x[v]+w,流量为inf的边,就可以限制到啦

Code:

CodeForces 543C:Remembering Strings

描述:给定一堆字符串,改变某个字符需要一定的花费,求使所有的字符串都是好记的(存在一位的字符是该位中的唯一一个)(n<=20,len<=20)

很神奇的一道题,考虑用数位dp来解决这道题。我们考虑如何使一个字符串变成好记的,很简单只要改变某一位的字符即可,或者需要把这种字符都改变的话,那么花费是sum-mx(除了花费最大的不变,其他都需要改变)然后就行啦

实现的话用了一直比较鬼畜的写法,结果意外的短,详情可以看代码

Code:

CodeForces 543D:Road Improvement

已知有一颗树,对所有点求删去某些边,使得其他点到该点至多经过一条坏边的方案数(n<=2*10^5)

很明显是树形dp,那么f[x]=pai(f[ch[x]]+1)

考虑怎么从祖先的答案算出自己的答案,很明显吧自己除去就能把祖先当自己的子树干了

除的时候不能直接用乘法逆元(f[x]可能为0 ), 需要存一个前缀和还有后缀和

Code:

CodeForces 546E:Soldier and Traveling

描述:有n个城市和m条道路,每个城市有一定的士兵,士兵可以移动到相邻的城市,求是否存在一种移动方式使得每个城市的驻兵数为某个值(n<=100,m<=200)

很明显是网络流吧,拆点然后随便搞搞即可

Code:

CodeForces 534D:Handshakes

描述:有个房子,有n个人按顺序进去,一个人进去就会跟房间中空闲的人握手,每3个人可以组队做事,给定握手数,求方案

我们从0开始,每次看+1的有没有人,没有就-3,完了

Code:

CodeForces 545E:Paths and Trees

给定一个图,求权值和最小的最短路树

那么最短路图建好,模拟克鲁斯卡尔算法,拍个序,又由于是个有向树,所以除了点u外都只有一个父亲,维护这个性质即可

CodeForces 542F:Quest

给定若干个节点作为二叉树的儿子节点,每个节点有其深度限制及权值,求构建一颗二叉树,使其权值最大

按深度限制从大到小干,每次把两个最大的合成一个小的即可

Code:

好了就写到这里啦,代码回来再贴。回去收东西啦。

%d 博主赞过: