HDU 6628

发布时间：2020-12-13 21:30:51 所属栏目：PHP教程来源：网络整理

导读：题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6628 此题不难看出，n8，第一位一定是n，后面的排序可以找规律得出；n=8，暴力得出。但看题解后，我发现可以直接对差值排序，然后进行暴力。 1 #includecstdio 2 #includeiostream 3 using namespace

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6628

此题不难看出，n>8，第一位一定是n，后面的排序可以找规律得出；n<=8，暴力得出。

但看题解后，我发现可以直接对差值排序，然后进行暴力。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define ll long long
 5 ll sum[22];
 6 int ans[22],vis[22];
 7 int n,k;
 8 /*
 9 void Dfs(int id){
10     if(id==n){
11         for(int i = 0;i < n;i++){
12             if(i) printf(" ");
13             printf("%d",ans[i]);
14         }
15         cout<<endl;
16     }
17     for(int i = 1;i <= n;i++){
18         if(vis[i]) continue;
19         vis[i] = 1;
20         ans[id] = i;
21         dfs(id+1);
22         vis[i] = 0;
23     }
24 }*/
25 int dfs(int id,int low,int high){
26     if(id==n){
27         k--;
28         if(!k){
29             for(int i = 0;i < n;i++){
30                 if(i) printf(" ");
31                 printf("%d",ans[i]-low+1);
32             }
33             printf("n");
34             return 1;
35         }
36         return 0;
37     }
38     for(int i = high-n+1;i <= low+n-1;i++){
39         if(vis[i]) continue;
40         vis[i] = 1;
41         ans[id] = i;
42         if(dfs(id+1,min(low,i),max(high,i))){
43             vis[i] = 0;
44             return 1;
45         }
46         vis[i] = 0;
47     }
48     return 0;
49 }
50 int main()
51 {
52     int t;
53     scanf("%d",&t);
54     while(t--){
55         scanf("%d%d",&n,&k);
56         for(int i = 1;i <= n;i++) vis[i] = 0; 
57         //Dfs(0);
58         ans[0] = n;
59         vis[n] = 1;
60         dfs(1,n,n);
61         vis[n] = 0;
62     }
63     return 0;
64 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!