NC24063. [USACO 2019 Jan B]Guess the Animal
描述
游戏开始时，Bessie会想好一种动物（大部分时候，她想的都是奶牛，这使得游戏相当无聊，但是偶尔Bessie也能有些新意，想一些别的）。随后Elsie会通过问一些问题来猜出Bessie选择的动物。每个问题都是询问这种动物是否具有某个特定的特征，Bessie对于每个问题回答“是”或“不是”。例如：
Elsie：“这种动物是能飞的吗？” Bessie：“不是。” Elsie：“这种动物是吃草的吗？” Bessie：“是。” Elsie：“这种动物是能产奶的吗？” Bessie：“是。” Elsie：“这种动物是会哞哞叫的吗？” Bessie：“是。” Elsie：“这样的话我想这种动物是奶牛。” Bessie：“猜对了！”
如果我们将所有具备符合Elsie到目前为止所提出的问题的特征的动物的集合称为“可行集”，那么Elsie会持续进行提问直到可行集仅包含一种动物，然后她会把这种动物作为她的答案。对于每个问题，Elsie会选择某种动物的一个特征进行询问（即使这个特征并不能进一步帮助她缩小可行集）。她不会关于同一个特征询问两次。
给定Bessie和Elsie知道的所有动物以及它们的特征，请求出Elsie在猜出正确的动物之前能够得到的“是”的回答的最大数量。
输入描述
输入的第一行包含动物的数量N（2≤N≤100）。以下N行每行描述了一种动物。每一行开始是这种动物的名称，接下来是一个整数K（1≤K≤100），接下来是这种动物的K个特征。动物的名称和特征是至多20个小写字母（a..z）组成的字符串。没有两种动物具有完全相同的特征。
输出描述
输出游戏结束之前Elsie可能得到的“是”的回答的最大数量。
示例1
输入:
4 bird 2 flies eatsworms cow 4 eatsgrass isawesome makesmilk goesmoo sheep 1 eatsgrass goat 2 makesmilk eatsgrass
输出:
3
说明:
在这个例子中，Elsie可能在对话中获得3个“是”的回答（题目中的例子），并且不可能进行包含超过3个“是”的回答的对话。C++14(g++5.4) 解法, 执行用时: 32ms, 内存消耗: 748K, 提交时间: 2020-05-23 22:32:58
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string animal;//存动物名
string p[101][101];//相同动物，特征存在一行
int num[101];//存每个动物的特征数
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>animal;
cin>>num[i];
for(int j=1;j<=num[i];++j){
cin>>p[i][j];
}
sort(p[i]+1,p[i]+num[i]+1);
}
int ans=0;
for(int i=1;i<n;++i)
for(int j=i+1;j<=n;++j)
{
int an=0;
for(int x=1,y=1;x<=num[i];++x)
{
while(p[i][x]>p[j][y]&&y<=num[j])++y;
if(p[i][x]==p[j][y])++an;
}
ans=ans>an?ans:an;
}
cout<<ans+1;
return 0;
}
Python3(3.5.2) 解法, 执行用时: 632ms, 内存消耗: 3832K, 提交时间: 2019-09-03 17:44:31
def com(a, b):
a = sorted(a)
b = sorted(b)
s = [i for i in a if i in b]
return len(s)
def fun():
n = int(input())
if n == 1:
print(1)
return
values = []
for i in range(n):
row = input().strip().split(' ')
values.append(row[2:])
max_same = 0
for i in range(len(values) - 1):
for j in range(i+1, len(values)):
l = com(values[i], values[j])
if max_same < l:
max_same = l
print(max_same + 1)
fun()
C++11(clang++ 3.9) 解法, 执行用时: 24ms, 内存消耗: 744K, 提交时间: 2019-07-20 15:38:57
#include<bits/stdc++.h>
using namespace std;
int n,k[105],ans=0,r;
string m[105],p[105][105];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>m[i];
scanf("%d",&k[i]);
for(int j=1;j<=k[i];j++) cin>>p[i][j];
sort(p[i]+1,p[i]+k[i]+1);
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
r=0;
for(int x=1,y=1;x<=k[i];x++){
while(p[j][y]<p[i][x]&&y<=k[j]) y++;
if(p[j][y]==p[i][x]) r++;
}
ans=max(ans,r+1);
}
}
printf("%d\n",ans);
return 0;
}
pypy3(pypy3.6.1) 解法, 执行用时: 60ms, 内存消耗: 19568K, 提交时间: 2020-12-07 00:00:13
#!/usr/bin/env python3 # # Guess the Animal # import sys, os, math n = int(input()) a = [] for _ in range(n): s = set() for x in input().split()[2:]: s.add(x) a.append(s) c = 0 for i in range(len(a)): for j in range(i + 1, len(a)): c = max(c, len(a[i].intersection(a[j]))) print(c + 1)