即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

ZOJ Problem Set – 3960―What Kind of Friends Are You?

编程语言 qq_37763006 7℃ 0评论
Time Limit: 1 Second      Memory Limit: 65536 KB
Japari Park is a large zoo home to extant species, endangered species, extinct species, cryptids and some legendary creatures. Due to a mysterious substance known as Sandstar, all the animals have become anthropomorphized into girls known as Friends.
Kaban is a young girl who finds herself in Japari Park with no memory of who she was or where she came from. Shy yet resourceful, she travels through Japari Park along with Serval to find out her identity while encountering more Friends along the way,
and eventually discovers that she is a human.
However, Kaban soon finds that it’s also important to identify other Friends. Her friend, Serval, enlightens Kaban that she can use some questions whose expected answers are either “yes” or “no” to identitfy a kind of Friends.
To be more specific, there are n Friends need to be identified. Kaban will ask each of them q same questions and collect their answers. For each question, she also gets a full list of animals’ names that will give a “yes” answer to that question (and those
animals who are not in the list will give a “no” answer to that question), so it’s possible to determine the name of a Friends by combining the answers and the lists together.
But the work is too heavy for Kaban. Can you help her to finish it?
Input
There are multiple test cases. The first line of the input is an integer T (1 ≤ T ≤ 100), indicating the number of test cases. Then T test cases follow.
The first line of each test case contains two integers n (1 ≤ n ≤ 100) and q (1 ≤ q ≤ 21), indicating the number of Friends need to be identified and the number of questions.
The next line contains an integer c (1 ≤ c ≤ 200) followed by c strings p1, p2, … , pc (1 ≤ |pi| ≤ 20), indicating all known names of Friends.
For the next q lines, the i-th line contains an integer mi (0 ≤ mi ≤ c) followed by mi strings si, 1, si, 2, … , si, mi (1 ≤ |si, j| ≤ 20), indicating the number of Friends and their names, who will give a “yes” answer to the i-th question. It’s guaranteed
that all the names appear in the known names of Friends.
For the following n lines, the i-th line contains q integers ai, 1, ai, 2, … , ai, q (0 ≤ ai, j ≤ 1), indicating the answer (0 means “no”, and 1 means “yes”) to the j-th question given by the i-th Friends need to be identified.
It’s guaranteed that all the names in the input consist of only uppercase and lowercase English letters.
Output
For each test case output n lines. If Kaban can determine the name of the i-th Friends need to be identified, print the name on the i-th line. Otherwise, print “Let’s go to the library!!” (without quotes) on the i-th line instead.
Sample Input
2
3 4
5 Serval Raccoon Fennec Alpaca Moose
4 Serval Raccoon Alpaca Moose
1 Serval
1 Fennec
1 Serval
1 1 0 1
0 0 0 0
1 0 0 0
5 5
11 A B C D E F G H I J K
3 A B K
4 A B D E
5 A B K D E
10 A B K D E F G H I J
4 B D E K
0 0 1 1 1
1 0 1 0 1
1 1 1 1 1
0 0 1 0 1
1 0 1 1 1
Sample Output
Serval
Let’s go to the library!!
Let’s go to the library!!
Let’s go to the library!!
Let’s go to the library!!
B
Let’s go to the library!!
K
Hint
The explanation for the first sample test case is given as follows:
As Serval is the only known animal who gives a “yes” answer to the 1st, 2nd and 4th question, and gives a “no” answer to the 3rd question, we output “Serval” (without quotes) on the first line.
As no animal is known to give a “no” answer to all the questions, we output “Let’s go to the library!!” (without quotes) on the second line.
Both Alpaca and Moose give a “yes” answer to the 1st question, and a “no” answer to the 2nd, 3rd and 4th question. So we can’t determine the name of the third Friends need to be identified, and output “Let’s go to the library!!” (without quotes) on the
third line.

1、题意:大概意思可以理解输入一串人名,然后再输入哪个题谁能回答上来,然后再输入回答这些题的一种情况―哪道题能答对或者答错,答对为1答错为0,然后输出符合这种情况的人名,如果没有符合的或者大于等于2个人符合则输出Let’s go to the library!。
2、思路:第一次做的时候我是想让每个人的回答问题的情况都构成一个数,例如当小明回答问题的情况为1 0 1 1 0的时候,与他符合的数就是10110;然后当输入情况的时候也是组成一个数,直接比较就行了,结果不知道是哪里考虑不全面或者这种方法有缺陷一直Wrong……然后有用第二种方法,就是将每个人的答题情况都存到数组里,然后直接一个个的和输入的答案比较,结果一遍就过了…
3、代码:
#include
#include
#include
using namespace std;
char name[201][30];
int sname[201][300];
int answer[300];
char yes[30];
int main()
{
int i,j,k,t,T,n,q,c,m,out,tm,cs;
double sum;
cin>>T;
while(T--)
    {
    cin>>n>>q;
    cin>>c;
    memset(sname,0,sizeof(sname));
    for(i=0;i>name[i];  
    for(i=0;i>m;    
        for(j=0;j>yes; 
            for(k=0;k>answer[j];  
         for(k=0;k

4、其实这道题用最简单的方法挺容易做的,结果想取巧用别的方法做一直错...




转载请注明:CodingBlog » ZOJ Problem Set – 3960―What Kind of Friends Are You?

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情