P8038 [COCI2016-2017#7] BAZA 题解

· · 题解

题目大意

现有一个包含 n 行 m 列的数据库，然后询问 q 次，每次有 m 个数，当 m_j(j∈[1,m]) 为 \texttt{-1} 时可以将 m_j 变成任意数。求出数据库中有几行数可以由这 m 个数变化而来。

思路

既然当 m_j 为 \texttt{-1} 时可以变成任何数，那么我们只需要考虑当 m_j≠-1 时和数据库的匹配情况。

对于输入的 m_j，我们可以枚举第 i 行第 j 列上的数是否与 m_j 相等。用数组 vis 保存每一行是否与这 m 个数有不同，则当 m_j≠a_{i,j} 时将 vis_i 赋值为 1。最后检查 1 到 n 中的 vis_i 有多少个仍然为 0，即为这次询问的答案。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,b,q;
int a[1001][1001];
bool vis[1001];
int main()
{
//  freopen("P8038.in","r",stdin);
//  freopen("P8038.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    scanf("%d",&q);
    while(q--)
    {
        memset(vis,0,sizeof(vis));
        ans=0;
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&b);
            if(b!=-1)
            {
                for(int i=1;i<=n;i++)
                    if(a[i][j]!=b) vis[i]=1;
            }
        }
        for(int i=1;i<=n;i++) if(!vis[i]) ans++;
        printf("%d\n",ans);
    }
    return 0;
}