Anti-Fibonacci Permutation 题解

原题链接：Link

题目简介

简单来说，如果在一个序列 \(A\) 中，对于每一个 \(i > 2\) ，都有 \(A_i \ne A_{i-1}+A_{i-2}\) ，那么 \(A\) 被称为反斐波那契数列。就是不符合斐波那契数列要求的数列。题目要求构造出 \(n\) 个这样的数列，每一个数都要在 \(1 \sim n\) 之间。

构造思路

显然枚举全排列然后每次都 \(O(n)\) 判一遍是可行的，但是最好不要自己写全排列，容易 \(T\) 。建议使用 STL 的 next_permutation() 函数（用法可以百度）。可以知道这样的最坏复杂度是 \(O(n^2)\) 的，因为 next_permutation() 的复杂度最坏是 \(O(n)\) 。不过我们有更好的方法。

考虑序列 \(A=\{ n, n-1, n-2,...,2, 1 \}\) ，它一定是反斐波那契数列。因为 \(A_i\) 显然比 \(A_{n-1}\) 和 \(A_{n-2}\) 更小。然后我们考虑把最后一个数放到第一个，即 \(A'=\{1,n,n-1,...,3,2\}\) ，它也是一个反斐波那契数列，因为 \(n-1 < n+1\) ，然后构造 \(A''=\{2,1,n,n-1,...,4,3\}\) ，这里有一个小小的曲折：如果 \(n=2+1=3\) ，那么它就不是反斐波那契数列，但不用担心，特判 \(n=3\) 之后把样例输出就可以了。对于其他的 \(n\) ， \(A''\) 显然也是反斐波那契数列。之后的构造就顺风顺水，重复把最后一个数放到第一个的操作，可以知道所得 \(n\) 个序列都是反斐波那契数列，就有答案了。证明如下：

对于构造的第 \(i\) 个数列，一定符合 \(i-1,i-2,i-3,...,2,1,n,n-1,...,i+1,i\) 的形式。由之前构造的 \(A\) 数列，可以知道递减序列一定是反斐波那契数列，那么只要 \(2,1,n,n-1\) 这一段两个递减序列接合的地方满足要求即可。又由 \(A''\) 的构造中知道，当 \(n>3\) 时，接合处也满足要求，所以第 \(i\) 个数列一定是反斐波那契数列。

时间复杂度 \(O(n)\) 。

AC代码

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

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

int t, n;

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		if (n == 3) {
			printf("3 2 1\n1 3 2\n3 1 2\n");
			continue;
		}
		for (int s = n; s >= 1; s--) {
			int cnt = n, i = s;
			while (cnt--) {
				printf("%d ", i);
				i--;
				if (i == 0) i = n;
			}
			putchar('\n');
		}
	}
	return 0;
}