2015暑假多校联合---Cake（深搜）

题目链接：HDU 5355

http://acm.split.hdu.edu.cn/showproblem.php?pid=5355

Problem Description

There are

Input

There are multiple test cases. The first line of input contains an integer

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

Sample Input

1 2

5 3

5 2

9 3

Sample Output

YES

1 5

2 1 4

2 2 3

YES

3 1 5 9

3 2 6 7

3 3 4 8

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6

Recommend

wange2014 | We have carefully selected several similar problems for you: 5867 5866 5865 5864 5863

题意：输入n，m 表示有n个蛋糕，大小为1~n，要均分给m个人，但是每一个蛋糕不能切分，给每个人的蛋糕必须是完整的，输出分配方案；

思路：刚开始，我是用贪心划分的，每个人应该划分的量h=（n+1）*n/2/m 首先给一个人分一个最大的蛋糕x，接下来分h-x，如果h-x已经给别人了，那么继续向下找h-x-1....

这样做是有bug的如23 6 这个数据就会输出NO ，但实际上是有解的YES

3 11 12 23

4 1 10 13 22

4 2 9 14 21

4 3 8 15 20

4 4 7 16 19

4 5 6 17 18

故这样贪心的做法有bug；

正解：深搜枚举出所有的情况，找到正确的划分方案，这里有一个很好的可以优化，可以发现任取2*m个连续的数都可以均分给m个人，并且n>=2*m-1时才有划分方案，所以令nn=（n-2*m+1）%2*m+2*m-1 从nn+1到n是x*2*m，这部分很好划分，那么只需要对1~nn进行深搜即可；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
int n,m,nn,h;
bool vis[100005];

set<int>s[15];
set<int>::iterator it;

int dfs(int cnt,int pos,int sum)
{
    if(cnt==m+1) return 1;
    for(int i=pos;i>=1;i--)
    {
        if(!vis[i])
        {
            vis[i]=true;
            if(i+sum<h)
            {
               s[cnt].insert(i);
               if(dfs(cnt,pos-1,sum+i)) return true;
               s[cnt].erase(i);
            }
            else if(i+sum==h)
            {
                s[cnt].insert(i);
                if(dfs(cnt+1,n,0)) return true;
                s[cnt].erase(i);
            }
            vis[i]=false;
        }
    }
    return 0;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=0;i<15;i++)
        s[i].clear();
        scanf("%d%d",&nn,&m);
        if(nn<2*m-1||(long long)(nn+1)*nn/2%m!=0)   {puts("NO"); continue;}
        n=(nn-2*m+1)%(2*m)+2*m-1;
        h=(n+1)*n/2/m;
        memset(vis,false,sizeof(vis));

        dfs(1,n,0);

        int go=(nn-2*m+1)%(2*m)+2*m-1;
        int  k=(nn-2*m+1)/(2*m);
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=m;j++)
            {
                s[j].insert(go+j);
                s[j].insert(go+2*m+1-j);
            }
            go+=2*m;
        }
        puts("YES");
        for(int i=1;i<=m;i++)
        {
            printf("%d",s[i].size());
            for(it=s[i].begin();it!=s[i].end();it++)
                printf(" %d",*it);
            puts("");
        }
    }
}