题意：如果一个数中的某一段是长度大于2的菲波那契数，那么这个数就被定义为F数，前几个F数是13,21,34,55......将这些数字进行编号，a1 = 13, a2 = 21。现给定一个数n，输出和n相差最小的数ax与n的差值的绝对值，其中下标x满足是一个菲波那契数。
分析：该题所求真是九曲十八弯，说了那么多其实要解决的问题可以转化为给定一个x，求1-x之间有多少个F数，通过二分查找能够把下标是菲波那契数的序列求出来，之后就直接for循环找到那个最相近的数就可以了。关键是如何求解1-x之间有多少个F数，容易想到的是数位dp，但是这里不太好弄，因为10^11次方之内有50多个数，每个数又有一定的长度，因此通过枚举每一数位来直接dp状态记录成了问题，而ac自动机能够解决多串匹配的问题，因此通过建立一个ac自动机（使用静态数组实现），把状态映射到ac自动机上的静态数组下标上，这样一来状态数少了不说而且能够把这个匹配过程表示出来。其他地方和一般的数位dp没什么区别了。C++编译器调用abs函数WA了，看了看头文件确实没有long long型的重载，不过G++中调用abs竟然过了，因此索性改成手动判负。最近dev也不知怎么搞的，%I64d无法读入long long啊，本地不过提交AC这种事情真忧伤，索性cin了。
#include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> using namespace std; typedef long long LL; const int N = 600; LL n; int bit[20]; LL f[60]; LL dp[15][N]; // dp[i][j]表示剩余i位没有限制，并且已经在自动机中匹配到j位置的F数的个数 LL POW[15]; // 存储10的幂 LL seq[60]; LL suf[20]; queue<int>q; struct Ac_Auto{ int ch[N][10]; int fail[N]; bool flag[N]; int idx, root; int newnd() { memset(ch[idx], 0, sizeof (ch[idx])); flag[idx] = false, fail[idx] = 0; return idx++; } void init() { idx = 0, root = newnd(); } void insert(LL x) { int id = 0; while (x) bit[id++] = x%10, x/=10; int p = root; for (int i = id-1; i >= 0; --i) { if (!ch[p][bit[i]]) ch[p][bit[i]] = newnd(); p = ch[p][bit[i]]; } flag[p] = true; } void build() { for (int i = 0; i < 10; ++i) { if (ch[root][i]) { q.push(ch[root][i]); } } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 10; ++i) { int &v = ch[u][i]; int x = fail[u]; if (v) { q.push(v); while (x && !ch[x][i]) x = fail[x]; fail[v] = ch[x][i]; flag[v] = flag[v] || flag[fail[v]]; } else { v = ch[x][i]; // 直接通过引用来更改，叼啊 } } } } void find(LL x) { int id = 0; while (x) bit[id++] = x%10, x/=10; int p = root; for (int i = id-1; i >= 0; --i) { p = ch[p][bit[i]]; if (flag[p]) { cout << "OMG" << endl; return; } } } }; Ac_Auto ac; LL count(int p, int sta, bool bound) { if (p == 0) return 0; if (!bound && ~dp[p][sta]) return dp[p][sta]; int y = bound ? bit[p] : 9; LL sum = 0; int tsta; for (int i = 0; i <= y; ++i) { tsta = ac.ch[sta][i]; if (ac.flag[tsta]) { if (bound&&i==y) sum += suf[p-1]+1; else sum += POW[p-1]; continue; } sum += ::count(p-1, tsta, bound&&i==y); } if (!bound) dp[p][sta] = sum; return sum; } LL cal(LL x) { int idx = 1; while (x) suf[idx] = suf[idx-1]+x%10*POW[idx-1], bit[idx++] = x%10, x/=10; return ::count(idx-1, ac.root, true); } void prepare() { f[1] = 1, f[2] = 1; for (int i = 3; i <= 55; ++i) { f[i] = f[i-1] + f[i-2]; } ac.init(); for (int i = 7; i <= 55; ++i) { ac.insert(f[i]); } ac.build(); POW[0] = 1; for (int i = 1; i < 15; ++i) POW[i] = POW[i-1] * 10; memset(dp, 0xff, sizeof (dp)); LL tmp; for (int i = 2; i <= 55; ++i) { LL l = 13, r = POW[12], mid; while (l <= r) { mid = (l + r) >> 1; if ((tmp=cal(mid)) < f[i]) l = mid + 1; else if (tmp > f[i]) r = mid - 1; else seq[i] = mid, r = mid - 1; } } } int main() { prepare(); while (cin >> n, n != -1) { LL ret = 1LL << 60; for (int i = 2; i <= 55; ++i) { LL t = seq[i] - n; if (t < 0) t = -t; ret = min(ret, t); } cout << ret << endl; } return 0; }