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

Codeforces Beta Round 9 D How many trees? (Div.2 Only)

题目

源地址:

http://codeforces.com/problemset/problem/9/D

理解

神DP,给战斗民族的数学功底跪了。 一个二叉搜索树,要求左子树的和小于右子树,问存在多少个这样的数。由题意可以推出这样一个结论:左子树的和小于右子树,只要左子树的最大值小于右子树的最大值即可,因为2^0+2^1+2^p-1<2^p。 所以在求dp[i][j]~(dp[i][j]表示i个点组成高度小于等于j的树的总数)~的时候,有两种情况: 1. 子树的中n-1个点权在左子树,要么全在右子树,这样的话就没有条件限制了。 2. 如果左右子树都有,那么最大的肯定要放在右子树上,所以除了当前根和最大的点,其他点(总共i-2个)随便取 ,枚举左子树最多放几个,右子树最多放几个就可以推出来。 转移转移方程为:dp[i][j]+=dp[k][j-1]*dp[i-k-1][j-1]

Read More

Codeforces Beta Round 7 D Palindrome Degree

题目

源地址:

http://codeforces.com/problemset/problem/7/D

理解

被引入的新概念吓到了= =,其实这道题就是一个求最大回文串的问题。 不过按照这个数据量,每一次都进行strcmp肯定不现实,所以我们需要一个好的字符串hash(的板子)。预处理之后,分别计算前缀和后缀的hash值。如果hash值相等,说明前缀和后缀相同,它们的度数就是长度/2再加上一。然后结果就是度数的和。

字符串hash的时候那个素数开大一点比较好,不用去处理hash冲突,23333。

Read More

Codeforces Beta Round 8 B Obsession with Robots

题目

源地址:

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

理解

在那遥远的地方有位好姑娘 ,人们走过她的帐篷都要留恋的张望 23333,不逗比了,真正的题解开始。 在一个无穷大的平面上,有一个机器人可以自由地上下左右移动。然后在它移动的路径上,你可以给它设置任意个障碍。如果存在一种障碍的设计,使得机器人的移动路径是最短路径,则OK;如果不存在,则存在BUG。 这道题写得很逗= =。一开始作死用switch来写,不过在字符的判断上好像写搓了,怎么写都是BUG。后来想到可以用一个vis来标记机器人走过的路径,如果存在一个点被访问过两次,那么这个路径一定不是最短路径。不过这份代码挂了,原因是还存在另外一种可能,比如:URD。也就是说,只要形成一个类似于U的结构,也一定不是最短路径。一时半会儿没想出来什么高效的方案,干脆暴力敲了一个。设一个flag出来,然后每走一个点,就四个方向判断一下是否访问过,如果flag>=2,说明一定是BUG。 多亏了CF机子好,居然过了,也是RP好。

Read More

Codeforces Beta Round 9 C Hexadecimal's Numbers (Div.2 Only)

题目

源地址:

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

理解

题意不难理解。给定一个n,要你求出从0到n有多少个仅用0和1能表示出来的数。 想法很简单,我们先来处理最为简化的情况,如果给定一个二进制数,我们要求出比这个小的二进制数的个数有多少。小脑一动,我们就能知道,这个个数就是这个二进制数转化为十进制数的大小。 那么问题来了,给定一个十进制数,我们怎样才能求出这个最大的二进制数呢?其实我们可以这样来处理:每一位都有三种情况,0或者1或者大于1。0和1不需要进行任何操作,如果大于1,我们则把从这一位起的每一位都变成1。这样处理之后,我们就得到了最大的二进制数。然后就是一个简单的进制转换问题。

其实当天晚上的BestCoder 18的1003题跟这个有点像,不过做BC的时候,我没有捋清楚思路,最后还是没有敲出来。不过多亏被虐了一发,这道题才顺利地推出了结论。

Read More

UVa 1025 A Spy in the Metro

题目

源地址:

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

理解

其实题目还是蛮吓人的= =,因为上来就是Line1~7的输入。其实题意不难,有从左到右编号为1~n的车站,有m1辆车从第1站往右开,有m2辆车从第2站往左开。主角在t=0的时候从第1站出发,要在t时刻遇见车站n的一个间谍。要求求出最短的等待时间,没有的话就输出impossible。 小脑一动,可以知道,每一次有三个选择:等待,向左,向右。我们可以用dp[t][i]来表示第t时刻在第i个车站,然后用vis[t][i][sta]来表示三种选择。全部预处理一遍之后,dp求解最短时间即可。

Read More