【HDOJ6616】Divide the Stones（构造）

题意：给定n堆石子，第i堆的个数为i，要求构造出一种方案将其分成k堆，使得这k堆每堆数量之和相等且堆数相等

保证k是n的一个约数

n<=1e5

思路：先把非法的情况判掉

n/k为偶数的方法及其简单

n/k为奇数就先构造出n=3k的情况然后减掉，剩下的就是n/k为偶数

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 //typedef pair<ll,ll>P;
 11 #define N  1000010
 12 #define M  200010
 13 #define fi first
 14 #define se second
 15 #define MP make_pair
 16 #define pb push_back
 17 #define pi acos(-1)
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 20 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 21 #define lowbit(x) x&(-x)
 22 #define Rand (rand()*(1<<16)+rand())
 23 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 24 #define ls p<<1
 25 #define rs p<<1|1
 26 
 27 const int MOD=1e9+7,inv2=(MOD+1)/2;
 28       double eps=1e-4;
 29       int INF=1e9;
 30       int inf=0x7fffffff;
 31       int dx[4]={-1,1,0,0};
 32       int dy[4]={0,0,-1,1};
 33 
 34 VI c[N];
 35 
 36 int read()
 37 {
 38    int v=0,f=1;
 39    char c=getchar();
 40    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 41    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 42    return v*f;
 43 }
 44 
 45 int main()
 46 {
 47     int cas=read();
 48     while(cas--)
 49     {
 50         int n=read(),k=read();
 51         ll s=1ll*n*(n+1)/2;
 52         if(s%k>0||k==n&&k>1)
 53         {
 54             printf("no
");
 55             continue;
 56         }
 57         printf("yes
");
 58         if(n==1&&k==1)
 59         {
 60             printf("1
");
 61             continue;
 62         }
 63         int t=n/k;
 64         rep(i,1,k) c[i].clear();
 65         if(t>=3&&t%2==1)
 66         {
 67             int x=k/2,m=n;
 68             rep(i,1,k)
 69             {
 70                 c[i].pb(m);
 71                 m--;
 72             }
 73             rep(i,x+1,k)
 74             {
 75                 c[i].pb(m);
 76                 m--;
 77             }
 78             rep(i,1,x)
 79             {
 80                 c[i].pb(m);
 81                 m--;
 82             }
 83             int y=m;
 84             per(i,k,x+1)
 85             {
 86                 c[i].pb(m);
 87                 m-=2;
 88             }
 89             m=y-1;
 90             per(i,x,1)
 91             {
 92                 c[i].pb(m);
 93                 m-=2;
 94             }
 95             n-=3*k;
 96         }
 97         t=0;
 98         rep(i,1,n/2)
 99         {
100             t++;
101             if(t==k+1) t=1;
102             c[t].pb(i);
103         }
104         t=0;
105         per(i,n,n/2+1)
106         {
107             t++;
108             if(t==k+1) t=1;
109             c[t].pb(i);
110         }
111 
112         rep(i,1,k)
113         {
114             rep(j,0,(int)c[i].size()-1) printf("%d ",c[i][j]);
115             printf("
");
116         }
117     }
118     return 0;
119 }