USACO/crypt1

分析

有两种方法，第一种较容易理解，第二种速度O(1)

第一种：穷举法

   S1  S4  S5
×     S2  S3

约束条件只有3个：第3、4行是3位数，第5行是4位数。我们按S1到S5的顺序搜索。

如果S1×S2>10或者S1×S3>10，则3、4行肯定不是3位数，剪枝。

即S1*S2+S4*S2/10>=10 || S1*S3+S4*S3/10>=10 剪枝

补充: 从高位到低位，从小到大填数据，如果发现乘积超过999就剪枝。 见代码PASCAL中MZD的

---

最坏情况分析，就是九位{1，2，3，4，5，6，7，8，9} 这种情况下，O(9^5*10),不超过8位，可以接受 所以只需要五层循环嵌套（或者选择回溯算法，不过没必要），产生两个乘数，甚至不需要剪枝，直接进行相乘，相加，并且判断就可以

第二种：Hash搜索法

可以用用哈希表设计O(1)的穷举法.

两个乘数的位数是固定的，第一个数一定是100到999之间，第二个数只能是10到99之间。
既然如此，那么我们完全没有必要用DFS去按数位搜索，直接穷举100到999间的所有数以及10到99间的所有数。
然后计算乘积与两个分部乘积，判断乘积是否为四位数（是否在1000到9999之间），以及两个分部乘积的位数是否符合要求。
再判断他们是否由给定的数字组成，如果上面的判断都通过了，则计数器加1。
穷举的个数是常数，第一个数有900种可能，第二个数有90种可能，一共有81000种可能。判断是否由给定数字组成的时间复杂度是O(n)。故整个算法的时间复杂度是O(81000n)=O(n)。
然而这还有改进的余地，将可使用数字存在哈希表而不是线性表里。
定义hash[i]:
如果数字i是可以被使用的，则hash[i]=1否则为0。
利用这hash结构，要判断一个固定位数的数是否由给定数字组成，复杂度为O(1)。
故整个算法的时间复杂度也是O(1)。
By Aikilis
下面是这个算法的测试结果：

Executing...
   Test 1: TEST OK [0.000 secs, 1832 KB]
   Test 2: TEST OK [0.000 secs, 1832 KB]
   Test 3: TEST OK [0.000 secs, 1832 KB]
   Test 4: TEST OK [0.000 secs, 1832 KB]
   Test 5: TEST OK [0.000 secs, 1832 KB]
   Test 6: TEST OK [0.000 secs, 1832 KB]
   Test 7: TEST OK [0.000 secs, 1832 KB]

All tests OK.

参考代码

C
C++
Pascal
Java

引用

[1]

[2]