点击打开链接
题意:n名学生,k辆bus,每个stu坐d次车,要求任意两个学生的乘车序列不能相同(顺序不同就算不同),输出可行方案 学生的乘车序列为:d天中乘坐bus的编号序列. n,d<=1e3,k<=1e9
有解:只要k种bus中选d个的排列数量>=n即可
法1: dfs暴力生成排列
法2:1111..~kkk.. 把排列看成d位(k+1)进制数 模拟高精度加法 生成前n个排列即可 O(nd)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+20; int n,k,d,num; int a[N],f[N][N];//f[i][j] 第i个学生,第j天坐的bus void Perm(int cur) { if(num>n) return;//生成n个排列 if(cur==d+1) { for(int i=1;i<=d;i++) f[num][i]=a[i]; num++; return; } //每个pos都有1~k种选法(n^d>n,小优化) for(int i=1;i<=min(n,k);i++) { a[cur]=i; if(num<=n) Perm(cur+1); } } int main() { while(cin>>n>>k>>d) { //k种选d个排列 ,每个位置有k个选法,总的为:k^d 首先判断是否>=n int cnt=1; bool flag=false; for(int i=1;i<=d;i++) { cnt=cnt*k; if(cnt>=n) { flag=true; break; } } if(flag) { num=1; //生成n个排列即可,O(nd)=1e6 Perm(1); for(int j=1;j<=d;j++) { for(int i=1;i<=n;i++) { printf("%d ",f[i][j]); } printf("\n"); } } else puts("-1"); } return 0; }#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pb push_back #define mp make_pair #define VAL(x) #x << " = " << (x) << " " #define SQR(a) ((a) * (a)) #define SZ(x) ((int) (x).size()) #define ALL(x) (x).begin(), (x).end() #define CLR(x, a) memset(x, a, sizeof x) #define FOREACH(i, x) for(__typeof((x).begin()) i = (x).begin(); i != (x).end(); i ++) #define FOR(i, n) for (int i = 0; i < (n); i ++) #define X first #define Y second const int MAXN = 1 * 1000 + 10; int ans[MAXN][MAXN]; int main () { ios::sync_with_stdio(false); int n, d, k; cin >> n >> k >> d; ll tmp = 1; bool check = false; for (int i = 0; i < d; i ++) { tmp *= k; if (tmp >= n) { check = true; break; } } if (!check) { cout << -1 << endl; return 0; } for (int i = 1; i < n; i ++) { for (int j = 0; j < d; j ++) ans[i][j] = ans[i - 1][j]; for (int j = d - 1; j >= 0; j --) { ans[i][j] = (ans[i][j] + 1) % k; if (ans[i][j]) break; } } for (int i = 0; i < d; i ++, cout << endl) for (int j = 0; j < n; j ++) cout << ans[j][i] + 1 << ' '; return 0; }
