首页 > ACM题库 > HDU-杭电 > hdu 3748 Equivalent mass[解题报告]C++
2015
02-22

hdu 3748 Equivalent mass[解题报告]C++

Equivalent mass

问题描述 :

Little Min’s family has a grocery store,and she helps her parents to weight the goods everyday. She often wants to know whether the quality of the goods they sell can be equal to the sum quality of several poise weights. Suppose there are N kinds of poise weights, but there are M pairs of them can’t be used at the same time, and we know the quality of the goods is V. The question is: can little Min exactly take K form N poise weights, and their sum quality is equal to the goods’ quality?
Download

输入:

The first line contains an integer T, the number of test cases (T < 25). Each test case is in the following format.The first line starts with four integers N (1 <= N <= 32) denoting the number ofpoise weights and M (0 <= M <= 6),K(1<=K<=N),V(1<=V<=1000000000). The second line has N integer ai each denoting the kind poise weight’s quality(1<=i<=N,1<=ai<=1000000000).Then following M lines, each line has two integers a and b, which denoting the a-th poise weight can’t be used with the b-th poise weight at the same time(1<=a,b<=N,a!=b).

输出:

The first line contains an integer T, the number of test cases (T < 25). Each test case is in the following format.The first line starts with four integers N (1 <= N <= 32) denoting the number ofpoise weights and M (0 <= M <= 6),K(1<=K<=N),V(1<=V<=1000000000). The second line has N integer ai each denoting the kind poise weight’s quality(1<=i<=N,1<=ai<=1000000000).Then following M lines, each line has two integers a and b, which denoting the a-th poise weight can’t be used with the b-th poise weight at the same time(1<=a,b<=N,a!=b).

样例输入:

2
5 1 3 1000
100 200 300 500 600
2 3
5 2 3 1000
100 200 300 500 600
2 3
1 5

样例输出:

YES
NO


不得不说代码写的非常丑陋。。
开始写了个暴力+剪枝果断TLE(不过貌似有同学这样水过了。。),听了大牛讲解后发现是二分的思想,貌似之前也有题用过这样的方法,将全部数据分为两部分,先对一部分暴力记录部分结果,然后枚举另一部分看和之前记录的结果能不能组合成解。这题就是这样的思路,先将所有有限制条件的物品分一组,暴力出所有可能的解,要用hash记录,因为重量可能到100000000不能开数组,然后再对剩下的进行枚举,复杂度O(2^(n/2+1))取决于这两组是否分的平均。

#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
map<int,int> hash[35];
int vis[35];
int n,v,k;
int flag;
int constraint;
int g[35][35];
struct node
{
    int w;
    int cons;
}t[35],s[35];
void dfs(int y,int x,int cur)
{
    if(y>k) return;
    else if(x==constraint) hash[y][cur]=1;
    else
    {
        int tt=0;
        if(s[x].cons!=-1)
        {
            for(int i=0;i<n;i++) if(g[x][i])
            {
                if(vis[i])
                {
                    tt=1;
                    break;
                }
            }
        }
        if(s[x].cons==-1||!tt)
        {
            vis[x]=1;
            dfs(y+1,x+1,cur+s[x].w);
            vis[x]=0;
        }
        dfs(y,x+1,cur);
    }
}
void dfs2(int y,int x,int cur)
{
    if(y>k) return;
    else if(x==n)
    {
        if(hash[k-y][v-cur]==1)
        {
            flag=1;
            return;
        }
    }
    else if(!flag)
    {
        dfs2(y+1,x+1,cur+s[x].w);
        dfs2(y,x+1,cur);
    }
}
int main()
{
    int i,j;
    int T;
    int m;
    int mark[35];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&k,&v);
        for(i=0;i<n;i++)
        {
            scanf("%d",&t[i].w);
            t[i].cons=-1;
            s[i].cons=-1;
        }
        int cnt=0;
        memset(mark,-1,sizeof(mark));
        memset(g,0,sizeof(g));
        for(i=0;i<m;i++)
        {
            int t1,t2;
            int c1,c2;
            scanf("%d%d",&t1,&t2);
            t1--;
            t2--;
            if(mark[t1]==-1) mark[t1]=cnt++;
            if(mark[t2]==-1) mark[t2]=cnt++;
            c1=mark[t1];
            c2=mark[t2];
            s[c1].cons=c2;
            s[c1].w=t[t1].w;
            t[t1].cons=t2;
            t[t2].cons=t1;
            s[c2].cons=c1;
            s[c2].w=t[t2].w;
            g[c1][c2]=1;
            g[c2][c1]=1;
        }
        if(cnt>n/2) constraint=cnt;
        else constraint=n/2+1;
        for(i=0;i<n;i++) if(t[i].cons==-1)
        {
            s[cnt++]=t[i];
        }
        for(i=0;i<=k;i++)
            hash[i].clear();
        memset(vis,0,sizeof(vis));
        dfs(0,0,0);
        flag=0;
        dfs2(0,constraint,0);
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
}

 


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. int L[m+1][n+1];这样定义出错,这个在gcc上可以编译通过 在VS上不行 应该改为new 或者vector

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。