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

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

阅读量：5010 次

发布时间：2019-06-12

本文共 2249 字，大约阅读时间需要 7 分钟。

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

Recommend

chendu | We have carefully selected several similar problems for you:

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

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

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

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                const int maxn=1e5+5;typedef long long ll;using namespace std;vector
                
                 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
                 
                  =1; t--) { vec[t].push_back(cnt++); } } } for(int t=1; t<=k; t++) { for(int j=0; j

转载于:https://www.cnblogs.com/Staceyacm/p/11280622.html

你可能感兴趣的文章