Cake
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)
Special Judge
Problem Description
There aresoda and today is their birthday. The-st soda has preparedcakes with size. Now-st soda wants to divide the cakes intoparts 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 theparts. Each cake must belong to exact one ofparts.
Input
There are multiple test cases. The first line of input contains an integer, indicating the number of test cases. For each test case:The first contains two integers, 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 outputlines denoting theparts. The first number-th line is the number of cakes in-th part. Thennumbers follow denoting the size of cakes in-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
/*********************************************************************************/
该题有点坑，比赛的时候spj出了问题，结果成了一道AC率高达50%的水题，比赛结束后更新了spj，使得原先AC的代码大部分都WA了，现在我来讲讲能AC的一种方法，之前说晚些会放上另一种方法，但是不知道哪里出了问题，一直TLE，所以不能与大家分享了，对不起。
题意：给你n个尺寸大小分别为1,2,3,…,n的蛋糕，要求你分成m份，要求每份中所有蛋糕的大小之和均相同，如果有解，输出“YES”，并给出每份的蛋糕数及其尺寸大小，否则输出“NO”
例如n=5,m=3，即大小尺寸分别为1,2,3,4,5的5个蛋糕，要求分成三份，那么解可以是第一份一个蛋糕，大小为5；第二份两个蛋糕，大小为1、4；第三份两个蛋糕，大小为2、3。这样每份大小之和均为5，满足题目要求。
放上出题人的解题报告
解题思路：此题无解的情况无外乎两种：①所有蛋糕的大小之和无法被m整除；②每一份蛋糕的大小之和不得小于蛋糕大小的最大值n，即sum/m>n,转化一下为n*m<sum，亦可以将sum代入，转化为n<2*m-1。
之后便是有解的情况，有解的情况每份蛋糕的大小之和是知道的，即sum/m。然后我们可以知道n最小得是2*m-1，举个例子就很清楚了，譬如n=5,m=3，
5 3
1 5
2 4 1
2 3 2
2*m-1就说明了n本身可以自己一组，其他两两一组，一个正向递增，一个反向递减，必定可以凑成n，当然这是奇数的情况
但该方法其实是不分奇偶性的，上述只是说明。其实我们需要做的就是把分配方式分成两部分，一部分是k个2*m，另外就是剩下的那部分，我们来看看n=23,m=6这组数据，之前AC的代码普遍过不了这组数据
23 6YES3
先利用(n-m*2+1)%(m*2)+m*2-1算出粉色那部分数据的大小，然后二分枚举即可找到符合的蛋糕大小，剩下的绿色部分则是k个2*m的部分，该部分小的数是正向递增的，大的数是反向递减的，所以必定是符合要求的。为了更加直观，，放上n=100，m=5的数据
100 5YES12 99 24 87 25 86 26 85 27 84 28 8320 31 80 32 79 33 78 34 77 35 76 36 75 37 7420 40 71 41 70 42 69 43 68 44 67 45 66 46 6520 49 62
上AC代码，如果仍有不理解的可以在此文章下评论，我会尽快予以回答，谢谢
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>#include<math.h>#include<vector>#include<map>#include<set>#include<cmath>#include<string>#include<algorithm>#include<iostream>#define exp 1e-10#define ll __int64using namespace std;const int N = 100005;const int inf = 1000000000;const int mod = 1000000007;int solve(){__int64 n,m;int i,j,k,c,s,d,r,w[32];set<int> v;set<int>::iterator it;scanf("%I64d%I64d",&n,&m);if(((n+1)*n/2)%m||m*2-1>n)return puts("NO");c=(n-m*2+1)%(m*2)+m*2-1,s=c*(c+1)/(m*2),d=(n-c)/(m*2);puts("YES");for(i=1; i<=c; i++)v.insert(i);for(j=0,k=c+1;j<m;j++,putchar('\n')){for(c=r=0;r<s;){it=v.upper_bound(s-r);r+=w[c++]=*–it;v.erase(it);}printf("%d",c+d*2);for(i=0;i<c;i++)printf(" %d",w[i]);for(i=0;i<d;i++)printf(" %d %d",k++,n–);}}int main(){int t;for(scanf("%d",&t);t–;solve());}
//此题数据被更新，上述方法是已经AC的代码，但以下方法已经不能ＡＣ，留此作为反例借鉴
题意：给你n个尺寸大小分别为1,2,3,…,n的蛋糕，要求你分成m份，要求每份中所有蛋糕的大小之和均相同，如果有解，输出“YES”，并给出每份的蛋糕数及其尺寸大小，否则输出“NO”
却又小到连一粒嫉妒的沙石也不能容纳
