当前位置: 首页 > news >正文

与斐波那契数列相关的对换题目 CF553B Kyoya and Permutation

定义标准循环表示法
即,对于每个循环,都将其最大值放在最前面,然后将这若干个循环按照最大值从小到大排列。这样,\([4,1,6,2,5,3]\)
标准循环表示法就是
\((4 2 1)(5)(6 3)\)

定义好的排列:原排列和标准循环表示一致

寻找第k个字段序的好的排列

此题手玩n=4的样例可以发现:
“好的排列”只能由1..n的顺序排列通过以下操作得来:

在原排列上,选择若干个不相交的,长度为2的区间,然后翻转每个区间。
这个性质瞪眼法有点难瞪
长度为 n 的序列最多有几个好的排列?
n只能与n-1翻转,于是,对于一个排列,n要么和n-1翻转,要么不翻转
n和n-1翻转的话,即 \(f(n)+=f(n-2)\)
n不翻转的话,即 \(f(n)+=f(n-1)\)

这就是一个斐波那契的式子!
\(f(n) = f(n-1)+f(n-2)\)

然后我们递归的填数字就好了,递归写起来很简单,只是有点难想

#include<iostream>
#include<vector>
using namespace std;
#define ffp(x,y,z) for(ll (x)=(y);(x)<=(z);(x++))
#define ll long long int
#define q_ read()
inline ll read()
{ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();return x * f;
}void solve()
{ll n = q_;ll k = q_;vector<ll>fb(n + 2, 0);vector<int>num(n + 2, 0);fb[2] = fb[1] = 1;ffp(i, 3, n)fb[i] = fb[i - 1] + fb[i - 2];auto bud = [&](auto&& bud, int l,int r, ll nk)->void{if (l > r) { return; }if (l == r){num[l] = l;return;}int len = r - l + 1;//需要构造一个长度为len的,值为nk的数列if (nk <= fb[len])//可以放进len里面{num[l] = l;bud(bud, l + 1, r, nk);//把下面的全部翻转,然后翻转当前这个}else//太大了,需要翻转{num[l] = l+1;num[l + 1] = l;bud(bud, l + 2, r, nk - fb[len]);}};bud(bud, 1, n, k);ffp(i, 1, n)cout << num[i] << " \n"[i == n];
}int main()
{int t = 1;while (t--){solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=25049

相关文章:

  • wpf .net 8 使用mvvm指南
  • office办公软件
  • 2025.10.4训练记录
  • st表 + 变形的djs (好题
  • 2025年微信小程序开发:AR/VR与电商的最新案例 - 指南
  • 10.5
  • 在wpf .net 8项目中使用materialDesign 4 以上版本的的注意事项
  • 学习STC51单片机26(芯片为STC89C52RCRC) - 实践
  • 洛谷P14120 题解 - lemon
  • cf41d
  • 33 ACwing 294 Count The Repetitions 题解
  • 电赛电装实习总结
  • 30 ACwing 291 蒙德里安的梦想 题解
  • 21 ACwing 289 环路运输 题解
  • 26 UVA1630 串折叠 Folding 题解
  • 13 ACwing 283 Polygon 题解
  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板