題目描述

當奶牛貝茜和她的朋友艾爾西玩膩了常見的貝殼游戲后，她們喜歡玩另一個經典游戲"猜動物"。

游戲開始時，貝茜會在心中選定一種動物（大多數時候她都會選奶牛，這讓游戲變得相當無聊，不過偶爾貝茜也會發揮創意選擇其他動物）。接著艾爾西通過提出一系列問題來推斷貝茜選擇的動物。每個問題都會詢問該動物是否具有某種特定特征，貝茜則用"是"或"否"來回答。例如：

艾爾西：“這種動物會飛嗎？”
貝茜：“不會”
艾爾西：“這種動物吃草嗎？”
貝茜：“吃”
艾爾西：“這種動物產奶嗎？”
貝茜：“產”
艾爾西：“這種動物會哞哞叫嗎？”
貝茜：“會”
艾爾西：“那我猜這是頭奶牛。”
貝茜：“答對了！”

如果我們把"候選集合"定義為當前所有符合艾爾西已提問特征的動物集合，那么艾爾西會持續提問，直到候選集合只剩一種動物，這時她就會宣布答案。每個問題中，艾爾西會從候選集合中某個動物的特征里選取提問（即使這個特征可能無法進一步縮小候選范圍）。她絕不會重復詢問同一個特征。

已知貝茜和艾爾西了解的所有動物及其特征，請計算在確定正確答案前，艾爾西可能獲得的最大"是"回答次數。

輸入格式

第一行輸入動物數量 ($2\le N\le 100$)。

接下來 $N$ 行，每行描述一個動物，格式為：動物名稱開頭，接著一個整數 ($1\le K\le 100$)，然后是 $K$ 個該動物的特征。

動物名稱和特征都是由不超過 $20$ 個小寫字母 (a..z) 組成的字符串。任意兩個動物的特征組合都不會完全相同。

輸出格式

輸出一個整數，表示游戲結束前艾爾西可能獲得的最大"是"回答次數。

輸入輸出樣例

輸入 #1

4
bird 2 flies eatsworms
cow 4 eatsgrass isawesome makesmilk goesmoo
sheep 1 eatsgrass
goat 2 makesmilk eatsgrass

輸出 #1

3

樣例說明

在這個樣例中，艾爾西最多能獲得 $3$ 次"是"的回答（如上文對話所示），無法獲得超過 $3$ 次的"是"回答。

提交鏈接

Guess the Animal

思路分析

關鍵觀察：最多“是”回答的情況是：她先問某一對動物共有的所有特征（每個都答“是”，但這兩個動物仍都在候選集合里），然后再問一個只屬于其中一個的額外特征得到最后一個“是”使候選集合縮到唯一。

因此：答案 = 任意一對動物之間共有特征數的最大值 + 1。

1. 枚舉所有動物對

   對于所有 $i<j$ 的動物對（即每一對不同動物），計算它們之間的共有特征數。

   具體做法是：對第 $i$ 只動物的每個特征 $it$，再和第 $j$ 只動物的每個特征 $is$ 逐一比較，相等時計數 $same++$。

2. 維護最大共有特征

   每對算出的共有特征數 $same$ 和當前記錄的最大 $Mx$ 比較，取較大者。

   循環結束后，$Mx$ 就是任意一對動物之間共有特征數的最大值。

3. 輸出最終答案

   輸出 $Mx+1$，即在最糟情況下能得到的最多“是”回答次數。

時間復雜度：$O(n^2?K^2)$

參考代碼：

#include <bits/stdc++.h>
using namespace std;int main()
{// freopen("guess.in", "r", stdin);// freopen("guess.out", "w", stdout);int n, mx = 0, id;cin >> n;vector<int> k(n + 1);vector<string> animal(n + 1);vector<vector<string>> Te(n + 1);map<string, int> mp;for (int i = 1; i <= n; i++){cin >> animal[i]; // 動物的名字cin >> k[i];	  // k個特征for (int j = 0; j < k[i]; j++){string s;cin >> s; // 每一個特征Te[i].push_back(s); // 第i個動物的每一個特征}}int Mx = 0;//求任意兩個動物之間的共同特征for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){int same = 0;for(auto it : Te[i])for(auto is : Te[j])if(it == is)same++;Mx = max(Mx , same);}}cout << Mx + 1;return 0;
}