CF拉练第四场

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

Read More

Codeforces Beta Round 8 C Looking for Order

题目

源地址:

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

理解

群里面讨论时,萌神说是一个状态压缩DP,然后我就主动放弃了这道题= =。 实际上,如果用枚举的方法来更新DP,肯定会超时的,有一个小小的技巧在于,小女孩拿东西是没有顺序的。然后在每一次拿东西的时候,都需要更新出两个状态,一种是只拿一个,另一种是拿两个。

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

UVa 116 Unidirectional TSP

题目

源地址:

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

理解

这道题和之前做过的一道求最大四位数和有点像。那道题我是用暴力+乱搞过得,这道题则是用了刚学的DP。 不用看题,光是看图和样例就能明白大概的题意:给定一个m*n的矩阵,要求从左往右依次选择n个数,使得这n个数的和最小。不过存在这样的限制条件:首先,每次都只能选择当前数的相邻数,也就是右上,右方,右下;其次,要求字典序最小。 找到这样的一个序列并不难,不过要求输出字典序最小的就有点麻烦。通过从右向左来扫描,就能解决这样的问题。

Read More

UVa 1347 Tour

题目

源地址:

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

理解

给出n个定点,要求计算出连接这些点的最短闭合路径。 使用dp[i][j]来保存从i到1再从1到j的最短距离。然后可以得到这样两条递推公式:

dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis(i,j));
dp[i][j]=dp[i-1][j]+dis(i,i-1);

最后的结果就是遍历一遍dp[n][i]+dis(n,i),找到最小值。

Read More

CF拉练第五场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=62933#overview 比赛总结 前面被BC艹了一顿爆零之后,这场手感还不错。好多都是暴力+乱搞的题目,打得还行。不过自己的DP还是太弱,那场DP还得好好补,要不然像E这种题目只能看人品。 分题讲解 A题(字符串) 贪心+乱搞,水过的题目。为了抢时间都没有测数据,幸运1A。 http://xuanwo.org/2014/11/16/CF-11A/ B题(进制转换) 机智+乱搞。 这个题正好跟前面那场BC有点像,能过也有点运气成分。不过思路出来之后敲得有点慢,这个是弱点。水题要出的快,出的稳,这样才能保住铜牌,233333。 http://xuanwo.org/2014/11/16/CF-9C/ C题(暴力) 暴力+乱搞。 这道题只要能正确的找出导致BUG的两类情况就能A,我少考虑了一种,WA了一发,2A。 http://xuanwo.org/2014/11/16/CF-8B/ D题(字符串Hash,DP) 字符串Hash+乱搞。 开了一个好几个50万的数组乱搞,感谢CF不限制内存占用= =。 http://xuanwo.org/2014/11/16/CF-7D/ E题(神DP) 有一个神奇的递推公式,猜一猜,看RP,赛后出证明。 http://xuanwo.org/2014/11/16/CF-9D/ 更新日志 2014年11月16日 完成题解。

Read More