Codeforces Beta Round 13 C Sequence

题目

源地址:

http://codeforces.com/problemset/problem/13/C

理解

给定一个序列,然后对于每一个数,你都可以进行自增或者自减操作。要求求出使得这个序列变为非减序列的最少操作次数。 我一开始的想法比较朴素,我想,只要找到一个比较的标准,比这个标准大我就–,比这个标准小我就++,这样就能得到这个非减序列的最少次操作。然后我就开始寻找这样的标准,后来发现,这是一个不可能的任务。因为给定的序列什么可能都有,我没有办法来衡量每一个数对于整体值的重要程度,然后也没有办法来计算操作的次数。 没有思路之后就开始开脑洞了。很显然,我可以得到这样一个结论,对于一个序列中的某一个数而言,步数最少的,肯定是变成左边或者右边的那个数。如果再考虑到对于整体数列的影响(因为这是一个循环的过程,整个数列都有整体上移或者下移的趋势),这个数可能的取值,肯定是这个数列中已经存在的数。不难猜想,如果这个数变成的最后结果不是这个数列中的数,说明这个解一定不是最优解。(因为要么就多操作了,要么就少操作了。 这么说好像有点难懂,我来举一个栗子吧,就是数列4 1 9。很显然,我们一眼就能看出,最优解的状态应该是4 4 9,也就是这个1恰好变成了4。试想,如果1变成了3,状态变为4 3 9,不合题意;如果1变成了5,状态变为4 5 9,符合题意,但是操作数多了1。那么问题来了,我变成3 3 9,难道不好吗?确实是这样,符合题意,而且结果最优。但是我们可以继续想,3 3 9可以,2 2 9可以吗?再继续,1 1 9可以吗?0 0 9可以吗?然后我们就能看出,位于4 4 91 1 9之间的数列都是可以的,超过了就不行了。这里的4和1,都是原来数列里面的数。我想,这或许并不是能不能问题,而是算法设计方便的问题。如果取原来数列的数,我们直接进行判断即可;如果不是,我们依然是要取原来数列里的数,判断是否在区间内。 根据上面的讨论,我们不妨得出这样的结论:对任何数进行的操作,最后的结果都是把它们变成原数列中的某个数。 解决了理论上的问题之后,下面进入实际的编码过程。直接开二维数组暴力搞的话,这个问题的时间复杂度过高,不可行。所以我们需要对原数组来一次sort,保证b数组是递增的。然后我们可以看到,dp的过程中,只会用到前后两个数,因此我们可以使用滚动数组来降低空间复杂度。这样,这个问题就得到解了。

Read More

Codeforces Beta Round 14 B Young Photographer (Div. 2)

题目

源地址:

http://codeforces.com/problemset/problem/14/B

理解

一个摄影师要拍摄运动员比赛的照片,然后给定摄影师的坐标,以及每一位运动员的活动范围。要求计算出摄影是需要活动的最小步数。 首先我们需要对输入的数据进行一次处理,也就是必须保证左端比右段小。处理完毕之后,两端分别进行sort,这样就得到了运动员活动范围的起点和终点的有序列。显然,只有当最大的起点比最小的终点还小的时候,摄影师才有可能同时看到。然后,如果当前摄影师的坐标比最大的起点小,他只要移动到最大起点即可;如果当前摄影师的坐标比最小的终点大,他就需要移动到最小终点。 这样,我们就得到了摄影师需要移动的距离。

Read More

Codeforces Beta Round 12 C Fruits (Div.2 Only)

题目

源地址:

http://codeforces.com/contest/12/problem/C

理解

题意并不复杂:给定一些标价牌,然后再给定一些水果的名字,每种水果对应一个标价牌。要求输出水果总价的最大值和最小值。 第一眼感觉很简单,贪心乱搞。标价牌排序之后,如果求最小值就从前往后选;如果求最大值,就从后往前选。这个思路没有太大的问题,然后问题来了,我怎么样才能够得到一个去除重复项,并且能计算出每种水果数量的数据结构呢? 然后我就开始SB了,因为循环的时候字符串写得搓,debug半天,都不符合我的预期。等到队友们基本都过了,我才勉强A题。

Read More

CF拉练第四场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=62931#overview 比赛总结 这场比赛开的时候,我还在南京= =,并没有好好做,过了水题之后就没有继续往下做了。 剩下的都是赛后补的题,不过自己的DP确实弱,很多都是自己想不明白,一看题解就懂。 分题讲解 A题(阅读题) 题意理解题,只要读懂题目就能A,并不是很难。 http://xuanwo.io/2014/11/13/CF-9A/ B题(字符串) C题(模拟) 感觉也是题意理解题,没有什么算法,只要模拟出翻面的操作就可以。 http://xuanwo.io/2014/11/13/CF-7A/ D题(扩展欧几里得) 用到了扩展欧几里得,模板题。 http://xuanwo.io/2014/11/19/CF-7C/ E题(状态压缩DP) 一开始不是特别明白,折腾了很久才看懂这个递推的公式。 http://xuanwo.io/2014/11/19/CF-8C/ 更新日志 2014年11月19日 初稿。

Read More

UVa 11400 Lighting System Design

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2395

理解

变量多的题目确实头疼,我来稍微捋一下。 题目中给出n中灯泡,不同的灯泡要用不同的电源,相同的灯泡可以使用相同的电源。然后每种灯泡有着四种参数,电压v,电源费用k,每个灯泡的费用c,所需要的该种灯泡的数量l。小脑一动就能明白,每次更换只会采用同一种灯泡,因为不同中灯泡的话要买两种电源,一定不是最优解。 这样的话,按照电压进行排序之后,可以得到递推公式: dp[i]=min(dp[i], dp[j]+(sum[i]-sum[j])*s[i].c+s[i].k) 其中sum[i]=sum[i-1]+s[i].l;

Read More

UVa 12563 Jin Ge Jin Qu hao

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4008

理解

~看完题目的名字就情不自禁的笑了= =。~ 这就是一个变形的背包问题:在t-1的时间内,最多可以选择多少歌曲使得歌曲数最多并且播放时间最长,差不多可以类比于ACM竞赛中的AC数和罚时。先比较播放歌曲数,取歌曲数较多者;如果歌曲数相同,比较播放时长,取播放时间较长的。 处理之后,就成了一个背包+一些判断的问题。

Read More