长生的梦呓


  • 归档
  • 算法
  • 基础
  • 关于

  • 分类
  • 日志
  • Servlet
  • Archive
  • 数据结构
  • IO 流

  • 标签
  • 友链
  • MyBatis
  • About
  • Spring 5
  • Java SE
  • Java EE
  • Algorithms
  • 新特性
  • 位运算技巧

  • 搜索
内网穿透 项目实战 数据库 MySQL 安卓踩坑 开发工具 设计模式 Enum 枚举 Linux MyBatis-plus JSON IDEA Transactions AOP IO 流 DP IoC 与 DI 位运算技巧 工具类 学习技巧 Git JDK 排序 Spring Boot Spring MVC Spring Framework MyBatis Log4J Regex Jsoup JDBC 数据结构 递推 递归 算法 Servlet与JSP 小难 中等 简单

【ZOJ】3960.What Kind of Friends Are You

发表于 2020-04-06 | 1 | 阅读次数 239

一、题目

原题链接:https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370087

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.

二、AC代码

题目意思我看了好久。。。

其他的就是找合适的容器存数据了,可以用数组,也可以用集合(个人比较喜欢用集合)。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 3960.What Kind of Friends Are You?
 *
 * @author ChangSheng
 * @date 2020-04-06
 */
public class P3960_AC_What_Kind_of_Friends_Are_You {
    public static void main(String[] args) throws IOException {
        int T = Reader.nextInt();
        for (int i = 0; i < T; i++) {
            int n = Reader.nextInt(), q = Reader.nextInt();
            // 5 Serval xxx
            int c = Reader.nextInt();
            String[] p = new String[c];
            for (int j = 0; j < c; j++) {
                p[j] = Reader.next();
            }
            // q个问题,回答yes的人数
            List<String>[] yesNames = new List[q];
            for (int j = 0; j < q; j++) {
                // 读取前面的数
                int yesCount = Reader.nextInt();
                yesNames[j] = new ArrayList<>(yesCount);
                for (int k = 0; k < yesCount; k++) {
                    yesNames[j].add(Reader.next());
                }
            }
            // 重复多次的,需要排除
            List<String> exclude = new ArrayList<>();
            // 获取5 Serval xxx中所有值,1101...
            Map<String, String> all = new HashMap<>(c);
            for (int j = 0; j < c; j++) {
                String s = "";
                for (int k = 0; k < yesNames.length; k++) {
                    List<String> line = yesNames[k];
                    if (line.contains(p[j]))  s+="1";
                    else s+="0";
                }
                if (all.containsKey(s)) exclude.add(s);
                all.put(s, p[j]);
            }
            for (String s : exclude) {
                if (all.containsKey(s)) all.remove(s);
            }
            // n 个人
            for (int j = 0; j < n; j++) {
                String s = "";
                for (int k = 0; k < q; k++) {
                    s += Reader.nextInt();
                }
                String ans = "Let's go to the library!!";
                if (all.containsKey(s)) ans = all.get(s);
                System.out.println(ans);
            }
        }
    }

    /** 快速输入类 */
    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");
        /** 获取下一段文本 */
        static String next() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }
        static int nextInt() throws IOException {
            return Integer.parseInt( next() );
        }
        static double nextDouble() throws IOException {
            return Double.parseDouble( next() );
        }
    }
}
  • 本文作者: 长生的梦呓
  • 本文链接: https://shengjava.com/archives/zoj3960whatkindoffriendsareyou
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 内网穿透 # 项目实战 # 数据库 # MySQL # 安卓踩坑 # 开发工具 # 设计模式 # Enum # 枚举 # Linux # MyBatis-plus # JSON # IDEA # Transactions # AOP # IO 流 # DP # IoC 与 DI # 位运算技巧 # 工具类 # 学习技巧 # Git # JDK # 排序 # Spring Boot # Spring MVC # Spring Framework # MyBatis # Log4J # Regex # Jsoup # JDBC # 数据结构 # 递推 # 递归 # 算法 # Servlet与JSP # 小难 # 中等 # 简单
【ZOJ】3959.Problem Preparation
Java 快速输入输出
  • 文章目录
  • 站点概览
长生的梦呓

长生的梦呓

110 日志
39 分类
40 标签
RSS
E-mail CSDN
Creative Commons
Links
  • CSDN 地址
  • waltz26
  • Ryan Wang's Blog
  • JohnNiang's Blog
  • 廖雪峰
  • 菜鸟教程
© 2021 长生的梦呓
浙ICP备20005262号-1