题意:在前100000个Fibonacci(以下简称F)数字里,能否在这100000个F里找出以某些数字作为开头的F。要求找出下标最小的。没找到输出-1。
代码:(Accepted,0.250s)
1 | //UVa12333 - Revenge of Fibonacci |
分析:暴力求出前100000个F数字的话妥妥地超时。我一开始也想只取前面多少位以减少计算,担心出现99999...999什么什么的情况,导致精度不对,但看网上取50位的都过了,那就不虚了。 思路是用树的结构,每一位数(next)为一个结点,每个结点还储存“遍历到当前位数时满足的最小的F下标(index)”。若某个F刚好遍历到当前结点时结束,则修改当前结点index为当下F下标,并将其置为不可修改状态(flag:=true;)。若F遍历到当前还未结束,则若当前下标小于已储存下标且flag=false,则修改当前index。其实很好理解,但我好像说的不太清楚。 这题并没用到STL,看网上也是这样。数据结构的组建参考了 http://blog.csdn.net/a197p/article/details/44170921 。真的只是大概的看两眼那两个结构体,看了两眼想自己思考实现出来,但最后自己实现出来发现结构体里的变量和他的一样,最好的实现方法也只能是这样。最神奇的是甚至insert函数和search(他的query)函数和我的都和他写的一样—。— 但是他的代码就是0.130s,而我的时间是他的两倍,明明差不多我却没找出多在哪里。但是大神的代码里有好多巧妙的地方,比如他的 tnode dict[nodesize];//line 14
tnode* newnode() { return &dict[size++]; }//line 31
这样就免去了每次都new,节约时间还免去了delete的烦恼,厉害了。于是毫不犹豫抄过来。再比如他的 memset(dict,0,sizeof(dict));//line 28
我一开始是在struct EACH_DIGIT
里面写了个构造函数 EACH_DIGIT():flag(0),id(0){memset(next,NULL,sizeof(next));}
但是发现他一个memset全设为0和我效果不是一样的嘛。刷过去还快。
v1.5.2