CodeForces - 553B (数学题

题意：把一个排列表示成若干环，这些环内的元素逆序排列，各个环以最大元素为关键字顺序排列，求使排列的环表示和原排列一样的第k个排列。

思路：斐波那契数列，因为必须是两位相邻，所以输出也不难。

复制代码#include<iostream> #include<map> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<functional> #define pb push_back using namespace std; typedef long long ll; const int maxv=1005; const ll mod=1e9+7; ll fei[60]; vector<int> getans(int n,int add,ll k){ vector<int> ans,ans2; if(n<=0) return ans; if(fei[n-1]>=k){ ans.pb(1+add); ans2=getans(n-1,add+1,k); }else{ ans.pb(2+add);ans.pb(1+add); ans2=getans(n-2,add+2,k-fei[n-1]); } for(int i=0;i<ans2.size();i++) ans.pb(ans2[i]); return ans; } ll n,k; int main(){ freopen("/home/files/CppFiles/in","r",stdin); fei[0]=fei[1]=1; for(int i=2;i<55;i++) fei[i]=fei[i-1]+fei[i-2]; while(cin>>n>>k){ vector<int> out=getans(n,0,k); for(int i=0;i<out.size();i++){ cout<<out[i]<<" "; } cout<<endl; } 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
#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<functional>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxv=1005;
const ll mod=1e9+7;
ll fei[60];
vector<int> getans(int n,int add,ll k){
vector<int> ans,ans2;
if(n<=0) return ans;
if(fei[n-1]>=k){
ans.pb(1+add);
ans2=getans(n-1,add+1,k);
}else{
ans.pb(2+add);ans.pb(1+add);
ans2=getans(n-2,add+2,k-fei[n-1]);
}
for(int i=0;i<ans2.size();i++) ans.pb(ans2[i]);
return ans;
}
ll n,k;
int main(){
freopen("/home/files/CppFiles/in","r",stdin);
fei[0]=fei[1]=1;
for(int i=2;i<55;i++) fei[i]=fei[i-1]+fei[i-2];
while(cin>>n>>k){
vector<int> out=getans(n,0,k);
for(int i=0;i<out.size();i++){
cout<<out[i]<<" ";
}
cout<<endl;
}
return 0;
}