codeforces 459C Pashmak and Buses 解题报告

题目链接：http://codeforces.com/problemset/problem/459/C

题目意思：有 n 个 students，k 辆 buses。问是否能对 n 个students安排每一天搭乘的buses，使得没有两个student 在 d 天搭乘相同的buses，buses 的 容量没有限制，也就是它可以搭无限多的人。

　　做这条题的时候，我是得不出无解的条件的，看了 tutorial 之后一下子明白了，就是 k^d > n。很容易理解，因为每一天某个student可以选择的 buses 都有 k 种选择嘛～～～而且又因为要输出 d 行 n 列 那么多的数，所以 k ^ d > n 表示至少有两列数会使得某两个student 成为 close friend！

知道这个之后就是如何构造答案了，其实就是所有排列情况，不过我是不会做啦～～～看了作者的代码自己重新写，非常惊叹他的智慧呀～～～

拿这组数据来说吧，20   3   5

结合代码中注释为transfer

　　ans[i][j] = ans[i-1][j];  表示从左边那一列复制到下一列，那么为了不使得两个student成为close friend 就势必要使得他们有一点不同，这时就用到代码中的 update 操作了

ans[i][j] = (ans[i][j] + 1) % k;

这行代码用得相当巧妙，由于循环是从 d-1 ——> 0 的，也就是对于当前处理的那一列，从下往上更改（如果遇到 % k == 0 的情况），否则（% k != 0）就在上一列的对应行 + 1。

最后还有一个地方，在判断 k^d > n 的时候，如果可以提早发现有answer，要提早 break 出来，从 test7 可以知道！考虑数据范围：1 ≤ n, d ≤ 1000; 1 ≤ k ≤ 10^9 ，因为乘的时候有可能很大，超出long long 范围 ！！

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int maxn =  + ;

 int ans[maxn][maxn];

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif

     int n, k, d;

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

     {

         bool flag = false;

         LL product = ;

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

         {

              product *= (LL)k;     // one select has k choice

              if (product >= n)      // mean has answer

              {

                  flag = true;

                  break;

              }

         }

         if (!flag)      // repeat, no answer

             printf("-1\n");

         else            // construct the answer

         {

             memset(ans, , sizeof(ans));

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

             {

                 for (int j = ; j < d; j++)

                 {

                     ans[i][j] = ans[i-][j];   // right transfer

                 }

                 for (int j = d-; j >= ; j--)   // update

                 {

                     ans[i][j] = (ans[i][j] + ) % k;

                     if (ans[i][j])

                         break;

                 }

             }

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

             {

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

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

                 printf("\n");

             }

         }

     }

     return ;

 }