鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5355
題意：給定n與m,其中1<= n <= 1e5,2 <= m <= 10;問是否存在將1~n個數分成m組，使得每組的和相等；若存在輸出m行，每行表示一組的值，否則輸出NO;
ps:總共T<=1000組數據，還是挺大的；
思路：預判之後，若可能存在則直接以2m為周期，從大往小構造出和相等的m組，這樣就可以將n的值縮小到2m~4m-2；因為當n = 4m-1時，再次減去一個周期，下一個討論的右邊界為2m-1,易知(2m-1)*2m/2/m是可以構造出符合的m個式子的；並且坑爹的是，出題人這次的常數系數不能太大，AC的代碼運行了514ms，當把n 周期縮小處改為n > 4*m-1時，直接TLE了；在搜索中系數大了不止一倍；
dfs也是比較巧妙，需要加個start來單調查找每組的數據，是最終全部m組全部求完了再return true，並不是每組完成就直接return，這樣還可以修改直接選擇的錯誤;
判斷一組完成了只是將參數值復原為原始值；還有需要使用dp優化，設置了define來簡寫；
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define rep0(i,l,r) for(int i = (l);i < (r);i++)
4 #define rep1(i,l,r) for(int i = (l);i <= (r);i++)
5 #define rep_0(i,r,l) for(int i = (r);i > (l);i--)
6 #define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
7 #define MS0(a) memset(a,0,sizeof(a))
8 #define MS1(a) memset(a,-1,sizeof(a))
9 #define MSi(a) memset(a,0x3f,sizeof(a))
10 #define inf 0x3f3f3f3f
11 #define lson l, m, rt << 1
12 #define rson m+1, r, rt << 1|1
13 #define lowbit(x) (x&(-x))
14 typedef pair<int,int> PII;
15 #define A first
16 #define B second
17 #define MK make_pair
18 typedef long long ll;
19 typedef unsigned int uint;
20 template<typename T>
21 void read1(T &m)
22 {
23 T x=0,f=1;char ch=getchar();
24 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
25 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
26 m = x*f;
27 }
28 template<typename T>
29 void read2(T &a,T &b){read1(a);read1(b);}
30 template<typename T>
31 void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
32 template<typename T>
33 void out(T a)
34 {
35 if(a>9) out(a/10);
36 putchar(a%10+'0');
37 }
38 int i,j,k,n,m,l,r;
39 const int N = 1e5+7;
40 int ans[11][N],aux[11][N],vs[44],ave,board;
41 int dp[50][11],rec[50][11][11][50];
42 #define def rec[board][m]
43 bool dfs(int tot,int id,int start)
44 {
45 if(tot == ave){id++;tot = 0;start = 1;} // 這是一項結束了，是另一項的開始;當然了只有全部結束時，才返回true;
46 if(id == m){
47 rep1(i,1,board)if (!vs[i]){
48 aux[id][++aux[id][0]] = i;
49 }
50 return true;
51 }
52 rep1(i,start,board){
53 if(tot+i > ave) return false;
54 if(!vs[i]){
55 vs[i] = 1;
56 aux[id][++aux[id][0]] = i;
57 if(dfs(tot+i,id,i+1)) return true;
58 vs[i] = 0,aux[id][0]--;
59 }
60 }
61 return false;
62 }
63 bool solve(int top)
64 {
65 if(top >= 4*m-1){
66 for(int i = 1,j = 0;i <= m;i++,j++){
67 ans[i][++ans[i][0]] = top-2*m+1+j;
68 ans[i][++ans[i][0]] = top-j;
69 }
70 return solve(top-2*m);
71 }
72 else{
73 ave = top*(top+1)/m/2;
74 //printf("%d ",ave);
75 board = top;
76 if(dp[board][m] == 0){
77 if(dfs(0,1,1)){
78 dp[board][m] = 1;
79 rep1(i,1,m)
80 rep1(j,0,aux[i][0])
81 def[i][j] = aux[i][j]; // define了
82 }
83 else dp[board][m] = -1;
84 }
85 if(dp[board][m] == 1) return true;
86 return false;
87 }
88 }
89 int main()
90 {
91 //freopen("data.txt","r",stdin);
92 //freopen("out.txt","w",stdout);
93 int T; read1(T);
94 for(int kase = 1;kase <= T;kase++){
95 MS0(vs);
96 rep1(i,0,10) ans[i][0] = aux[i][0] = 0;
97 read2(n,m);
98 ll sum = 1LL*n*(n+1)/2;
99 if(sum%m || sum/m < n || !solve(n)){
100 puts("NO");
101 continue;
102 }
103 puts("YES");
104 rep1(i,1,m){
105 printf("%d",ans[i][0]+def[i][0]);
106 rep1(j,1,ans[i][0])
107 printf(" %d",ans[i][j]);
108 rep1(j,1,def[i][0])
109 printf(" %d",def[i][j]);
110 puts("");
111 }
112 }
113 return 0;
114 }
