题解：P11155 【MX-X6-T1】Subtask Dependency

· · 题解

题意

首先这是一道题，总共有 n 个子任务，其中有一些子任务依赖于其他的子任务。

判断一个程序能否通过一个子任务的条件如下：

  1. 如果该子任务依赖的子任务中存在一个子任务的状态为错误，则该子任务的状态为错误；

  2. 否则，评测机测试该子任务。如果选手的程序能通过该子任务，则该子任务状态为正确；否则状态为错误。

随后会给你 m 个选手程序，以及这些程序所对应的子任务的通过情况，你需要计算这些程序的得分。

分析

首先可以看出这是一道较为简单的模拟题，其中可能有一点点图论建模的相关知识，我们需要根据题意进行模拟。

首先将每一个子任务的依赖关系存储进一个数组。随后对于每一个给出的程序，枚举其子任务的通过情况，并计算得分即可，特别需要注意的一点是会出现某个子任务通过，但其所依赖的子任务不通过的情况，这时我们不应该计算该子任务的得分。

代码

#include<bits/stdc++.h>
using namespace std;
int s[114][514],d[114];
bool o[114];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
        for(int j=1;j<=d[i];j++)cin>>s[i][j];
    }
    int m;
    cin>>m;
    while(m--)
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>o[i];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=d[i];j++)
            {
                if(!o[s[i][j]])o[i]=0;
            }
        }
        for(int i=1;i<=n;i++)if(o[i])ans++;
        cout<<ans<<endl;
    }
}