12333

12333

题目链接如下：

Online Judge

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

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

代码如下：

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
// #define debug
const int maxx = 100000;int T;
std::string s;
std::unordered_map<std::string, int> mp;
std::vector<std::string> 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 debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);
#endiffor (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 debugfclose(stdin);fclose(stdout);
#endifreturn 0;
}