\u9ad8\u7cbe\u5ea6\u6574\u6570+STL\u3002\u770b\u5230\u9898\u7684\u60f3\u6cd5\u5176\u5b9e\u662f\u9ad8\u7cbe\u5ea6\u6574\u6570+Trie\uff0c\u7136\u800cTrie\u5e76\u6ca1\u5199\u8fc7\uff08\u4e5f\u5199\u4e0d\u6765\uff09\uff0c\u4f55\u51b5\u65f6\u95f4\u8db3\u8db3\u670910s\uff0c\u4e5f\u6ca1\u5fc5\u8981\u7528Trie\uff0c\u4e8e\u662f\u4f7f\u7528\u4e86\u5b57\u7b26\u4e32\u52a0\u6cd5+unordered_set\u3002\u4e3a\u4e86\u52a0\u5feb\u67e5\u627e\uff0c\u4e0d\u540c\u957f\u5ea6\u7684\u524d\u7f00\u5206\u522b\u5355\u72ec\u5f00unordered_set\u5b58\u653e\u3002\u65b9\u4fbf\u8d77\u89c1\uff0c\u6240\u6709\u6570\u5b57\u6211\u90fd\u662f\u53cd\u7740\u5b58+\u7528\u7684\u3002\u52a0\u6cd5\u6ca1\u5fc5\u8981\u4fdd\u5b58\u6574\u6bb5\u6570\u5b57\uff0c\u524d50\u4f4d\u5c31\u591f\u7528\u4e86\uff08\u53cd\u6b63\u540e\u9762\u8fdb\u4f4d\u5c0f\u5230\u53ef\u4ee5\u5ffd\u7565\uff09\u3002\u53e6\u5916\uff0c\u8bf4\u597d\u4e86smaller than 100000\u771f\u7684\u591a\u4e00\u70b9\u4e5f\u4e0d\u884c\uff0c\u4e4b\u524d\u6ca1\u4ed4\u7ec6\u770b\u7ed3\u679c\u4e00\u76f4WA\u3002<\/p>\n
<\/p>\n
\u5199\u8fd9\u9898\u521a\u5f00\u59cb\u6ca1\u60f3\u5230\u53ea\u7528\u524d50\u4f4d\u3002\u4e4b\u540e\u5199\u5b8c\u5b57\u7b26\u4e32\u7248\u672c\u540e\u8bd5\u4e86\u4e00\u4e0b\u7b97\u5230100000\uff0c\u611f\u89c9\u6709\u8d85\u65f6\u7684\u53ef\u80fd\uff0c\u4e8e\u662f\u5c31\u6539\u7528\u5927\u6574\u6570\u677f\u5b50\u4e86\uff0c\u6ca1\u60f3\u5230\u5927\u6574\u6570\u53ea\u7528\u4e861570ms\u3002\u540e\u6765\u60f3\u901a\u4e86\u5c31\u7b80\u5355\u6539\u6210\u4e86\u5b57\u7b26\u4e32+\u524d50\u4f4d\uff0c\u7acb\u523b510ms\u3002\u4f18\u5316\u7a7a\u95f4\u5176\u5b9e\u8fd8\u5f88\u5927\uff0c\u4ee3\u7801\u5199\u7684\u4e5f\u5f88\u70c2\u3002<\/p>\n
#include <iostream>\r\n#include <cstdlib>\r\n#include <vector>\r\n#include <algorithm>\r\n#include <unordered_set>\r\n#include <unordered_map>\r\n#include <set>\r\n\r\nusing namespace std;\r\n#define _for(i,j,k) for (int i=(j); i<=(k); i++)\r\n\r\nstring rev_add(string& a, string& b) {\r\n string r;\r\n int i = 0, carry = 0, sum = 0;\r\n while (i < a.size() || i < b.size()) {\r\n sum = carry;\r\n if (i < a.size()) sum += (int) (a[i] - '0');\r\n if (i < b.size()) sum += (int) (b[i] - '0');\r\n r.push_back(sum % 10 + '0');\r\n carry = sum \/ 10; i++;\r\n }\r\n if (carry > 0) r.push_back(carry + '0');\r\n if (r.size() > 50) {\r\n a = a.substr(1, a.size() - 1);\r\n b = b.substr(1, b.size() - 1);\r\n return r.substr(r.size() - 50, r.size());\r\n }\r\n return r;\r\n}\r\n\r\nunordered_set<string> quizCache[41];\r\nunordered_map<string, vector<int>> quizCase;\r\n\r\nint main() {\r\n string num;\r\n int n, *output, min_length = 0, cur = 1, end, numLen;\r\n cin >> n;\r\n output = (int*) malloc(n * sizeof(int));\r\n _for(i,0,n-1) {\r\n cin >> num;\r\n if (num == "1") {\r\n output[i] = 0;\r\n continue;\r\n }\r\n output[i] = -1;\r\n reverse(num.begin(),num.end());\r\n quizCache[num.size()].insert(num);\r\n if (quizCase.count(num) == 0)\r\n quizCase[num] = vector<int>();\r\n quizCase[num].push_back(i);\r\n }\r\n while (++min_length <= 40 && quizCache[min_length].size() == 0);\r\n string fn_2 = "1", fn_1 = "1", fn, sub;\r\n while (min_length <= 40 && cur < 100000 - 1) {\r\n fn = rev_add(fn_2, fn_1);\r\n fn_2 = fn_1; fn_1 = fn; cur++;\r\n if (fn.size() < min_length) continue;\r\n _for(length,min_length,min((int) fn.size(), 40)) {\r\n if (quizCache[length].size() == 0) continue;\r\n sub = fn.substr(fn.size()-length, fn.size());\r\n if (quizCache[length].count(sub) > 0) {\r\n quizCache[length].erase(sub);\r\n for (int ind: quizCase[sub]) output[ind] = cur;\r\n if (quizCache[length].size() == 0) {\r\n min_length = 0;\r\n while (++min_length <= 40 && quizCache[min_length].size() == 0);\r\n }\r\n }\r\n }\r\n }\r\n _for(i,0,n-1) cout << "Case #" << i+1 << ": " << output[i] << endl;\r\n return 0;\r\n}<\/pre>","protected":false},"excerpt":{"rendered":"\u9ad8\u7cbe\u5ea6\u6574\u6570+STL\u3002\u770b\u5230\u9898\u7684\u60f3\u6cd5\u5176\u5b9e\u662f\u9ad8\u7cbe\u5ea6\u6574\u6570+Trie\uff0c\u7136\u800cTrie\u5e76\u6ca1\u5199\u8fc7\uff08\u4e5f\u5199\u4e0d\u6765\uff09\uff0c\u4f55\u51b5\u65f6\u95f4\u8db3\u8db3\u67091 … <\/p>\n