codeforces 459C - Pashmak and Buses 【构造题】

妖狐艹你老母 2022-08-11 03:29 81阅读 0赞

题目：[codeforces 459C - Pashmak and Buses][]

题意：给出n个人，然后k辆车，d天时间，然后每天让n个人选择坐一辆车去上学，要去d天不能有任意两个人乘同一辆车，不能的话输出 -1

分类：数学，构造

分析：这个题目首先得分析，我开始想到的是首先用相同的放在一起，比如 7 2 3

这样构造 1 1 1 1 2 2 2

1 1 1 2 2 2 1

1 1 2 2 2 1 1

1 2 2 2 1 1 1

就是需要的天数跟每一行出现次数最多的数的出现次数相等，但是发现还有更优的方法，可以找到最多次数-1的方案

这样构造1 2 1 2 1 2 1

1 1 2 2 1 1 2

1 1 1 1 2 2 2

那么是怎样得到的呢？

这其实可以用构造数的原理，我们把每一列从下往上看成一个 k 进制的长度为 d 的数，然后构造这样的 n 个数就好了，其实很简单，直接从0开始枚举到n-1，然后每个数+1，就是结果。

那么判断不满足条件的就很简单了，k^d < n 的话，肯定没办法构造出来，注意会超int

当然可以用深搜来枚举所有可能的情况，来构造，方法差不多

代码：python

n,k,d = map(int,raw_input().split())
    if(n> k**d):
        print -1
    else:
        ans = []
        for  i in range(n):
            tmp = i;
            cur = []
            for j in range(d):
                cur.append(tmp%k+1)
                tmp/=k
            ans.append(cur)
        for i in range(d):
            for j in ans:
                print j[i], #没有换行输出
            print ('\n')

c++

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <queue>
    #include <stack>
    #include <map>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <set>
    #include <utility>
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 1200;
    using namespace std;
    int a[N][N];
    int main()
    {
        int n,k,d;
        while(~scanf("%d%d%d",&n,&k,&d))
        {
            if(double(n)>pow((double)k,d))
                printf("-1\n");
            else
            {
                Del(a,0);
                for(int st=0;st<n;st++)
                {
                    int tmp=st,j=0;
                    while(tmp)
                    {
                        a[j][st]=tmp%k;
                        tmp/=k;j++;
                    }
                }
                for(int i=0;i<d;i++)
                {
                    for(int j=0;j<n;j++)
                    {
                        printf("%d%c",a[i][j]+1,j==n?'\n':' ');
                    }
                    printf("\n");
                }
            }
        }
        return 0;
    }

[codeforces 459C - Pashmak and Buses]: http://codeforces.com/problemset/problem/459/C