5
ABCED
BDACE
EBBAA
1 0 3 4 2
数据规模
对于30%的数据,保证有N<=10;
对于50%的数据,保证有N<=15;
对于全部的数据,保证有N<=26。
<算法分析>
经典的搜索题。最单纯的搜索的时间复杂度为O(n!),是会非常严重的超时的。计算机是很“笨”的,它不会思考,在盲目搜索的过程中,很容易出现这种情况:
计算机在某一位搜索出了一个算式1 + 1 = 3,并且继续搜索。
明显,人眼很容易就看出这是不合法的,但计算机不会。于是,我们想到了第一个剪枝:每次搜索的时候,从最后向前判断是否有不合法的式子。
这一个剪枝非常简单,但是效果却非常的好。因为它剪去了很多不必要的搜索。为了配合这一种剪枝更好的实行,搜索顺序的改变也成为大大提高程序效率的关键:从右往左,按照字母出现顺序搜索,有很大程度上提高了先剪掉废枝的情况,使程序的效率得到大大的提高。
有了以上两个剪枝,程序就已经可以通过大部分测试点了。但是有没有更多的剪枝呢?答案是肯定的。
根据前面的剪枝,我们可以找到类似的几个剪枝:
对于a + b = c的形式,假如:
A***?***
+ B*?**?**
C***???*
其中*代表已知,?代表未知。那么,A + B与C的情况并不能直接确定。但是,假如(A + B) % N与(A + B + 1) % N都不等于C的话,那么这个等式一定是不合法的。因为它只有进位和不进位的两种情况。
同样,我们在一个数组里记录了Used[i]表示一个数字有没有用过,那么,对于某一位A + B = C的等式,如果已经得到了两个数,另一个数还待搜索的时候,我们还可以根据这个加入一个剪枝:
例如A + ? = C的形式,
考虑不进位的情况,则?处为P1 = (C - A + N) % N
假如考虑进位的情况,则?处为P2 = (C - A - 1 + N) % N
假如P1、P2均被使用过,那么这个搜索一定是无效的,可以剪去。
有了以上的剪枝,就可以很轻松地通过所有的测试数据了。当然,还有很多值得思考的剪枝以及其他的思路,例如枚举进位、解方程(但是可能需要枚举)等,在这里就不详细讨论了。