郁闷的有道难题


一开始太激动了。。。还以为是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,百度之星,有道难题,都只过了初赛。这一方面,说明我的算法水平纵向地比,比以前有了很大提高,但是横向比较的话,还是处在一个比较低的水平。毕业以后可能提高算法水平的机会不太多了,争取在毕业前多做一些题,多学一些。此外,不能只顾着做题的量,不能闭门造车,要多学习牛人的代码开阔思路。


posted on 2009-06-21 22:30 YZY 阅读(445) 评论(9)  编辑 收藏 引用 所属分类: AlgorithmMiscellaneous

评论

# re: 郁闷的有道难题 2009-06-22 18:14 春天

你好!认识下,我最近差不多做了你说的这些事。我的结果很惨淡,水平不够,继续努力。  回复  更多评论   

# re: 郁闷的有道难题[未登录] 2009-06-22 18:20 YZY

@春天
呵呵,我水平也很差,相互学习吧  回复  更多评论   

# re: 郁闷的有道难题 2009-06-22 18:48 春天

通过你的日志了解到你现在在读大学,对吧?我有时遇到困难,就容易停止不前了,我们相互勉励,相互竞争,争取早日进入下一阶(topcoder),如何?
我的ID zhuimengboy65 做了一次rating。  回复  更多评论   

# re: 郁闷的有道难题[未登录] 2009-06-22 18:59 YZY

@春天
呵呵,我硕士快毕业了。  回复  更多评论   

# re: 郁闷的有道难题 2009-06-22 22:04 goodidea

你写的代码是少点,但是运行起来效率还是不是很高,我初赛出了点问题没进,我写了用构造法直接给了结果
http://gc063tzf.blog.163.com
可以交流一下,我大三,学机械的,不过对编程还有点兴趣  回复  更多评论   

# re: 郁闷的有道难题[未登录] 2009-06-22 22:12 YZY

@goodidea
这个算法的复杂度我自己也没办法分析。不过比回溯法生成应该也不会慢。
我看了你的算法,比我快的地方在于后面直接生成010101这样的.这样编码麻烦且容易出错是.我算法log(n)步就可以从1e17到101010101010这样啊  回复  更多评论   

# re: 郁闷的有道难题 2009-06-22 22:38 goodidea

不过你的递归算法还是用的比较好的,学习啦。
对了你的第二个题怎么考虑了?也欢迎给我留言  回复  更多评论   

# re: 郁闷的有道难题[未登录] 2009-06-23 09:01 YZY

@goodidea
我的算法应该是logn*logn的复杂度  回复  更多评论   

# re: 郁闷的有道难题 2009-06-24 00:15 goodidea

@YZY
呵呵,你分析的在理,最初我也想用递归的,但是对这个题还是没想好递归的出口,以及准确性,所以就按自己想法写了一片代码。。。。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜