题解 P6479 【[CRCI2006-2007] BARD】

Utilokasteinn · 2020-04-29 08:18:28 · 题解

这道题题目看了半个小时。。题目简介：

有n个人，第1个人是诗人，m个天。如果某天诗人来了，所有人都多会唱一首歌。否则，当天所有人都会互相学习，把当场所以人会的歌都学会。输出第m天后会唱所有歌的人。

简单模拟，如果哪天诗人没来，就记录那天来的人会唱的歌，并互相赋值。否则，当天来的人都新会唱一首歌，并且全部的歌数加1.

这道题不算太难，代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,song[101][101],s,k,come[101],v[101];
//n表示n个人，m表示m天 
//song[i][j]如果是1，就是第i个人会唱第j首歌，否则就是不会唱
//s表示最多会唱几首歌，如果诗人来了，s就加1，k表示来到人数 
//come[i]表示来的第i个人
//v[i]如果是1表示这天晚上第i首歌有人会唱，否则就没有人会唱 
int main()
{
    cin>>n>>m;//输入人数和天数 
    for(int i=1,o=0;i<=m;i++,o=0) 
    {//o如果是1，表示诗人来了，否则就是没来 
        cin>>k;//输入k 
        for(int j=1;j<=k;j++)
        {
            cin>>come[j];//输入来的第j个人 
            if(come[j]==1)o=1;//如果诗人来了，就等于1 
        }
        if(o) 
        {
            ++s;//如果诗人来了，最多可以唱的歌数加1 
            for(int j=1;j<=k;j++)
                song[come[j]][s]=1;//来的人都会唱这首歌 
        }
        else//如果诗人没来 
        {
            for(int j=1;j<=k;j++)
                for(int u=1;u<=s;u++)
                    if(song[come[j]][u])v[u]=1;
            //看看第u首歌有没有人会唱，1是有人会唱，0是没人会唱 
            for(int j=1;j<=k;j++)
                for(int u=1;u<=s;u++)
                    if(v[u])song[come[j]][u]=1;
            //如果有人会唱第u首歌，则当天来的全部人都会唱第u首歌 
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=s&&song[i][j];j++)//如果有一首不会唱这里就直接退出了
            if(j==s)cout<<i<<endl;//如果第i个人所有的歌都会唱，就输出i 
    return 0;
}

最后附上无注释代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,song[101][101],s,k,come[101],v[101];
int main()
{
    cin>>n>>m;
    for(int i=1,o=0;i<=m;i++,o=0) 
    {
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            cin>>come[j];
            if(come[j]==1)o=1;
        }
        if(o) 
        {
            ++s;
            for(int j=1;j<=k;j++)
                song[come[j]][s]=1;
        }
        else
        { 
            for(int j=1;j<=k;j++)
                for(int u=1;u<=s;u++)
                    if(song[come[j]][u])v[u]=1;
            for(int j=1;j<=k;j++)
                for(int u=1;u<=s;u++)
                    if(v[u])song[come[j]][u]=1;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=s&&song[i][j];j++)
            if(j==s)cout<<i<<endl;
    return 0;
}

谢谢观赏