CF 459C

标签:strong   efi   tmp   tor   iostream   color   fine   i++   进制   

做过一点点构造题,花了一个小时想怎么构造,但并没有什么用,写起来感觉有点复杂。

标程分析:

对于输出结果,共d次分配情况。而对于每个学生而言,每个人有d次选择乘坐车辆的机会。

那么所有同学在k辆车,d轮下的选车情况共有k的d次方种选法。

仔细想一想,如果学生的数量超过了上述选法种数,根据鸽巢原理,必有重复的情况产生,此时则不符合题意。

其余情况,对于全排列中的n项,我们只需要选取k进制下的前n个数字输出结果即可。

竖着看输出样例。

 1 #include<iostream>  2 #include<algorithm>  3 #include<vector>  4 #include<cstdio>  5 #define ll long long  6 using namespace std;  7  8 int n, k, d;  9 //n为总人数,k为大巴数量,d为操作次数 10 int res[1010][1010]; 11 void solve() 12 { 13 for(int i = 1 ; i < n ; i++){ 14 for(int j = 0 ; j < d ; j++){ 15 res[j][i] = res[j][i - 1]; 16  } 17 for(int j = d - 1 ; j >= 0 ; j--){ 18 res[j][i] = (res[j][i] + 1) % k; 19 if(res[j][i]) break; 20  } 21  } 22 23 for(int i = 0 ; i < d ; i++){ 24 for(int j = 0 ; j < n ; j++){ 25 printf("%d ",res[i][j] + 1); 26  } 27 printf("\n"); 28  } 29 } 30 31 int main(){ 32 scanf("%d%d%d",&n,&k,&d); 33 ll tmp = 1; 34 for(int i = 1 ; i <= d ; i++){ 35 tmp *= k; 36 if(tmp >= n) break; 37  } 38 if(tmp < n){ 39 printf("-1\n"); 40 return 0; 41  } 42 if(n <= k){ 43 for(int i = 1 ; i <= d ; i++){ 44 for(int j = 1 ; j <= n ; j++){ 45 printf("%d ",j); 46  } 47 printf("\n"); 48  } 49 return 0; 50 }else{ 51  solve(); 52  } 53 54 return 0; 55 }

 

CF 459C

标签:strong   efi   tmp   tor   iostream   color   fine   i++   进制   

原文地址:https://www.cnblogs.com/ecustlegendn324/p/13816843.html

版权声明:完美者 发表于 2020-11-02 9:42:40。
转载请注明:CF 459C | 完美导航

暂无评论

暂无评论...