SGU 108 Self-numbers 2

题意

http://www.nocow.cn/index.php/Translate:Sgu/108,翻译版,这里不再多说。

思路

这个题刚到手其实都是会写的,但是一般交上去会发现爆内存,原因就是我们用来判定self number的数组开太大了,要想减少空间复杂度只能从这个数组入手,那么我们真的需要那么大的数组么?显然是不用的,通过本题的数据范围可以发现N最大为7位数,即使7位全是9,我们能够更新到的数组区域长度也仅为63个单位,所以我们把bool标记数组开个63长度就够了,开100那更是没问题,这个技巧就是所谓的“滚动数组”。
滚动数组的操作方法有几点:1.通过求余来确定位置 2.使用完当前位置后,要给它初始化为没有使用过的样子以便以后的元素正常使用。
仅仅使用滚动数组还不足以完成这个题,还要注意输出答案的方式,因为数组在滚动,所以你不可能在完成判定之后再输出结果,而是应该边滚动判定,边记录,最后把记录的输出去。
本题有几个坑点:首先你要把输出的目标索引排个序,否则如果数据是乱序的基本都会跪,其次要注意请求的索引中是有重复的,可能一个索引被请求了多次。

代码

 

FZU 2159 WuYou

Proceed big numbers A and B,A and B have same digits(Both A and B have no prelude zeros),A contains uncertain digits marking ‘?’.Find a largest A to make A < B.

策略是先从前往后扫描一遍已知的数位,如果相等的话,放过当前位,如果当前位a>b这时停止扫描,纪录扫到的位置i,记录状态为1,如果当前位a<b这时停止扫描记录扫描到位置i,状态为2.

对与状态1,如果我们不能在i之前找到一个‘?’使这一位正好比b少1,那么无解,找到了的话,就记录这个新位置为i,跳到状态2。

对于状态2,只要令i左边的数位和B一样,右边的数位都是9就可以了。

都完成之后,做一下最终检查,注意只有一位数时首位可以为0,A!=B就可以了。

Scroll to top