凑出和相等的k组数,玄学结论——hdu6616

ゞ浴缸里的玫瑰 2023-10-11 09:10 11阅读 0赞

\[1,n\]n个数分成k组，每组n/k个，问k组数和相等的解决方案

首先(1+n)\*n/2判定一下是否可以被k整除

n/k为偶数时显然成立

n/k为奇数时每组数前三个很难配，我想了一种玄学的结论，也证明不出来为什么是对的。。

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 200005
    int n,k; 
    vector<int>G[maxn];
    pair<int,int>a[100005*5];
    int main(){
        int t;cin>>t;
        while(t--){
            scanf("%d%d",&n,&k);
            if(n==1){puts("yes");cout<<1<<endl;continue;}
            
            for(int i=1;i<=n;i++)G[i].clear();
            
            int tmp=n/k;//每组的个数 
            if(tmp%2==0){
                puts("yes");
                for(int i=1;i<=n;i+=2*k){
                    for(int j=i;j<=i+k-1;j++)
                        G[j-i+1].push_back(j);
                    for(int j=i+k;j<=i+2*k-1;j++)
                        G[k-(j-i-k)].push_back(j);
                }
                for(int i=1;i<=k;i++){
                    cout<<G[i][0];
                    for(int j=1;j<n/k;j++)
                        cout<<" "<<G[i][j];
                     puts("");
                }
            } 
            else {
        //最后还剩下三组配不出来 
                if(tmp==1 || k%2==0){puts("no");continue;}//每组一个或组数为偶数 
             
                 int step=k/2,p=1;
                 memset(a,0,sizeof a);
                 for(int i=1;i<=k;i++){
                     p+=step;
                     while(p>k)p-=k;
                    a[i+p+3*k]=make_pair(i+k,p+2*k);
                }
                int sum=(1+3*k)*3/2;
                 for(int i=1;i<=k;i++){
                     G[i].push_back(i);
                     pair<int,int>b=a[sum-i]; 
                     G[i].push_back(b.first);
                    G[i].push_back(b.second); 
                }
                 
                for(int i=3*k+1;i<=n;i+=2*k){
                    for(int j=i;j<=i+k-1;j++)
                        G[j-i+1].push_back(j);
                    for(int j=i+k;j<=i+2*k-1;j++)
                        G[k-(j-i-k)].push_back(j);
                } 
                puts("yes");
                for(int i=1;i<=k;i++){
                    cout<<G[i][0];
                    for(int j=1;j<n/k;j++)
                        cout<<" "<<G[i][j];
                     puts("");
                }
                    
            }
                
            
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11280009.html