CakeTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 965Accepted Submission(s): 119Special Judge
Problem Description
There aremsoda and today is their birthday. The1-st soda has preparedncakes with size1, 2, \dots, n. Now1-st soda wants to divide the cakes intomparts so that the total size of each part is equal.Note that you cannot divide a whole cake into small pieces that is each cake must be complete in themparts. Each cake must belong to exact one ofmparts.
Input
There are multiple test cases. The first line of input contains an integerT, indicating the number of test cases. For each test case:The first contains two integers(1 \le n \le 10^5, 2 \le m \le 10), the number of cakes and the number of soda.It is guaranteed that the total number of soda in the input doesn’t exceed 1000000. The number of test cases in the input doesn’t exceed 1000.
Output
For each test case, output "YES" (without the quotes) if it is possible, otherwise output "NO" in the first line.If it is possible, then outputmlines denoting themparts. The first number-th line is the number of cakes ini-th part. Thens_inumbers follow denoting the size of cakes ini-th part. If there are multiple solutions, print any of them.
Sample Input
41 25 35 29 3
Sample Output
NOYES1 52 1 42 2 3NOYES3 1 5 93 2 6 73 3 4 8
Source
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <vector>#include <queue>#include <set>#include <stack>#include <algorithm>#define LL long longusing namespace std;const LL MAXN = 500000 + 10;LL n, m;LL ans[20][MAXN];LL A[MAXN];LL pos[MAXN];LL tot, tar;bool dfs(LL dep, LL now, LL u, LL c){if(now == 0){LL k = 0;while(pos[k] != -1) k++;pos[k] = c;if(dfs(dep + 1, A[k], k + 1, c)) return true;pos[k] = -1;return false;}if(now == tar){if(dep == tot) return true;if(dfs(dep, 0, 0, c + 1)) return true;}for(LL i=u;i<tot;i++){if(pos[i] == -1 && now + A[i] <= tar){pos[i] = c;if(dfs(dep + 1, now + A[i], i + 1, c)) return true;pos[i] = -1;}}return false;}int main(){LL T;scanf("%d", &T);while(T–){scanf("%d%d", &n, &m);for(LL i=0;i<m;i++) for(LL j=0;j<n;j++) ans[i][j] = 0;if((n * (n + 1) / 2) % m != 0 || (2 * m – 1) > n){printf("NO\n");continue;}while(n >= 40){for(LL i=0;i<m;i++) ans[i][++ans[i][0]] = n – i;for(LL i=0;i<m;i++) ans[i][++ans[i][0]] = n – 2 * m + 1 + i;n -= 2 * m;}tot = n;tar = n * (n + 1) / (2 * m);for(LL i=0;i<tot;i++) A[i] = tot – i;for(LL i=0;i<tot;i++) pos[i] = -1;dfs(0, 0, 0, 0);for(LL i=0;i<tot;i++) ans[pos[i]][++ans[pos[i]][0]] = A[i];printf("YES\n");for(LL i=0;i<m;i++){printf("%d", ans[i][0]);for(LL j=1;j<=ans[i][0];j++) printf(" %d", ans[i][j]);printf("\n");}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，心有多大，舞台就有多大。
