一开始太激动了。。。还以为是Div2 的250呢。直接暴力就交了。。。
想想不对。。用1e17测了下,果然超时。。太脑残了今天。。
最后重提交了。。。cha对一个,cha错一个,得了个140+,排350多名。。泪奔啊。。
归根结底还是自己水平不行,继续努力吧。
贴一下最终的代码,还好过了system test,还有一点点安慰。。。
class UnrepeatingNumbers
{
public:
long long getNext(long long A)
{
return _get(A+1);
}
/*_get()函数用于获得>=A的第一个非重复数。
如果A是一个非重复数,直接返回。否则A必然为 xxaaXXXX形式。
其中XXXX为非重复的。也就是说我们找第一个重复数字。那
么下一个非重复数,必然大于(xxaa+1)0000。
这样就跟暴力比就大大减小了计算次数。。
*/
long long _get(long long A){
long long t = 1;
long long res = A;
int last = A%10;
A/=10;
while( A){
if( A%10==last){
return _get((A*10+last+1)*t);
}else{
last = A%10;
A/=10;
t*=10;
}
}
return res;
}
}
附题:
如果一个数字十进制表达时,不存在连续两位相同,则称之为“不重复数”。例如,105、1234和12121都是“不重复数”,而11、100和
1225不是。
给定一个long类型数字A,返回大于A的最小“不重复数”。
DEFINITION
Class:UnrepeatingNumbers
Method:getNext
Parameters:long
Returns:long
Method signature:long getNext(long A)
CONSTRAINTS
-A 取值范围是[0, 1017],注意是闭区间。
EXAMPLES
0)
54
Returns: 56
大于54的最小数字是55,但55不是“不重复数”。下一个数字是56,它满足条件。
1)
10
Returns: 12
2)
9
Returns: 10
3)
98
Returns: 101
99和100都不是“不重复数”,但101是。
4)
21099
Returns: 21201
虽然没什么名次,但还是应该吸取一些教训吧。
这次的问题主要在于:
1.水平问题 对题目限制条件不敏感,暴力不能解决问题,至少不能解决绝大部分问题。平时做题,对1000分的题基本上不看,对难题没信心
2.心态问题 作为一个混迹TopCoder这么长时间的还是一个绿色的资深loser来说,在一堆红黄蓝面前,开始就没打算能进top 200。不够足够认真,谨慎,开始就没有太强的比赛意识
教训有:
平时做题要和平时比赛一样,要紧张高效,不能慢慢吞吞的,加强Div2前两题的正确性和编码速度。尝试学习理解牛人代码,尝试解1000分题.写代码要争取一次编译通过,少在细节问题上犯错误。
比赛要全力以赴,至于结果如何并不全由自己能把握,不留遗憾,发挥出自己水平就可以了。
今年大的比赛可能都已经结束了,纵观腾讯tic,百度之星,有道难题,都只过了初赛。这一方面,说明我的算法水平纵向地比,比以前有了很大提高,但是横向比较的话,还是处在一个比较低的水平。毕业以后可能提高算法水平的机会不太多了,争取在毕业前多做一些题,多学一些。此外,不能只顾着做题的量,不能闭门造车,要多学习牛人的代码开阔思路。