3 科技节

(scifest.pas/.c/.cpp)

【问题描述】

一年一度的科技节即将到来。同学们报名各项活动的名单交到了方克顺校长那,结果校长一看皱了眉头:这帮学生热情竟然如此高涨,每个人都报那么多活动,还要不要认真学习了?!这样不行!……于是,校长要求减少一些活动,使每位学生只能参加一项(一名同学要参加某活动,必须已报名且该活动未被去掉)。当然,他也不希望哪位同学因此不能参加任何活动。他想知道自己的方案能否实行。

【输入】

输入文件名为scifest.in。

输入数据包括多组。

对于每组数据:

第一行两个正整数n和m,分别表示活动数和学生数。

接下来n行,每行m个为0或1的数。第i+1行第j列的数若为1,表示j同学报名参加活动i,否则表示j同学没有报名参加活动i。

【输出】

输出文件名为scifest.out。

对于每组数据输出一行,若校长方案可行则输出“Yes”,否则输出“No”。(均不包括引号)

【输入输出样例】

scifest.in

scifest.out

3 3

0 1 0

0 0 1

1 0 0

4 4

0 0 0 1

1 0 0 0

1 1 0 1

0 1 0 0

Yes

No

【数据范围】

对于20%的数据,n≤10,m≤200,数据组数≤10;

对于60%的数据,n≤16,m≤300,数据组数≤100;

对于100%的数据,n≤16,m≤300,数据组数≤1,000。

解题报告:

  这道题好像是我在这套题里唯一做了的,用了一个搜索,每次去找只选了唯一活动的学生,做标记,没有唯一的就找哪一个活动参与的人最少,然后删去。再重复刚才的步骤,直到所有未被删的都是唯一标记,若不是,就为No.我觉得并没有错,可是,可是,我把n和m看反了。。输入都是对的,后来进入搜索就忘了,于是,全错,还有,我连Yes,No 都输出的是YES NO ,能不全错吗?.......

  那天因为时间原因,我也没有去调试改错,看一下我原程序的错误,这里便给一个标程的解释吧。

  标程也是用的搜索,只不过它是记录的选中的活动及其人数,再加上 位运算 的使用,十分巧妙。位运算也是以前讲过的,复习一下:

&:0 1 0 1        | :0 1 0 1          ^: 0 1 0 1

1 1 0 0             1 1 0 0              1 1 0 0

0 1 0 0             1 1 0 1              1 0 0 1

  下面是对标程中的一些难理解的代码的解释:

 int x[][],h[];

x[20][10]:最大二进制数31位,此处有300个学生,把每一项活动的300个用10组二进制数记录其 1 的位置。

               if (a==)
{
x[i][j/]+=<<(j%);
h[i]++;
}

1、x[i][j/31]:第 i  个项目 第 k 组 ,如果参加。一个二进制数为32位,一位符号位,/31 即这个1 在第几组 上,j %31 即这一组的第几位上是 1。

 for ( i=;i<;i++)
{
if ((s[i]&x[p][i])>) break;
t[i]=s[i]|x[p][i];
}

这里是选择活动时的操作:s[i]是已经选了的活动。&:如果s[i]与x[p][i]上的1 有重复,(如:0 1 0 1&1 1 0  0),则说明一个人有两个活动了,break;

| :如果选这个活动这个人本来没有选的,s[i]这一位上为0,则这项活动可以选(如:0 1 0 1|1 0 0 0  [第二行的1可以选])

另外,还要按照活动的参与人数进行排序,人多的先选。

下面是完整代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,m;
int x[][],h[];
bool yes=;
void work()
{
memset(x,,sizeof (x));
for (int i=;i<n;i++)
{
h[i]=;
for (int j=;j<m;j++)
{
int a;
scanf("%d",&a);
if (a==)
{
x[i][j/]+=<<(j%);
h[i]++;
}
}
}
int k;
for (int i=;i<n-;i++) //? n-1
for (int j=i+;j<n;j++)
{
if (h[i]<h[j])
{
k=h[i];h[i]=h[j];h[j]=k;
for (int t=;t<;t++)
{
int u=x[i][t];x[i][t]=x[j][t];x[j][t]=u;
}
}
}
}
void doit(int p,int s[],int have)
{
if (p==n)
{
if (have==m) yes=;
return ;
}
int t[],i;
for ( i=;i<;i++)
{
if ((s[i]&x[p][i])>) break;
t[i]=s[i]|x[p][i];
}
if (i==) doit(p+,t,have+h[p]);
if (!yes) doit(p+,s,have);
}
int main()
{
freopen("scifest.in","r",stdin);
freopen("scifest.out","w",stdout);
while (scanf("%d%d",&n,&m)==)
{
work();
yes=;
doit(,x[],);//***p=0
if (yes==) printf("Yes\n");
else printf("No\n");
}
return ;
}

注意:赋初值。

04-16 14:55