UVA 12333 Revenge of Fibonacci

高精度整数+STL。看到题的想法其实是高精度整数+Trie，然而Trie并没写过（也写不来），何况时间足足有10s，也没必要用Trie，于是使用了字符串加法+unordered_set。为了加快查找，不同长度的前缀分别单独开unordered_set存放。方便起见，所有数字我都是反着存+用的。加法没必要保存整段数字，前50位就够用了（反正后面进位小到可以忽略）。另外，说好了smaller than 100000真的多一点也不行，之前没仔细看结果一直WA。

写这题刚开始没想到只用前50位。之后写完字符串版本后试了一下算到100000，感觉有超时的可能，于是就改用大整数板子了，没想到大整数只用了1570ms。后来想通了就简单改成了字符串+前50位，立刻510ms。优化空间其实还很大，代码写的也很烂。

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <set>

using namespace std;
#define _for(i,j,k) for (int i=(j); i<=(k); i++)

string rev_add(string& a, string& b) {
    string r;
    int i = 0, carry = 0, sum = 0;
    while (i < a.size() || i < b.size()) {
        sum = carry;
        if (i < a.size()) sum += (int) (a[i] - '0');
        if (i < b.size()) sum += (int) (b[i] - '0');
        r.push_back(sum % 10 + '0');
        carry = sum / 10; i++;
    }
    if (carry > 0) r.push_back(carry + '0');
    if (r.size() > 50) {
        a = a.substr(1, a.size() - 1);
        b = b.substr(1, b.size() - 1);
        return r.substr(r.size() - 50, r.size());
    }
    return r;
}

unordered_set<string> quizCache[41];
unordered_map<string, vector<int>> quizCase;

int main() {
    string num;
    int n, *output, min_length = 0, cur = 1, end, numLen;
    cin >> n;
    output = (int*) malloc(n * sizeof(int));
    _for(i,0,n-1) {
        cin >> num;
        if (num == "1") {
            output[i] = 0;
            continue;
        }
        output[i] = -1;
        reverse(num.begin(),num.end());
        quizCache[num.size()].insert(num);
        if (quizCase.count(num) == 0)
            quizCase[num] = vector<int>();
        quizCase[num].push_back(i);
    }
    while (++min_length <= 40 && quizCache[min_length].size() == 0);
    string fn_2 = "1", fn_1 = "1", fn, sub;
    while (min_length <= 40 && cur < 100000 - 1) {
        fn = rev_add(fn_2, fn_1);
        fn_2 = fn_1; fn_1 = fn; cur++;
        if (fn.size() < min_length) continue;
        _for(length,min_length,min((int) fn.size(), 40)) {
            if (quizCache[length].size() == 0) continue;
            sub = fn.substr(fn.size()-length, fn.size());
            if (quizCache[length].count(sub) > 0) {
                quizCache[length].erase(sub);
                for (int ind: quizCase[sub]) output[ind] = cur;
                if (quizCache[length].size() == 0) {
                    min_length = 0;
                    while (++min_length <= 40 && quizCache[min_length].size() == 0);
                }
            }
        }
    }
    _for(i,0,n-1) cout << "Case #" << i+1 << ": " << output[i] << endl;
    return 0;
}