HBC24063小飞机,语言题[USACO 2019 Jan B]Guess the Animal题解（奶牛bessie和朋友elsie的猜动物游戏）

人生如戏算法基础篇 2023-11-09 11:23:02 24 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

奶牛Bessie和她的朋友Elsie厌倦了她们的坚果壳游戏，她们想要玩另一个叫做“猜动物”的常见游戏，游戏开始时，Bessie会想好一种动物，随后Elsie会通过问一些问题来猜出Bessie选择的动物，每个问题都是询问这种动物是否具有某个特定的特征，Bessie对于每个问题回答“是”或“不是”，例如： Elsie：“这种动物是能飞的吗？”

奶牛Bessie和她的朋友Elsie厌倦了她们的坚果壳游戏，她们想要玩另一个叫做“猜动物”的常见游戏。游戏开始时，Bessie会想好一种动物（大部分时候，她想的都是奶牛，这使得游戏相当无聊，但是偶尔Bessie也能有些新意，想一些别的）。随后Elsie会通过问一些问题来猜出Bessie选择的动物。每个问题都是询问这种动物是否具有某个特定的特征，Bessie对于每个问题回答“是”或“不是”。例如： Elsie：“这种动物是能飞的吗？” Bessie：“不是。” Elsie：“这种动物是吃草的吗？” Bessie：“是。” Elsie：“这种动物是能产奶的吗？” Bessie：“是。” Elsie：“这种动物是会哞哞叫的吗？” Bessie：“是。” Elsie：“这样的话我想这种动物是奶牛。” Bessie：“猜对了！” 如果我们将所有具备符合Elsie到目前为止所提出的问题的特征的动物的集合称为“可行集”，那么Elsie会持续进行提问直到可行集仅包含一种动物，然后她会把这种动物作为她的答案。对于每个问题，Elsie会选择某种动物的一个特征进行询问（即使这个特征并不能进一步帮助她缩小可行集）。她不会关于同一个特征询问两次。给定Bessie和Elsie知道的所有动物以及它们的特征，请求出Elsie在猜出正确的动物之前能够得到的“是”的回答的最大数量。