月度归档:2016年11月

蒟蒻的Codeforces Round #316 (Div. 2)补题记

中午打了这场vp,有点惨啊。。。E有思路没写完,还是太弱了。

A. Elections(模拟)

A题看错题意,没处理好一人都没的票的情况。。。WA了四次,还有一次过了47个点。。。虽说9min就过了C,但是还是直接崩了。

B. Simple Game(博弈论)

简单题博弈,分奇偶情况讨论一下。

C. Replacement(乱搞,讨论)

我是乱搞,就是维护出来一开始有多少个相邻的’.’,然后每次改变分情况讨论。

D. Tree Requests(dfs序+二分)

这道题比赛的时候想了个记录每一层字母的思路,没想清楚。后来看看题解,发现方法主要有离线和在线的做法。在线的做法和我的很像,在这里就写一下在线做法,但是在线做法因为用了STL有可能被卡时间空间也是很悬。。。

维护dfs序出来,同时存下来每层深度下每个字符的属于的节点的dfs序。然后我们就可以二分找到某个节点子树的某一层的那些字符的个数。回文串必然要求为奇数的字符不大于等于2.所以就可以在线算出来了。

E. Pig and Palindromes(dp)

E差一点就写完了,就是最后的讨论没写清楚,没出样例于是GG。

首先我们可以从左上角(1,1)和右下角(n,m)同时分别向中间走。那么设dp[i][j][k],表示两个方向现在都走了i步,左上角走到了第i行,右下角走到了第j行。然后我们可以计算出这两个点的现在坐标,然后转移就可以了。

但是麻烦的地方在于最后中间那部分的讨论。如果走的是偶数的回文串(n+m%2==1),那么这两个点的最后坐标并不是在一起的,有两种情况:j>k和j=k的情况。走的是奇数的话,只有j=k的情况。

总结:这次换了打法,先做了C还比较顺利,但是A,B的崩盘我觉得还是自己的读题有问题吧。E题最后时刻没写出来,对于我来说也不是第一次,四省赛不就是这样吗,这种细节的题目,没有压力的时候还好脑子不乱,但是最后关头很难理清楚了。。。D题没想到dfs序,实在是太傻比了。以后争取每周打两场cf的vp。。。

蒟蒻的Codeforces Round #379 (Div. 2)颓废记

vp了一场,中间被队友叫去填表格耽误了一些时间,E没时间想了,后来看看题解自己推了推感觉还有可能拯救一下?

A. Anton and Danik(模拟)

B. Anton and Digits(模拟)

C. Anton and Making Potions(二分+贪心)

看了半天的题面才明白在说啥。。。枚举第一种操作的选择(可能不需要第一种操作,所以加一个花费为0的来代替),同时因为第二种操作,可以把一些药水直接做好,而且相关的c,d数组都是非递减的。我们肯定贪心的选择转换最多的且满足花费限制的。这个可以二分找到,因为满足限制的花费最多的操作肯定满足转换的最多。

D. Anton and Chess(模拟)

忘记开long long wa了一次。因为棋子是无法跳过障碍的格子攻击国王的。所以我们就维护国王八个方向离它最近的棋子的相关属性。最后check一下就好了。

E. Anton and Tree(缩点+树的直径)

首先缩点后,我们可以得到一棵黑白相间的树(黑色节点相连的一定是白色节点,白色同理)。然后我们求出树的直径dis,然后取直径中点的染色(dis+1)/2即可。我们可以这样想,如果直径上的节点数是奇数,那么你每次染色,可以让直径上的有两个点变的同色。如果偶数的话,最后一次只让一个节点变得同色,但还是那个公式。。。而又因为是直径,所以直径上挂的枝叶也会跟着变的同色,而且不会超过直径的染色次数,否则就不是直径了。觉得抽象,画个图模拟一下就好了。

我是用并查集缩点,然后两次dfs求直径。。写的有点丑。复杂度是O(n),但可能常数较大。。。

F. Anton and School(数学)

F题考察出了我上学期数字逻辑没怎么学好(废话只考了75) ,clearY一眼秒了。我还是看了题解才发现这个性质: .感觉就是个加法器的实现啊。

然后设,那么.我们把所有的求和得到:

那么,那么每一个都可以算出来了。现在我们只需要检验我们计算出的是否合法即可,其实我们不需要n^2检验,而是可以直接按位检验。因为如果当前数,那么在二进制下的为1的位置一定是中为1的位置。至于这个位置上有几个1我们可以预处理出来。的处理同理。那么这样的话复杂度O(nlog(1e9))。

总结:A,B煞笔题,C题一开始想错了一个贪心的地方,好在后来想明白了。D题因为C题一直WA有点慌了,细节没处理好(比如long long)。E题在补的时候也有一点问题,就是重新建图的时候一开始连边错了,居然还过了样例。F题其实如果长成这样大家都可以看出来了吧:.

hdu 3507 Print Article(斜率优化dp)

Problem Description
Zero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost

M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

 

Input
There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

 

Output
A single number, meaning the mininum cost to print the article.

 

Sample Input
5 5
5
9
5
7
5

 

Sample Output
230
题意:一个长度为n的序列,让你划分成任意数目的连续段。每一段连续段的代价是.求这n个数的序列的最小价值。
斜率优化的入门题,但是也推了好久。
首先一个很明显的dp递推式:
,sum数组是前缀和。
但是这个是O(n^2),TLE。所以接着挖掘性质。
假设,假设选择j比k优。
那么就得到这样一个式子:
左右移项合并同类项后就是这个样子了:
因为,所以.我们把,视为,视为,依次类推。
那么上面的式子就变成了:,这就相当于k点到j点的斜率嘛。设k到j的斜率为
那么上面最终的式子是长这样的:,也就是如果两个决策点间的斜率满足这样的关系的话,我们就可以舍弃k点。
现在假设,如果,若,那么b比c优,a比b优。所以b可以被舍弃。如果,那么c比b优。所以只要有这样的斜率关系,b肯定可以被舍弃。那这样的我们维护的一个图形画出来就是一个下凸包。
然后用单调队列维护他就可以了,注意这是在x单调,y单调的情况下,才可以用单调队列维护。还需要注意的是为了表示可以从什么都不选的情况递推过来,需要在单调队列加入一个0节点。因为这个WA了无数发。