ITPub博客

首页 > 应用开发 > IT综合 > 我的做题笔记 (转)

我的做题笔记 (转)

原创 IT综合 作者:amyz 时间:2007-10-17 18:39:50 0 删除 编辑
我的做题笔记 (转)[@more@]

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
ASP?id=1000">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。


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752019/viewspace-977250/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7363970