Codeforces Round #407 (Div. 2)做题记录

被学长和myk大爷carry了,但是人太菜,居然还写挂了一个D题。。无语了。。。所以机房开车众都一夜上紫了,而我还是在div2鱼塘里沉迷。。。

A. Anastasia and pebbles

题意:给出n堆不同颜色的石子,k个相同颜色的石子可以放到一个口袋内,但是1天只有两个口袋。需要判断出最少需要多少天把所有石子弄完。n<=10^5

比赛的时候一开始按照2*k分堆了,一直wa,后来就按照k来分堆了。把所有种类的石子都分成k个1堆,如果剩余的话就在弄一堆。

B. Masha and geometric depression

题意:就是给你一个等比的序列,告诉你这个序列中的绝对值不能超过l,而且有若干数是不能选的。问最终这个序列最终有多少个数字。

分类讨论q=0,q=1,q=-1,以及首项小于l的情况,总之情况需要好好判断。。。然后wa惨了,不过还好搞过了。

C. Functions again

题意:给出n个数,组成一个a[i]的序列。定义:,求整个序列的最大的f值。

维护一个数组,它类似于差分数组,只过是在第奇数个差分数组的值前面乘1,在偶数面前乘-1。这是因为f(l,r)中的相邻差分值随着起点的不同而正负改变。假设起点为奇数的位置,那我们就需要在这个新数组内找寻一个区间连续最大值。假设起点为偶数的位置,那么我们就需要在这个新数组内找寻一个区间连续的最小值,最后把这个最小值取负就好啦。取区间连续的最大值可以O(n)扫一遍就好了。

D. Weird journey

题意:图中有n个点,m条边,现在你可以选择两条边只走一遍,其余边走两遍,使得可以一次走完所有的边。每个点存在最多一条的自环。问不同的方案数,不同的方案数定义为选取的只走一遍的边不完全相同。

题目要求一次走过所有的边,而不是所有的点,所以假如图中有孤立点,但是边可以一次走完,仍然是合法的,这里一定要注意。

问题等价于把原图中的边都复制一遍,然后要求选择两条边删去,使得剩余的边们可以形成一个欧拉路(或者欧拉回路)。因为原图中的边都复制了一遍,那么现在的图中每个点的度都是偶数的,那么如果原图是一个联通的,那么新图一定是个欧拉图。考虑自环和非自环的边的情况,假如删掉任意两个自环,那么我可以任意删去两个点的自环(因为一个点的自环最多只有一条)。这样的方案数是,其中C是有自环的点数目。假如删去一个非自环和一个自环的话,那么这样最多也只会改变两个点的度的奇偶性,所以肯定可以满足欧拉路的条件。那么这个方案数是(m-c)*c。也就是从非自环任选一条,自环任选一条。那么考虑删去两个非自环的边,假如删去的边没有公共顶点,那么会让4个点的度都从偶数变成奇数,无解。除非这两条边有一个公共顶点,这样保证只会影响到两个点。所以这部分答案就是

判无解的地方我比赛的时候写错了。。。。so sad。。。但是写挂自己菜,还是当时脑子一热了。。

 

E. The Great Mixing

题意:现在有k个物品ai/1000,可以重复选用物品,要求最后调制出n/1000的物品,求出最少使用多少个。k<=1000000,0<=n<=1000,0<=ai<=1000

比赛的时候只是看了看题,以为是个怎么背包的题目。。。赛后学长说可以bfs。。。去看了一下官方题解,果然可以。。。

首先我们可以把每个物品都减去一个n,这样变成了从任意件物品中可以重复选用凑成0的情况。因为物品实际种数不会超过1001(0-1000),所以我们可以以这些为起点去bfs找到他们能够到达的可行状态,从而找到到0这个点的最短路。注意一个点,就是我们可能会出现先加上一个数x(现在答案大于了n)再减去一个数(现在答案等于了n)。但是如果我们不卡住边界的话,状态就太多了。但是上面说的那个情况如果反过来,先减去再加上就可以了,所以说卡住边界为-1000到1000好了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注