UVA-12333 Fibonacci的复仇 题解答案代码 算法竞赛入门经典第二版

​​GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版​​

算法竞赛入门经典书中给出了大数类的算法，直接照抄即可。

我的做题过程：

1. 照着书上抄了大数类，下面的判断就使用循环查找。结果超时。

2. 大数类从int改成了long long，base成了10^16。结果还是超时。

3. 不直接存储大数类本身，只存储前40个数字的string的vector。结果超时。

3. 优化细节：iostream改成stdio.h，生成Fibonacci数列时采用长度为3的数组循环，减少大数类的赋值，所有循环中的变量都提前定义好，size()等函数都提前计算好保存。结果还是超时。

4. 在计算好Fibonacci数列后，直接结束函数，发现从Time limit exceeded变为了Wrong answer，看来计算数列的过程可能不是超时的原因，查找的时候才是。查找时候的复杂度最高是100000*50000。

5. 尝试对存储前40个数字的string的vector进行字典序排序，打算用二分查找找出字典序最符合的。结果发现这和题目要求不符，题目要求的不是字典序最靠前的，而是符合前n个数字时序号最靠前的，因此排序的方法行不通。

6. 发现字典树可以解决这个查找的问题。从根节点到当前节点路径形成的数字序列就是查找的序列，当前节点对应的值就是这个序列最早出现的序号。从超时变为Wrong answer。

7. 改了一点小问题，比如从数字转字符串时：1. 严格只要前40个；2. 注意非大数类中非第一个数子转换成字符串时，需要补前导0。结果AC。

AC代码

#include<stdio.h>
#include<string.h>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

struct BigInt {
  static const long long BASE = 1000000000000000000;
  static const int WIDTH = 18;
  static const int LEN = 4;
  
  vector<long long> s;
  BigInt(long long num = 0) {
    *this = num;
  }
  BigInt operator= (long long num) {
    s.clear();
    do {
      s.push_back(num % BASE);
      num /= BASE;
    } while(num > 0);
    return *this;
  }
  BigInt operator+ (const BigInt &b) {
    BigInt c;
    c.s.clear();
    long long g = 0, x;
    int ssize = s.size(), bssize = b.s.size();
    for(int i = 0; ; i++) {
      if(g == 0 && i >= ssize && i >= bssize) break;
      x = g;
      if(i < ssize) x += s[i];
      if(i < bssize) x += b.s[i];
      c.s.push_back(x % BASE);
      g = x / BASE;
    }
    return c;
  }
  string outN() {
    string str, st;
    int i = s.size() - 1, j = LEN;
    while(i >= 0 && j > 0) {
      st = to_string(s[i]);
      while(i != s.size() - 1 && st.length() < WIDTH) {
        st = "0" + st;
      }
      str += st;
      --i;
      --j;
    }
    return str.substr(0, 40); 
  }
};

struct Node {
  int id;
  int num;
  Node* childs[10] = {NULL};
};

vector<string> v;

Node* createTree() {
  int i, j, n, num;
  Node * tree = new Node;
  tree->id = -1;
  tree->num = -1;
  for(i = 0; i < v.size(); ++i) {
    n = v[i].size();
    Node *p = tree;
    for(j = 0; j < n; ++j) {
      num = v[i][j] - '0';
      if(!p->childs[num]) {
        p->childs[num] = new Node;
        p->childs[num]->id = i;
        p->childs[num]->num = num;
      }
      p = p->childs[num];
    }
  }
  return tree;
}

int main() {
  char s[45];
  int i, j, T, n, num, res;
  BigInt bv[3];
  bv[0] = 1;
  bv[1] = 1;
  v.push_back("1");
  v.push_back("1");
  for(i = 2; i < 100000; ++i) {
    bv[i % 3] = bv[(i-1) % 3] + bv[(i-2) % 3];
    v.push_back(bv[i % 3].outN());
  }
  scanf("%d", &T);
  
  Node * tree = createTree();
  
  for(i = 0; i < T; ++i) {
    scanf("%s", s);
    n = strlen(s);
    Node * p = tree;
    for(j = 0; j < n; ++j) {
      num = s[j] - '0';
      if(!p->childs[num]) {
        break;
      }
      p = p->childs[num];
    }
    if(j == n) {
      res = p->id; 
    } else {
      res = -1;
    }
    printf("Case #%d: %d\n", i+1, res);
  } 
  return 0;
}