首页 > ACM题库 > HDU-杭电 > HDU 2806-Selecting Problems[解题报告]HOJ
2014
02-17

HDU 2806-Selecting Problems[解题报告]HOJ

Selecting Problems

问题描述 :

The college of computer & software is going to hold an ACM contest. N (0<N<=1000) students have registered for the contest, and the teacher LCY has thought up M (0<M<=15) problems numbered from 1 to M. LCY is so familiar with the students that he can forecast the result of every student for the M problems.
Now he will select as many problems as possible from the M problems. And he want at least K (0<=K<=M) students to solve all problems. Will you compute the maximum number of problems he can choose? Output “0″ if there is no selection can satisfy the condition.

输入:

First line of each case contains three integers: N, M and K. Then N lines follow, and each line has the format:
Name P N1 N2 … NP.
Name (the length won’t exceed 20), P (number of problems he/she can solve, 0<=P<=M), then P integers (represent the problems, 1-based).

输出:

First line of each case contains three integers: N, M and K. Then N lines follow, and each line has the format:
Name P N1 N2 … NP.
Name (the length won’t exceed 20), P (number of problems he/she can solve, 0<=P<=M), then P integers (represent the problems, 1-based).

样例输入:

2 6 2
zl1 6 1 2 3 4 5 6
zl2 5 1 2 3 4 5
2 3 2
zl1 2 2 3
zl2 1 1

样例输出:

5
0

下面代码的理解。
v[][] 二维里面放置的是vector。其实是三维的。
如果把这个vector的size()打印出来的话,其实是符合杨辉三角的。
1 1
1 2 1
1 3 3 1
1 4 6 4 1
顺便再打印出 v[4]中的vector内容(二进制) 如下:
0
1 10 100 1000
11 101 1001 110 1010 1100
111 1011 10011 1110
1111
大家应该能开出规律了,v[i][j] 是里面1的个数为j个的集合。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>v[20][20];
int n,m,k;
int q[1005];
char ch[22];
bool work(int a)
{
    int i,j;
    int res=0;
     for(i=0;i<v[m][a].size();i++)
     {    res=0;
         for(j=1;j<=n;j++)
         {     
             if((v[m][a][i]^q[j])==v[m][a][i]+q[j])
             {    
                     res++;
             }    
         }
         if(res>=k) return true;

     }
     return false;
}                 
int main()
{
    int i,j,a,b,c;
    v[1][0].push_back(0);
    v[1][1].push_back(1);
    for(i=2;i<=15;i++)
    {
          for(j=0;j<i;j++)
          {
              for(int k=0;k<v[i-1][j].size();k++)
              {
                  v[i][j].push_back(v[i-1][j][k]<<1);
                  v[i][j+1].push_back(v[i-1][j][k]<<1^1);
              }
          }
     }    

    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            q[i]=(1<<m)-1;
            scanf("%s %d",ch,&a);
            for(j=0;j<a;j++)
            {
                scanf("%d",&b);
                q[i]^=(1<<(b-1));

            }

        }
        int l=0,r=m,mid;
        while(l+1<r)
        {
            mid=(l+r)>>1;
            if(work(mid))   l=mid;
            else
            r=mid-1;
        }
        if(work(r))  { printf("%d\n",r);}
        else printf("%d\n",l);
    }
    return 0;
}

 


  1. 是穷举,但是代码有优化(v数组),并不是2^n。测试数据应该没问题,之前有超时的代码。

  2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……