标签: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
暂无评论...