USACO 2.2.3 Runaround Numbers 解题报告
这题首先是一个枚举,从输入的数加一开始每个数字都看是不是题目所要的数。判断方法如下: 先把数字用字符串保存起来,然后读取一个数字并且标记为’x’,再读取一个,判断是否为’x’,如果为x就不是要求的数字,如果不是就继续读取,直到每个数字都被读取了,并且最后指针回到了第一个位置,那么这就是所需要的那个[……]
这题首先是一个枚举,从输入的数加一开始每个数字都看是不是题目所要的数。判断方法如下: 先把数字用字符串保存起来,然后读取一个数字并且标记为’x’,再读取一个,判断是否为’x’,如果为x就不是要求的数字,如果不是就继续读取,直到每个数字都被读取了,并且最后指针回到了第一个位置,那么这就是所需要的那个[……]
这一题是一个动态规划题,f[i][j]是i个数字(1, 2, 3, 4, .., i)能够组成和为i的个数,那么方程式是f[i][j] = {f[i – 1][j – k] + f[i – 1][j]} (1 <= k <= i),再DP就是的,代码如下: / LANG: C ID: y[......]
这题一开始确实会感觉很难,但是罗马数字的个位只有可能是{"I", "II", "III", "IV", "V", "VI", "VII", "VIII[……]
这题的话,话说感觉就是一个暴力的枚举,没多余要考虑的,一方面对所有整数开始枚举,设当前枚举的是i,那么在用i和所有已知的海明码进行比较,海明距离大于等于D的话就成为一个新的海明码,一直枚举出N个海明码。 得出海明距离也很简单,就从第一个位开始,一个不同的就记录一下,我直接把8位都枚举一次,所以B这[……]
咋一看,真是一个爆难的题目,但是仔细一想,其实也很简单,怎么个简单呢?对于每种食物来说,只有两种选择:吃或不吃,对吧,暴力枚举就是,只有2^15种方案,虽然数字还是非常大的,但是一秒钟的时限还是超不了,代码晚点发,在Linux下。 代码来了: / ID: yylogoo1 PROG: holste[......]
首先用两个数组分别保存排了序的数组和没排序的数组,然后再根据这两个判断,当前这个位置上应该是放什么数,而实际上放的是什么数,如果两个位置上需要的都正好是对方所有的,那么这是最好的,进行循环,把所有这种的都交换掉,然后累计交换次数。 但是最后会有这么一种情况,三个位置需要的分别是1, 2, 3,而他[……]
这题我的方法就是下面这个,不然的话就要爆搜,这个规律不知道平时用的上不,但现在这会儿挺好用:
0/1 1/1 1/2[......]
这题的话,就是贪心,把最大的罪恶值的两个囚犯都不关在一个牢房里,反复的贪心,但是数据太大,不允许使用邻接表和邻接矩阵,用什么结构来保存呢?我觉得(也是网上的资料里的咯)使用动态分配是个方法,因为最多10000条边,根据实际情况来分配,这样不会有浪费的空间,也就不会导致空间爆掉了。