本文主要是介绍Codeforces Round #261 (Div. 2) C,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
C. Pashmak and Buses
题意:有n个学生,k辆车,出去玩d天(也就是有d次乘车)。问是否可能任两个人至少一天没有乘坐相同的车。
思路:先自己造几组小数据人脑解一下,看看应该怎样安排。不难发现其实用k进制可以解,d位的k进制可以表示k^d个不同的值。每个值实际上代表了某个学生全部d天的乘车情况。
比如输入27 3 3,那么一组可能的解是:
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
纵向正好是三位三进制数按顺序排列(每位+1),表达了27个人3天的乘车情况,如果人数再多一个,就会撞了。解法异常地简洁。
不过这题如果你每次都用long long算k^d会爆掉,用double不精确,需要处理一下。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define INF 10000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010using namespace std; ll n,k,d;ll base(ll a,ll b){ll ans=1;while(b--){ans*=a;if(ans>n)return ans;}return ans;
}int main(){while(cin>>n>>k>>d){if(base(k,d)<n){cout<<"-1"<<endl;continue;}for(int dd=d-1;dd>=0;dd--){ll t=base(k,dd);for(int i=0;i<n;i++){cout<<(i/t)%k+1<<" ";}cout<<endl;}}return 0;
}
这篇关于Codeforces Round #261 (Div. 2) C的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!