首页 > 代码库 > hdu5355 Cake
hdu5355 Cake
Problem Description
There are soda
and today is their birthday. The -st
soda has prepared cakes
with size .
Now -st
soda wants to divide the cakes into 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 parts. Each cake must belong to exact one of parts.
Note that you cannot divide a whole cake into small pieces that is each cake must be complete in the parts. Each cake must belong to exact one of parts.
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 and , 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.
The first contains two integers and , 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 output lines denoting the parts. The first number of -th line is the number of cakes in -th part. Then numbers follow denoting the size of cakes in -th part. If there are multiple solutions, print any of them.
If it is possible, then output lines denoting the parts. The first number of -th line is the number of cakes in -th part. Then numbers follow denoting the size of cakes in -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 73 3 4 8
这题和木棒拼接正方形非常像,用同样的思路即可了。
这里注意dfs可能比較深,所以要手动开栈。#pragma comment(linker, "/STACK:102400000,102400000") 这句话加在程序最前面。
#pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<string> #include<algorithm> using namespace std; #define maxn 100050 #define ll long long int vis[maxn],liang,fen,n; set<int>myset[20]; set<int>::iterator it; int dfs(int x,int pos,ll len) { int i; if(x==fen)return 1; for(i=pos;i>=1;i--){ if(!vis[i]){ vis[i]=1; if(len+i<liang){ myset[x].insert(i); if(dfs(x,i-1,len+i))return 1; myset[x].erase(i); } else if(len+i==liang){ myset[x].insert(i); if(dfs(x+1,n,0))return 1; myset[x].insert(i); } vis[i]=0; } } return 0; } int main() { int i,j,T; ll num; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&fen); num=(ll)(n+1)*n/2; if(n<fen || num%fen!=0 || num/fen<n){ printf("NO\n");continue; } liang=num/fen; memset(vis,0,sizeof(vis)); for(i=0;i<=fen;i++){ myset[i].clear(); } if(dfs(0,n,0)){ printf("YES\n"); for(i=0;i<fen;i++){ printf("%d",myset[i].size()); for(it=myset[i].begin();it!=myset[i].end();it++){ printf(" %d",*it); } printf("\n"); } } else printf("NO\n"); } return 0; } /* 100 50 10 NO 40 10 YES 3 3 39 40 3 7 37 38 3 11 35 36 3 15 33 34 3 19 31 32 3 23 29 30 4 1 26 27 28 5 2 9 22 24 25 5 6 17 18 20 21 8 4 5 8 10 12 13 14 16 */
hdu5355 Cake
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。