UVA 100 - The 3n + 1 problem - 0:05.107 316K http://acm.uva.es/p/v1/100.html TLE 4次 WA 1次 AC n次 看了OIBH的介绍,我当初是决定用模拟+记忆化的方法来做,不过连续2次TLE了。后来改用了直接模拟不记忆的方法,结果还是TLE,真是百思不得其解。Bamboo说我应该得WA的,因为会有i>j的情况。我想想是该考虑上这种情况,又写了程序。这下子好了,不是TLE而是WA了,原来是输出的时候把交换后的i和j输出了,我这才知道为什么Bamboo的程序要先输出i和j再做交换。真笨!!
错误总结: 之前的TLE,估计是因为没有考虑细密,忽略了i>j的情况。WA是因为输出的时候也没有考虑好。如果用上记忆化,可能速度会快上一点。
UVA 101 - The Blocks Problem 0:00.040 64K http://acm.uva.es/p/v1/101.html TLE 2次 PE 1次 AC 2次 这次错在没有好好读题目,没有处理好输入不合法的情况,结果陷入死循环导致TLE(我发现UVA的TLE似乎都是死循环或是没考虑周密情况而发生的)。 PE是受了样例输出的HTML的误导。程序写得非常复杂,第一次的程序(101.pas)有3K,不过思路是可以看得很清楚的。第二次(101_2.pas)修改到2K后,思路有点看不清了,但核心就是把各段代码中重复的部分合起来,多次调用的同形式内容写成过程(函数)
错误总结: 没有认真读题。
UVA 102 - Ecological Bin Packing - 0:00.555 316K http://acm.uva.es/p/v1/102.html AC 1次 1次AC,挺高兴的。不过这道题目也没有什么难度。技巧方面有几个: 1.给定的数据读入时是按B G C的顺序,但是要求输出的时候,序列应按字母顺序排序,为了避免排序,在枚举的时候,就按B C G的顺序进行。所以数据读入部分,将读入的数据以B C G的顺序存放。 2.计算需要的移动数目时,不是一个个加,而是用总数减。如果箱子A专门放颜色X,则这个箱子中的颜色X肯定不用移动,其它的两种颜色就要移动到别的箱子中去。靠这个,我们枚举i,j,k,表示三个箱子分别留下哪种颜色不移动(即对应了这个箱子的颜色),然后计算差值,即可简单算出需要移动的数目。 3.由于i,j,k和肯定是6,k便可以不用枚举,而是用k:=6-i-j来计算。 4.为了方便记录i,j,k,用一个数组来保存,这样就可以整数组赋值。
最后是老想昏头的问题:能不能不改输入的B G C顺序,而是在枚举和计算的地方下手?我想是不行的,如果不把两者统一起来,在计算的时候就会混乱。
UVA 103 - Stacking Boxes - 0:00.008 64K http://acm.uva.es/p/v1/103.html WA 15次 OLE 3 次 AC n次 绝对是一个教训!这是一道DP题,方法我已经有了,是starfish告诉我的。然而我几乎是抄他的程序,结果却是WA。我检查了半天,怀疑了所有的部分,都没有查出为什么。最后重写了一遍,竟然就OK了!复查的时候,我把程序段分别替换,竟然都还是WA!最后!!!!!我才发现竟然是声明部分写错了,导致数组越界!而UVA的编译器给出的却是WA!害死我了!!!!!!
错误总结: 检查的时候不要漏检查声明部分,要在程序中用编译开关打开数组边界检查!
URAL 1000 - A+B Problem - 0.02 sec 389K http://acm.timus.ru/problem.asp?id=1000 AC 1次 无话可说!
URAL 1005 - Stone pile - 0.07 sec 504K http://acm.timus.ru/problem.asp?id=1005 AC 1次 这道题有两种作法。 1.回溯法 由于N比较少(N<20),我们可以设有两堆石块A,B。每个石块有两种状态:放在A,放在B。只要回溯枚举,算出A与B的差的绝对值,记下最小的就可以了。
2.DP 我们也可以设f[n,k]表示用前n个数是否可以算出k。我们可以得出状态转移方程: f[n,k] = f[n-1,k-Wn] OR f[n-1,Wn-k] OR f[n-1,k+Wn] 这样, 我们用两个数组进行翻滚就可以了
URAL 1009 - K-based numbers. - 0.02 sec 393K http://acm.timus.ru/problem.asp?id=1009 AC 1次 这道题也有两种作法. 1.枚举法 由题目条件2 <= K <= 10; 2 <= N; 4 <= N+K <= 18,我们可以推算出N<=8,数量并不算大,只要生枚举也是可以的。
2.递推法 由于题目只要求计数,我们便考虑是否可以采用递推、DP、组合数学的方法来计算。 我们可以这么考虑: 假设f[n,1]表示的是首位为0的“合法”的n位K进制数的个数,f[n,2]表示的是首位不为0的合法的n位K进制数。 这样,我们可以马上得到边界条件: f[1,1] = 1 (一个0就是一个数) f[1,2] = K-1 (K进制是从0..K-1共K个数,除去0,就只有K-1个了)
我们每次在最左边加上一个数字,然后我们可以写出下列的递推公式: f[n,1] = f[n-1,2] (由于不能同时出现两个0,所以在首位不为0的数前面加上一个0,就是这一类数的个数) f[n,2] = f[n-1,1]*(K-1) + f[n-1,2]*(K-1) (在首位为0的数前面加上一个不为0的数字,在首位不为0的数前面再加上一个不为0的数字,就是这一类数的个数)
现在已经解决了这个问题,时间复杂度为O(N),空间复杂度为O(2N)。
不过还有优化的余地。我们经过观察,发现由第一个递推关系,我们又可得f[n-1,1]=f[n-2,2],所以第二个递推关系可以写成: f[n,2] = f[n-2,2]*(K-1) + f[n-1,2]*(K-1)
这样我们就可以省去一个维,写成: f[n] = f[n-2]*(K-1) + f[n-1]*(K-1)
边界条件也要随之改变:f[1,1] = f[0,2] = 1 总之,边界条件就是 f[0] = 1 f[1] = K-1 注意:如果我们直接从定义去理解,f[0]是想不出来的,这就是递推的一个特点,要用公式去变换来找到具体值。
这样,我们就把空间复杂度降为了O(N)。不过还能进一步再优化。我们发现f[n]只与f[n-2]和f[n-1]有关,也就是说,我们只需要保存三个值就足够了。 我们可以用f0,f1,f2来保存,然后手工赋值翻滚,不过这样太麻烦了。我们还有更好的办法来实现:用MOD,写成这样: f[n MOD 3] = f[(n-1) MOD 3]*(K-1) + f[(n-2) MOD 3]*(K-1)
这样,我们只用定义一个数组,翻滚的操作就不需要我们来手工完成了。空间复杂度也降为了O(1)。
另外两道题URAL 1012和URAL 1013和这道题完全一样,只是数据变大了,只能使用递推来做,而且必须使用高精度计算。
URAL 1014 - The Product of Digits - 0.03 sec 393K - 2002.12.14 http://acm.timus.ru/problem.asp?id=1014 WA 2次 AC 1次 这道题也比较简单,考的是你思维的严密程度。先来分析算法: 题目给出一个数N,要求出一个数Q,其各位数字的乘积正好等于N。如果把N写成N=a1*a2*a3*...*an(a1>=a2>=a3>=...>=an),则Q=a1a2a3...an。又可得知,0<=ai<=9(i=1,2,3,...,n),进一步,ai=0,1都不能取(取0乘积是0,取1乘了也白乘),所以2<=ai<=9(i=1,2,3,...,n)。我们就可以得出算法了:将N分解为几个2~9的因数的乘积,统计个数,从从大到小输出相应个数的因数,就是所要求的数Q。显然,分解的顺序应是从大到小,这样分解出的因数个数是最少的,数Q的长度是最短的,数Q才是最小的。如果N不能被完全分解,即分解完成后N<>1,则说明不存在这样的数Q,就输出-1。
好了,算法是很简单的,但是……题目有以下两个陷井: 1.当N=1的时候,按我们的算法,会没有输出,这时应特别处理,直接输出1。我在做的时候,把N<10的情况都一起处理为直接输出N。 2.当N=0的时候,如果不注意,你会认为应该输出0。不过注意看题目:find the minimal positive integer,要求数Q为正数!所以应该输出的是10!
最后该说吐血的事了:我WA了两次都不是因为踏中上面的这两个陷井,而是被HTML的编码所害!如果用简体中文来看这道题,不存在合条件的数时应该输出的是"?",事实上!用ISO来看的时候,会发现那个"?"其实是"-1"!吐血吧?和UVA 103一样,又是一个教训!
错误总结: 看题目的时候,一定要把编码切换成ISO。
----------------------------------------------------- 附:我以后做新的题目,就直接修改这个,而不再另开新文章了:)
2002.12.14 - 今天改了一下URAL 1009,加了最后一行:)还有做了URAL 1014。 
|