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。 
|
本类阅读TOP10