翻译已交,直接上正解。
Solution
显然,直接 dfs 生成排列-测试会超时。
想到可以在 dfs 过程中进行测试(判断下一个放置的数字是否满足反斐波那契序列的条件)。
于是代码就长这样:
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
| #include<bits/stdc++.h> using namespace std; int n; bool flag[10001]; int ans[10001]; int tot;
void dfs(int now) { if(now==n+1) { tot++; for(int i=1;i<=n;i++) cout<<ans[i]<<" "; puts(""); } for(int i=1;i<=n;i++) if(!flag[i]&&(now==1||now==2||ans[now-2]+ans[now-1]!=i)) { flag[i]=true; ans[now]=i; dfs(now+1); if(tot==n) return; flag[i]=false; } }
int main() { int t; cin>>t; while(t--) { tot=0; memset(flag,0,sizeof(flag)); cin>>n; dfs(1); } }
|
46ms,AC。
But,你认为这就结束了吗?
Solution++
以上方法时间复杂度玄学(不想算,反正有 ,系数还蛮大),但通过数学分析可以降至裸 。并且代码量少很多
将排列降序。任意选择第 位数,那么这个数就是 。向前数两个数,分别是 和 。显然,。
将前两个数字相加,关于 的方程 的解为 。
![](https://cdn.luogu.com.cn/upload/image_hosting/d8niqm9c.png)
若不是反斐波那契数列,就应该满足 。与 相矛盾。说明逆序排列是反斐波那契数列。
那么,如果我们调换一下前后相邻的两个数的顺序?
那么,序列就会变成:
$$
(n-i+4),(n-i+3),(n-i+1),(n-i+2),(n-i+0),(n-i-1)
$$
事实上,可能没有 ,但没有可以不用管这个数字了,所以不会有问题。
如果有的话,调换顺序会波及到这些数字。
一一列出方程,解就完事了!
,不成立。
,不成立。
,不成立。
(想必你能猜到是这个吧),不成立。
都不成立,说明在倒序的基础上对调数字,都满足反斐波那契数列。
所以,总共可以调转 次,加上原来的逆序 次,就有 次了。
满足了题目条件。
这也就为什么题目上会有 的原因吧。
附:中间为什么会有一个 的解呢?
理性的认识,中间的两个数对调,移项了,所以有两点贡献,相比逆序的解应该少 。
这下,其他的解为 应该也不难理解了吧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include<bits/stdc++.h> using namespace std;
int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int j=n;j>=1;j--) printf("%d ",j);puts(""); for(int i=n;i>=2;i--) { for(int j=n;j>=1;j--) { if(j==i) printf("%d %d ",j-1,j),j--; else printf("%d ",j); } puts(""); } } return 0; }
|
Solution+
事实上,这道题有许多方法,最终原理就是 逆序排列永远满足反斐波那契数列。
方法1
逆序后,将任意一个数提前,也是 种。
方法2
逆序后,调换间隔一个数的两个数。(猜测)
附上 Translate。
Translate
反斐波那契数列(anti-Fibonacci)定义为 的排列中不满足 的排列。
输入 数据,每组数据给定序列长度 。
对于每组数据,只需任意输出 个长度为 的反斐波那契数列。每行一个序列,用空格分隔。(不允许输出多个相同的序列。易证长度为 的反斐波那契数列数量必定大于等于 。)
其中 。