首页 > 代码库 > Codeforces 459C Pashmak and Buses 机智数学题
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 __int64using namespace std;LL n,k,d;int ans[1010][1010];int main(){ while (scanf("%I64d%I64d%I64d",&n,&k,&d)!=EOF) { LL tmp=k; for (LL i=2;i<=d;i++){ tmp=tmp*k; if (tmp>=n) break; } if (tmp<n){ puts("-1"); continue; } for (int i=d;i>=1;i--) ans[0][i]=1; ans[0][d]=0; for (int i=1;i<=n;i++){ int c=0; ans[i][d]=ans[i-1][d]+1; if (ans[i][d]>k){ans[i][d]=1;c++;} for (int j=d-1;j>=1;j--){ ans[i][j]=ans[i-1][j]+c; if (ans[i][j]>k){ c=1; ans[i][j]=1; } else c=0; } } for (int i=1;i<=d;i++){ printf("%d",ans[1][i]); for (int j=2;j<=n;j++){ printf(" %d",ans[j][i]); } puts(""); } } return 0;}
Codeforces 459C Pashmak and Buses 机智数学题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。