HDU多校1003-Divide the Stones(构造)

Problem Description

There are n stones numbered from 1 to n.
The weight of the i-th stone is i kilograms. We divide the stones into k groups.
Each group consists of exactly stones.
We define the weight of each group is sum of the stones’ weights in the group.
Can we divide the stones so that the weights of all groups are same?

Input

The first line of input contains an integer T (1 <= T <= 100) denoting the number of test cases.
Each test case consists of one line containing two integers n (1 ≤ n ≤ 100000), k (k is divisor of n).
It is guaranteed that the sum of n overall test cases does not exceed 500000.

Output

For each test case, if you can’t divide into k groups satisfying condition, print “no”.
Else if you can divide into k groups satisfying condition, print “yes” in one line and then print k lines.
The i-th line represent the indices of stones belonging to the i-th group.
If there are multiple solutions, you can print any of them.

Sample Input

1 4 2

Sample Output

yes 1 4 2 3

Source

2019 Multi-University Training Contest 4

Recommend

chendu | We have carefully selected several similar problems for you: 6623 6622 6621 6620 6619

这个题先用求和公式对（1——n）求和然后判断是否能进行整分，不行就输出no 可以就输出yes

对于打印的时候怎么构造是要分情况讨论的若n/k是偶数则按列进行蛇皮填若n/k是奇数要单独处理前两列后面进行蛇皮排但也是前两列是这个题的难点

前两列你要实现把 1----2k个数都用上并且保证每行之和能够递增+1 这时候我们可以通过等差数列的性质然后求出第一行的值然后赋值为 1 和另一个可以求出来的数然后前者+（k/2+1） -（k/2）...... 后者-（k/2）+（k/2+1）.....就把这个题的构造实现了

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#include<cmath>
const int maxn=1e5+5;

typedef long long ll;
using namespace std;
vector<int>vec[maxn];
int vis[maxn];
int main()
{
    int T;
    cin>>T;
    ll n,k;
    while(T--)
    {
        scanf("%lld%lld",&n,&k);
        ll  sum=(n*(n+1)/2);
        for(int t=1; t<=k; t++)
        {
            vec[t].clear();
        }
        memset(vis,0,sizeof(vis));
        if(sum%k!=0)
        {
            puts("no");
        }
        else
        {
            if((n/k)%2==0)
            {
                puts("yes");
                int cnt=1;
                for(int j=1; j<=n/k; j++)
                {
                    if(j%2==1)
                    {
                        for(int t=1; t<=k; t++)
                        {
                            vec[t].push_back(cnt++);
                        }
                    }
                    else
                    {
                        for(int t=k; t>=1; t--)
                        {
                            vec[t].push_back(cnt++);
                        }
                    }
                }
                for(int t=1; t<=k; t++)
                {
                    for(int j=0; j<vec[t].size(); j++)
                    {
                        if(j!=vec[t].size()-1)
                            printf("%d ",vec[t][j]);
                        else
                        {
                            printf("%d",vec[t][j]);
                        }
                    }
                    printf("\n");
                }
            }
            else
            {
                puts("yes");
                if(n==1)
                {
                    puts("1");
                    continue;
                }
                ll kk=(3*k+3)/2;
                ll ss=k/2+1;
                
                int cnt=1;
                vec[1].push_back(cnt);
                vec[1].push_back(kk-cnt);
                int cnt1=cnt;
                int cnt2=kk-cnt;
                for(int t=2;t<=k;t++)
                {
                    if(t%2==0)
                    {
                    int temp1=cnt1+ss,temp2=cnt2-abs(k-ss);
                    vec[t].push_back(temp1);
                    vec[t].push_back(temp2);
                    cnt1=temp1;
                    cnt2=temp2;
                    }
                    else
                    {
                    int temp1=cnt1-abs(k-ss),temp2=cnt2+ss;
                    vec[t].push_back(temp1);
                    vec[t].push_back(temp2);
                    cnt1=temp1;
                    cnt2=temp2;
                    }
                    
                }
                cnt=2*k+1;
                for(int j=1; j<=n/k-2; j++)
                {
                    if(j%2==0)
                    {
                        for(int t=1; t<=k; t++)
                        {
                            vec[t].push_back(cnt++);
                        }
                    }
                    else
                    {
                        for(int t=k; t>=1; t--)
                        {
                            vec[t].push_back(cnt++);
                        }
                    }
                }
                for(int t=1; t<=k; t++)
                {
                    for(int j=0; j<vec[t].size(); j++)
                    {
                        if(j!=vec[t].size()-1)
                            printf("%d ",vec[t][j]);
                        else
                        {
                            printf("%d",vec[t][j]);
                        }
                    }
                    printf("\n");
                }
            }
        }
    }
    return 0;
}

HDU多校1003-Divide the Stones(构造)

推荐阅读