Codeforces 459C Pashmak and Buses 机智数学题

这个题目说的是有n个人，有k辆巴士，有m天，每天都要安排n个人坐巴士（可以有巴士为空），为了使得这n个人不会成为朋友，只要每两个人在这m天里坐的巴士至少一天不相同即可。

要你求是否有这样的安排方法，如果有，输出具体的安排方案，每个人每天坐那辆车。

挺不错的题目，我压根没想到。。真的，虽然知道之后惊呼原来如此简单，但一开始确实想岔了。现在一看这题目，很清晰，每个学生在这m天中坐的车辆，就会形成一个由m个数字组成的序列（数字为1-k代表巴士编号），按照题目要求，只需要学生的那个序列是独一无二的即可。

那么，我们只要把题意转化为求n个不同的m个数字组成的序列（只要有一个数字不同即为不同），那么我们把这个序列，认为是一个 m位的k进制的数不就行了，每次从111111.。

开始枚举，一直枚举到kkkkkk。。。结束啊啊。。。哎，真的很机智的题诶

当然一开始可以直接乘一下判断m个k进制的数是否>=n，不满足直接输出-1，满足就用类似高精度加法把序列求出来再输出即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define LL __int64

using namespace std;

LL n,k,d;

int ans[][];

int main()

{

    while (scanf("%I64d%I64d%I64d",&n,&k,&d)!=EOF)

    {

        LL tmp=k;

        for (LL i=;i<=d;i++){

            tmp=tmp*k;

            if (tmp>=n) break;

        }

        if (tmp<n){

            puts("-1");

            continue;

        }

        for (int i=d;i>=;i--) ans[][i]=;

        ans[][d]=;

        for (int i=;i<=n;i++){

            int c=;

            ans[i][d]=ans[i-][d]+;

            if (ans[i][d]>k){ans[i][d]=;c++;}

            for (int j=d-;j>=;j--){

                ans[i][j]=ans[i-][j]+c;

                if (ans[i][j]>k){

                    c=;

                    ans[i][j]=;

                }

                else c=;

            }

        }

        for (int i=;i<=d;i++){

            printf("%d",ans[][i]);

            for (int j=;j<=n;j++){

                printf(" %d",ans[j][i]);

            }

            puts("");

        }

    }

    return ;

}

巴特西

Codeforces 459C Pashmak and Buses 机智数学题

最新文章

热门文章