12333 - Revenge of Fibonacci （UVA）

题目链接如下：

Online Judge

全网只有我一个人是用这种笨办法解出来的吗……耗时9秒多卡进10秒AC.....

字典树啥的我都没学过不懂...需要学习一下。

代码如下：

#include 
#include 
#include 
#include 
#include 
// #define debug
const int maxx = 100000;
 
int T;
std::string s;
std::unordered_mapint> mp;
std::vector vec(maxx);
char toSum[70];
int toCarry[70];
 
void fibo(int k) {
  int i, j, carry = 0;
  int sz = std::min(vec[k - 2].size(), vec[k - 1].size());
  for (i = 0; i < sz; ++i) {
    int temp = vec[k - 2][i] + vec[k - 1][i] + carry - '0';
    carry = toCarry[temp];
    vec[k].push_back(toSum[temp]);
  }
  if (vec[k - 2].size() != vec[k - 1].size()) {
    j = sz == vec[k - 2].size() ? 1 : 2;
    sz = vec[k - j].size();
    while (i < sz) {
      int temp = vec[k - j][i] + carry;
      carry = toCarry[temp];
      vec[k].push_back(toSum[temp]);
      ++i;
    }
  }
  if (carry) {
    vec[k].push_back('1');
  }
  std::string temp;
  sz = std::max(0, (int)vec[k].size() - 40);
  for (i = vec[k].size() - 1; i >= sz; --i) {
    temp.push_back(vec[k][i]);
    if (mp.find(temp) == mp.end()) {
      mp[temp] = k;
    }
  }
}
 
int main() {
#ifdef debug
  freopen("0.txt", "r", stdin);
  freopen("1.txt", "w", stdout);
#endif
  for (int i = 48; i <= 57; ++i) {
    toCarry[i] = 0;
    toSum[i] = i;
  }
  for (int i = 58; i <= 67; ++i) {
    toCarry[i] = 1;
    toSum[i] = i - 10;
  }
  vec[0] = vec[1] = "1";
  mp[vec[0]] = 0;
  for (int i = 2; i < 100000; ++i) {
    fibo(i);
  }
  scanf("%d", &T);
  for (int i = 1; i <= T; ++i) {
    std::cin >> s;
    printf("Case #%d: %d\n", i, mp.find(s) != mp.end() ? mp[s] : -1);
  }
#ifdef debug
  fclose(stdin);
  fclose(stdout);
#endif
  return 0;
}

试着用字典树改了一下，还需要五秒多……代码如下：

#include 
#include 
#include 
#include 
// #define debug
const int maxx = 100000;
 
struct trieNode{
    int key = -1;
    trieNode* son[10] = {nullptr};
};
trieNode* root = new trieNode;
int T;
std::string s;
std::vector vec(maxx);
char toSum[70];
int toCarry[70];
 
void insert(std::string ss, int k){
    trieNode *curr = root;
    ss = ss.substr(0, 40);
    for (int i = 0; i < ss.size(); ++i){
        if (!curr->son[ss[i] - '0']){
            trieNode *temp = new trieNode;
            temp->key = k;
            curr->son[ss[i] - '0'] = temp;
        }
        curr = curr->son[ss[i] - '0'];
    }
}
 
int trieFind(std::string ss){
    trieNode *curr = root;
    for (int i = 0; i < ss.size(); ++i){
        if (!curr->son[ss[i] - '0']){
            return -1;
        }
        curr = curr->son[ss[i] - '0'];
    }
    return curr->key;
}
 
void fibo(int k) {
  int i, j, carry = 0;
  int sz = std::min(vec[k - 2].size(), vec[k - 1].size());
  for (i = 0; i < sz; ++i) {
    int temp = vec[k - 2][i] + vec[k - 1][i] + carry - '0';
    carry = toCarry[temp];
    vec[k].push_back(toSum[temp]);
  }
  if (vec[k - 2].size() != vec[k - 1].size()) {
    j = sz == vec[k - 2].size() ? 1 : 2;
    sz = vec[k - j].size();
    while (i < sz) {
      int temp = vec[k - j][i] + carry;
      carry = toCarry[temp];
      vec[k].push_back(toSum[temp]);
      ++i;
    }
  }
  if (carry) {
    vec[k].push_back('1');
  }
  std::string temp;
  sz = std::max(0, (int)vec[k].size() - 40);
  for (i = vec[k].size() - 1; i >= sz; --i) {
    temp.push_back(vec[k][i]);
  }
  insert(temp, k);
}
 
int main() {
#ifdef debug
  freopen("0.txt", "r", stdin);
  freopen("1.txt", "w", stdout);
#endif
  for (int i = 48; i <= 57; ++i) {
    toCarry[i] = 0;
    toSum[i] = i;
  }
  for (int i = 58; i <= 67; ++i) {
    toCarry[i] = 1;
    toSum[i] = i - 10;
  }
  vec[0] = vec[1] = "1";
  insert(vec[0], 0);
  for (int i = 2; i < 100000; ++i) {
    fibo(i);
  }
  scanf("%d", &T);
  for (int i = 1; i <= T; ++i) {
    std::cin >> s;
    printf("Case #%d: %d\n", i, trieFind(s));
  }
#ifdef debug
  fclose(stdin);
  fclose(stdout);
#endif
  return 0;
}