【贪心构造证明】Codeforces Round #814 (Div. 2) E. Fibonacci Strings

题意：
给定 $k$ 种不同的字符，第 $i$ 种字符有 $c_i$ 种。
所有字符可以随意顺序放，得到的序列按照相同数分成一段，问最后从前到后的每段数量是否可以构成一个斐波那契数列。
如：$a:1,b:2,c:3$
$abcbcc$ 对应为：$1(a),1(b),1(c),1(b),2(cc)$
$abbccc$ 对应为：$1(a),2(bb),3(ccc)$

如：$a:1,b:4,c:2$
$abccbbb$ 对应为：$1(a),1(b),2(c),3(bbb)$，这就是一个斐波那契数列
注意第一个和第二个值都为 $1$

数据范围：$1\le k\le 100,1\le c_i\le 10^9$

题解：
首先，易得斐波那契数列的个数是不会很多的，因为每个数最多 $10^9$，所以最大的一项不能超过 $10^9$；其次，因为需要将所有字符都分配出去，因此对应的字符数量和一定是一个斐波那契数列的前缀和。不满足上述的条件必然不能构成。

之后我们考虑如何去构造这个序列。
从最大的数开始，首先对应的字符种类的字符数量必须不小于这个最大的数，那么如果有多个，该选择哪个数呢？

对于最大的数，如果其不选择 $f[i]$，那么其最多可以选择的和是 $f[i-1]+f[i-3]+f[i-5]+...$

我们考虑如下问题：$f[i]\ge f[i-1]+f[i-3]+f[i-5]+...$，这里斐波拉契下标从 $0$ 开始
这个问题很好证明：

• $i$ 是偶数
  $f[i]>f[i-1]+f[i-3]+...+f[1]$
  因为 $f[i]=f[i-1]+f[i-2]$
  $f[i-2]>f[i-3]+...f[1]$
  因为 $f[i-2]=f[i-3]+f[i-4]$
  $f[i-4]>f[i-5]+...+f[1]$
  如此下去
  最后是：$f[2]>f[1]$，这是显然的。
• $i$ 是奇数
  $f[i]\ge f[i-1]+f[i-3]+...+f[0]$
  同上，最后是 $f[1]\ge f[0]$，这是显然的。

综上，如果最大的数 $a_{max}$ 不选择 $f[i]$，那么他最多只能选择的数不会大于 $f[i]$，甚至小于 $f[i]$，那么对于这个最大的数可能会用不完其所有的字符。因此，贪心地每次让最大的数选择即可，如果当前 $f[i]$ 找不到一个可以覆盖它的字符种类，那么无解。

代码：

#include 
using namespace std;

typedef long long ll;

const int N = 110; 
map<ll, int> mp;
ll fib[N];
ll a[N], n;

void solve() {
	scanf("%lld", &n);
	ll sum = 0;
	for (int i = 1; i <= n; ++i)scanf("%lld", &a[i]), sum += a[i];
	if (!mp.count(sum)) {
		puts("NO");
		return ;
	} 
	
	int last = 0;
	int st = mp[sum];
	for (int i = st; i >= 0; --i) {
		int id = -1;
		for (int j = 1; j <= n; ++j)
			if (j != last) if (id == -1 || a[id] < a[j]) id = j;
		if (id == -1 || a[id] < fib[i]) {
			puts("NO");
			return ;
		}
		a[id] -= fib[i];
		last = id;
	}
	puts("YES");
}

int main()
{
	fib[0] = fib[1] = 1;
	mp[1] = 0, mp[2] = 1;
	ll sum = 2;
	for (int i = 2; i <= 43; ++i) {
		fib[i] = fib[i - 1] + fib[i - 2];
		sum += fib[i];
		mp[sum] = i;
	}
	
	int T = 1;
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		solve();
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54