列表

详情

NC51210. A decorative fence

描述

Richard just finished building his new house. Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME Fence Catalogue 2002, the ultimate resource on cute little wooden fences. After reading its preface he already knew, what makes a little wooden fence cute. 
A wooden fence consists of N wooden planks, placed vertically in a row next to each other. A fence looks cute if and only if the following conditions are met: 
It follows, that we may uniquely describe each cute fence with N planks as a permutation of the numbers such that and vice versa, each such permutation describes a cute fence.
It is obvious, that there are many di erent cute wooden fences made of N planks. To bring some order into their catalogue, the sales manager of ACME decided to order them in the following way: Fence A (represented by the permutation a_1, . . . , a_N) is in the catalogue before fence B (represented by b_1, . . . , b_N) if and only if there exists such i, that (any j < i) and . (Also to decide, which of the two fences is earlier in the catalogue, take their corresponding permutations, find the first place on which they differ and compare the values on this place.) All the cute fences with N planks are numbered (starting from 1) in the order they appear in the catalogue. This number is called their catalogue number.

After carefully examining all the cute little wooden fences, Richard decided to order some of them. For each of them he noted the number of its planks and its catalogue number. Later, as he met his friends, he wanted to show them the fences he ordered, but he lost the catalogue somewhere. The only thing he has got are his notes. Please help him find out, how will his fences look like.

输入描述

The first line of the input file contains the number  of input data sets. K lines follow, each of them describes one input data set. 
Each of the following K lines contains two integers N and , separated by a space. N is the number of planks in the fence, C is the catalogue number of the fence. 
You may assume, that the total number of cute little wooden fences with 20 planks fits into a 64-bit signed integer variable (long long in C/C++, int64 in FreePascal). You may also assume that the input is correct, in particular that C is at least 1 and it doesn抰 exceed the number of cute fences with N planks.

输出描述

For each input data set output one line, describing the C-th fence with N planks in the catalogue. More precisely, if the fence is described by the permutation , then the corresponding line of the output file should contain the numbers ai (in the correct order), separated by single spaces.

示例1

输入: 

2
2 1
3 3

输出: 

1 2
2 3 1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 348K, 提交时间: 2022-08-12 19:51:11 

#include<stdio.h>
#define int long long
const int N=20+3;
int f[N][N][2];
bool vis[N];
void dp(int n=20)
{
	f[1][1][1]=f[1][1][0]=1;
	for (int i=2;i<=n;i++)
	  {
	  	 f[i][i][0]=0;
	  	 for (int j=i-1;j>=1;j--)
		   f[i][j][0]=f[i][j+1][0]+f[i-1][j][1]; 
		 f[i][1][1]=0;
		 for (int j=2;j<=i;j++)
		   f[i][j][1]=f[i][j-1][1]+f[i-1][j-1][0];
	  }
}
signed main()
{
	dp();
	int t; scanf("%lld",&t);
	while (t--)
	  {
	  	 int n,num; scanf("%lld%lld",&n,&num);
	  	 num--;
	  	 for (int i=1;i<=n;i++) vis[i]=false;
	  	 vis[0]=true;
	  	 int last;
	  	 for (int i=1;i<=n;i++)
	  	   if (num>=f[n][i][0]+f[n][i][1])
	  	     num-=f[n][i][0]+f[n][i][1];
	  	   else
	  	   	 {
	  	   	    vis[i]=true; printf("%lld",i);
	  	   	    last=i; break;
			 }
		 bool p; 
		 for (int i=2;i<n;i++)
		   {
		   	  bool flag=false; int count=0;
		   	  for (int j=1;j<=n;j++)
		   	    {
		   	       if (vis[j-1]) continue;
		   	       count++;
		   	       if (i^2) 
		   	         {
		   	            if (p)
		   	              if (last<j-1) continue;
		   	            if (!p)
		   	              if (last>j-1) continue;
				     }
				   int add=j-1>last?f[n-i+1][count][1]:f[n-i+1][count][0];
				   if (num>=add) num-=add;
				   else
				     {
				        vis[j-1]=true; printf(" %lld",j-1);
	  	   	            p=(last<j-1); last=j-1; flag=true;
					    break;
					 }
			    }
			  if (!flag) 
			    {
			       vis[n]=true; printf(" %lld",n);
	  	   	       p=(last<n); last=n;
				}
		   }
		 for (int i=1;i<=n;i++)
		   if (!vis[i]) {printf(" %lld",i);break;}
		 printf("\n");
	  }
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 476K, 提交时间: 2020-03-15 17:01:09 

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

ll dp[32][32][2];

int main() {
    ios::sync_with_stdio(0);
	int T; cin>>T;
	dp[1][1][0] = dp[1][1][1] = 1;
	for(int i=2;i<=20;i++) {
		for(int j=1;j<=i;j++) {
			for(int p=j;p<i;p++) {
				dp[i][j][0] += dp[i-1][p][1];
			}
			for(int p=1;p<j;p++) {
				dp[i][j][1] += dp[i-1][p][0];
			}
		}
	}
	while(T--) {
		ll n,m;
		cin>>n>>m;
		vector<int> used(n+1);
		int now,o;
		for(int i=1;i<=n;i++) {
			o = i;
			if(dp[n][i][1]>=m) {
				now = 1;
				break;
			}else m -=  dp[n][i][1];

			if(dp[n][i][0]>=m) {
				now = 0;
				break;
			}else m -= dp[n][i][0];
		}
		used[o] = 1;
		cout<<o;

		int len = n-1;
		for(int i=2;i<=n;i++) {
			now ^= 1;
			for(int p=1,j=0;p<=n;p++) {
				if(used[p]) continue;
				j++;
				if( (now==0 && p<o) || (now==1 && p>o)) {
					if(dp[len][j][now]>=m) {
						o = p;
						break;
					}else m -= dp[len][j][now];
				}
			}
			used[o] = 1;
			cout<<" "<<o;
			len--;
		}
		cout<<endl;
	}
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 404K, 提交时间: 2022-02-06 10:43:44 

#include<bits/stdc++.h>
using namespace std;
long long k,up[21][21],down[21][21],t,n,s[21];
void get(){
	int fup,v=0;
	for(int i=1;i<=n;i++)s[i]=i;
	for(int i=n;i;i--){
		if(i==n){
			for(int j=1;j<=n;j++){
				if(k<=down[j][i]){v=j;fup=0;break;}
				k-=down[j][i];
				if(k<=up[j][i]){v=j;fup=1;break;}
				k-=up[j][i];
			}
		}
		else{
			if(fup)for(int j=v;j<=i;j++){if(k<=down[j][i]){v=j;break;}k-=down[j][i];}
			else for(int j=1;j<v;j++){if(k<=up[j][i]){v=j;break;}k-=up[j][i];}
			fup^=1;
		}
		cout<<s[v]<<" ";
		for(int j=v;j<i;j++)s[j]=s[j+1];
	}
	cout<<"\n";
}
int main(){
	down[1][1]=1;
	for(int i=1;i<21;i++){for(int j=2;j<=i;j++)down[j][i]=down[j-1][i]+up[j-1][i-1];for(int j=1;j<=i;j++)up[j][i]=down[i-j+1][i];}
	cin>>t;
	while(t--)cin>>n>>k,get();
	return 0;
}

上一题

© 2024 nowcoder.com