列表

详情


NC232722. 佛

描述

我收到了 n 件礼物,其中每个礼物有 m 个颜色。 

接下来会输入一个序列 b,表示已知 Boss 送我的那一件礼物会有颜色 b_i

请输出每次得到信息之后,n 件礼物中可能是 Boss 送我的礼物个数。

注意:询问之间不独立,例如得到第三条信息时,你需要综合前三条(第一、二、三条)信息综合判断礼物是否符合要求。

输入描述

全文第一行输入一个正整数 ,表示数据组数。

对每组数据,第一行输入两个正整数

接下来输入一个 的矩阵,第 i 行第 j 列表示第 i 个礼物的第 j 种颜色

接下来输入一个长度为 m 的序列,表示序列

数据保证同一行之内 col 互不相同(即一个礼物上不会有两种相同的颜色),且信息 b_i 互不相同。

输出描述

对每组数据输出一行 m 个数,表示每次得到信息之后的结果。

示例1

输入:

2
3 3
1 2 3
2 3 4
3 4 5
3 2 1
3 2
1 2
2 3
1 3
1 2

输出:

3 2 1
2 1

说明:

第一组数据,三件礼物的颜色分别是 \{1,\color{blue}2\color{black},\color{red}3\color{black}\},\{\color{blue}2\color{black},\color{red}3\color{black},4\},\{\color{red}3\color{black},4,5\},一开始信息是 \color{red}3,三件礼物都符合;第二次信息是 \color{blue}2,只有前两件符合;最后一次信息是 1,只有第一件符合,因此依次输出符合要求的礼物个数 3,2,1

第二组数据,三件礼物颜色分别是 \{\color{red}{1},\color{blue}{2}\},\{\color{blue}{2},3\},\{\color{red}{1},3\},第一条信息给出之后,\{\color{red}{1},\color{blue}{2}\}\{\color{red}{1},3\} 都包含颜色 \color{red} 1,因此符合要求的有 2 个;第二条信息给出之后,同时具有颜色 \color{red}{1},\color{blue}{2} 的只有物品 1 了。

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

pypy3 解法, 执行用时: 2895ms, 内存消耗: 57712K, 提交时间: 2022-05-10 21:18:35

for cas in range(int(input())):
n, m = map(int, input().split())
c = []
for i in range(n):
c.append(list(map(int, input().split())))
a = [i for i in range(n)]
for tmp in input().split():
b = int(tmp)
nxt = []
for x in a:
for y in c[x]:
if y == b:
nxt.append(x)
break
print(len(nxt), end = ' ')
a = nxt
print('')

C++ 解法, 执行用时: 507ms, 内存消耗: 684K, 提交时间: 2022-05-06 20:17:22

#include<bits/stdc++.h>
using namespace std;
int main(){
int t,n,m,i,j,v[205][205],x,s;
scanf("%d",&t);
while(t--){
memset(v,0,sizeof v);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&x);
v[i][x]=1;
}
}
for(i=1;i<=m;i++){
s=0;
scanf("%d",&x);
for(j=1;j<=n;j++){
if(!v[j][0]){
if(v[j][x]) s++;
else v[j][0]=1;
}
}
printf("%d ",s);
}
printf("\n");
}
return 0;
}

Python3 解法, 执行用时: 2854ms, 内存消耗: 5440K, 提交时间: 2022-05-19 10:14:33

T=int(input())
for _ in range(T):
n,m=map(int,input().split(' '))
arr=[1]*n
brr=[[0]*205 for _ in range(n)]
for i in range(n):
for ci in map(int,input().split(' ')):
brr[i][ci]=1
cnt=0
for cj in map(int,input().split(' ')):
for i in range(n):
if brr[i][cj]==0:
arr[i]=0
cnt+=1
print(sum(arr),end=' ')
print()

上一题