[2019杭电多校第四场][hdu6616]Divide the Stones

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6616

题意是说n个数分别为1-n，将n个数分成k堆，能否满足每堆个数相等，数值之和相等。保证n%k=0。

构造题神马的太烦了略略略

我的构造方式是这样的，先判断每堆的个数，然后分奇偶讨论一下

每堆个数为偶时：

可以将n个数分成n/2对，如n为12时，分成1-12,2-11,3-10,4-9,5-8,6-7这样。

然后根据每堆的个数将n/2对分别放入每堆中。

如n=12,k=3时：

第一堆为1-12,2-11。

第二堆为3-10,4-9。

第三堆为5-8,6-7。

这样很好想。

每堆个数为奇时：

先用蛇型方式构造出k堆的前m-2项(m为每堆的个数)

如n=15,k=3时：

1 6 7 X X

2 5 8 X X

3 4 9 X X

三堆分别如上。

然后发现每堆现在的和为14 15 16单调递增。所以我们用剩余元素构造出一个单调递减的序列即可。

剩余元素为10 11 12 13 14 15，我们用15-11,13-12,14-10，构造出一个递减序列即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         ll n, m, k;

         scanf("%lld%lld", &n, &k);

         m = n / k;

         ll sum = n * (n + ) / ;

         if (k == ) {

             printf("yes\n");

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

                 printf("%d%c", i, i == n ? '\n' : ' ');

         }

         else if (sum%k) {

             printf("no\n");

             continue;

         }

         else {

             if (m & ) {

                 int num = ;

                 int tot = sum / k;

                 int tmp = n;

                 printf("yes\n");

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

                     for (int j = ; j <= m - ; j++) {

                         int x;

                         if (j & )

                             printf("%d ", x = (j - )*k + i);

                         else

                             printf("%d ", x = j * k - i + );

                         if (i == )

                             tot -= x;

                     }

                     printf("%d %d\n", tmp, tot - tmp);

                     tot--;

                     tmp -= ;

                     if (tmp < n - k)tmp = n - ;

                 }

             }

             else {

                 int cnt = ;

                 printf("yes\n");

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

                     cnt += ;

                     printf("%d %d", i, n - i + );

                     if (cnt == m) {

                         printf("\n");

                         cnt = ;

                     }

                     else

                         printf(" ");

                 }

             }

         }

     }

 }

巴特西

[2019杭电多校第四场][hdu6616]Divide the Stones

最新文章

热门文章