- Problem Description
- There are?
- m
- ?soda and today is their birthday. The?
- 1
- -st soda has prepared?
- n
- ?cakes with size?
- 1,2,,n
- . Now?
- 1
- -st soda wants to divide the cakes into?
- m
- ?parts 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 the?
- m
- ?parts. Each cake must belong to exact one of?
- m
- ?parts.
- ?
- Input
- There are multiple test cases. The first line of input contains an integer?
- T
- , indicating the number of test cases. For each test case:
- The first contains two integers?
- n
- ?and?
- m
- ?
- (1n
- 105
- ,2m10)
- , the number of cakes and the number of soda.
- It is guaranteed that the total number of soda in the input doesnt exceed 1000000. The number of test cases in the input doesnt 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 output?
- m
- ?lines denoting the?
- m
- ?parts. The first number?
- si
- ?of?
- i
- -th line is the number of cakes in?
- i
- -th part. Then?
- si
- ?numbers follow denoting the size of cakes in?
- i
- -th part. If there are multiple solutions, print any of them.
- ?
- Sample Input
- 4 1 2 5 3 5 2 9 3
- ?
- Sample Output
- NO YES 1 5 2 1 4 2 2 3 NO YES 3 1 5 9 3 2 6 7 3 3 4 8
- /**
- hdu5355 思维 + 爆搜
- 题目大意: 1~n 这 n 个数分成 m 份问能否成功, 若能请给出一种分配方式
- 解题思路: 假设 sum(1~n)%m!=0 无解, 而且 sum/m<n 亦无解, 其它情况有解令 ans=n%(2*m), 若 ans=0, 则一个有效方案为 (1+n),(2+n-1),(3+n-2)....
- 每 m 个为一组, 若 ans!=0: 令 cnt=min(n,ans+(2*m)), 这时候的 cnt 非常小我们爆搜就攻克了关于爆搜我们总共要搜出 m 组搜的时候枚举
- 每组的最小的数, 然后从该数開始往大了搜索
- */
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- typedef long long LL;
- vector<int>vec[55];
- LL n,m,dis,ans;
- int vis[105],pos[105],num[25];
- bool dfs(int cnt,int sum,int id)///ans 个数分成和相等的 m 份 (id 为第 cnt 份中最小的数爆搜)
- {
- if(cnt==m+1)return true;
- for(int i=ans;i>=id;i--)
- {
- if(vis[i])continue;
- if(sum+i==dis)
- {
- pos[i]=cnt;
- vis[i]=1;
- if(dfs(cnt+1,0,1))
- return true;
- vis[i]=0;
- return false;
- }
- else if(sum+i<dis)
- {
- pos[i]=cnt;
- vis[i]=1;
- if(dfs(cnt,sum+i,i+1))
- return true;
- vis[i]=0;
- }
- }
- return false;
- }
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- scanf("%lld%lld",&n,&m);
- LL sum=n*(n+1)/2;
- if(sum%m)
- {
- puts("NO");
- continue;
- }
- LL ave=sum/m;
- if(ave<n)
- {
- puts("NO");
- continue;
- }
- puts("YES");
- ans=n%(2*m);
- if(ans!=0)
- {
- ans+=2*m;
- ans=min(ans,n);
- }
- for(int i=1;i<=m;i++)
- {
- vec[i].clear();
- }
- memset(num,0,sizeof(num));
- for(int i=n;i>ans;i-=(2*m))/// 分成 2*m 份
- {
- for(int j=1;j<=m;j++)
- {
- int x=i-j+1;
- int y=i-2*m+j;
- vec[j].push_back(x);
- vec[j].push_back(y);
- num[j]+=(x+y);
- }
- }
- dis=ave-num[1];
- memset(vis,0,sizeof(vis));
- memset(pos,0,sizeof(pos));
- dfs(1,0,1);
- for(int i=1;i<=ans;i++)
- {
- vec[pos[i]].push_back(i);
- }
- for(int i=1;i<=m;i++)
- {
- printf("%d",vec[i].size());
- for(int j=0;j<vec[i].size();j++)
- {
- printf("%d",vec[i][j]);
- }
- printf("\n");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2507225.html