题目

UVA12333

返回值

$-1073741819$

输入

15
1
12
123
1234
12345
9
98
987
9876
98765
89
32
51075176167176176176
347746739
5610

代码

// Problem: Fibonacci的复仇 Revenge of Fibonacci
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA12333
// Memory Limit: 0 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;


int l;
int pre[100010];

// 这些代码在紫书P124
struct NewInt
{
	int BASE = 100000000;
	int WIDTH = 8;
	vector<int> s;
	NewInt operator = (const string& str)
	{
		s.clear();
		int x, len = (str.length() - 1) / WIDTH  + 1;
		for (int i = 0; i < len; i++)
		{
			int end = str.length() - i * WIDTH;
			int start = max(0, end - WIDTH);
			sscanf(str.substr(start, end - start).c_str(), "%d", &x);
			s.push_back(x);
		}
		return *this;
	}
	NewInt operator + (const NewInt& b) const
	{
		NewInt c;
		c.s.clear();
		for (int i = 0, g = 0; ; i++)
		{
			if (g == 0 && i >= s.size() && i >= b.s.size())
			{
				break;
			}
			int x = g;
			if (i < s.size())
			{
				x += s[i];
			}
			if (i < b.s.size())
			{
				x += b.s[i];
			}
			c.s.push_back(x % BASE);
			g = x / BASE;
		}
		return c;
	}
};
// 感谢楼上提供的trie模板
struct node
{
	int v;
	node *c[10];
	node()
	{
		v = 100000000;
		for (int i = 0; i < 10; i++)
		{
			c[i] = NULL;
		}
	}
}trie;

void insert(NewInt x, int cur)
{
	int i;
	node *now = &trie;
	for (i = x.s.size() - 1; !x.s.at(i); i--);
	for (i; i >= 0; i--)
	{
		if (now->c[x.s.at(i)] == NULL)
		{
			now->c[x.s.at(i)] = new node;
			now = now->c[x.s.at(i)];
			now->v = min(now->v, cur);
		}
	}
}
int prev(int x[])
{
	node *now = &trie;
	for (int i = 0; i < l; i++)
	{
		if (now->c[x[i]] == NULL)
		{
			return -1;
		}
		now = now->c[x[i]];
	}
	return now->v;
}

int main()
{
	int T;
	cin >> T;
	string tmp;
	// 构造一个数组，表示前面的fibnacci数
	NewInt fibnacci[100005];
	fibnacci[0] = "1";
	fibnacci[1] = "1";
	insert(fibnacci[0], 0);
	for (int j = 2; j <= 100000; j++)
	{
		fibnacci[j] = fibnacci[j - 1] + fibnacci[j - 2];
		insert(fibnacci[j], j);
	}
	for (int i = 1; i <= T; i++)
	{
		bool flag = 0;
		cin >> tmp;
		l = tmp.size();
		for (int j = 0; j < l; j++)
		{
			pre[j] = tmp[j] - '0';
		}
		printf("Case #%d: %d\n", i, prev(pre));
		
	}
}