暴力枚举题：PIPI的推理游戏

水深无声 2023-10-06 19:24 2阅读 0赞

## 暴力枚举题：PIPI的推理游戏 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 思路： ####

若对说谎的人进行枚举，则问题将会变得很复杂。注意到n个发言人中只有1个凶手，因此我们需对凶手进行枚举，而对于今天是星期几，只有7种情况，也可进行枚举。因此我们枚举凶手以及今天是星期几，判断说谎的人数，若说谎的人数为m个，则假设成立。 注意一直说废话的人也可以是说谎的人  
![在这里插入图片描述][a993a6914fa94aab826d4b0f994926a3.png]

**需注意的点** :

*  使用数组存储发言人，List< String >\[\]存储每个人的发言，使用map存储发言人和编号的映射，编号即对应上述两个数组的下标
 *  枚举凶手和星期几，并遍历每个人的发言，使用三个set：truePeople，falsePeople，unKnown分别表示说真话的人集合，说谎的人集合，说废话的人集合。根据每个人的发言将其置入三个集合中的一个，若某个人既说真话又说假话（即已在说真话集合中但当前遍历到的发言为假，或已在假话集合中但当前遍历到的发言为真），则当前枚举的情况不成立，继续下一次枚举。若判断某人为说真话或假话，而之前该发言人已被加入说废话的人集合，则需将他从说废话的人集合中去除，因为已经明确他发言的类型（真或假）
 *  遍历完所有人的发言后，若说谎话的人集合大小=m，或集合大小<m，但加上说废话的人集合大小>=m，则当前枚举情况成立（说废话的人也可认为为说谎）
 *  使用String ans保存真正的凶手，初值为""，若当前枚举情况成立，则需将当前枚举的凶手赋给ans，此时判断ans的情况，若ans不为初值，则ans已被赋值，这时还需判断ans是否等于当前枚举的凶手，若ans不为初值，且不等于当前枚举的凶手（因为枚举凶手时，进行了星期几的遍历，因此当前枚举凶手在之前日期的遍历中可能已被赋给ans），则有多个可能凶手，输出Not sure。 若ans为初值，则将凶手赋给ans。在枚举完所有情况后，判断ans是否为初值，若是，则无解，输出-1，否则输出ans
 *  注意存在误导性输入，比如XXX is guilty.XXX is not guilty.Today is XXX.这三种情况，XXX可能并非发言人或星期几，这时发言属于废话。在判断这三种发言格式时，需要判断XXX是否为发言人或星期几，若不是，则发言属于废话。

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static Map<String, Integer> map = new HashMap<>();
        static Set<String> set = new HashSet<>();
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String today, man;
            String[] weekDay = {
        "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
            String guilty;
            Set<String> unKnown = new HashSet<>();
            Set<String> truePeople = new HashSet<>();
            Set<String> falsePeople = new HashSet<>();
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int q = scanner.nextInt();
            String[] people = new String[22];
            int i, j, k, p;
            int fail = 0;
            scanner.nextLine();
            String str;
            List<String>[] sentence = new List[22];
            String[] ss;
            String ans = "";
            for (i = 0;i < weekDay.length;i++) {
        
                set.add(weekDay[i]);
            }
            for (i = 0;i < n;i++) {
        
                str = scanner.nextLine();
                people[i] = str;
                map.put(str, i);
            }
            for (i = 0;i < 22;i++) {
        
                sentence[i] = new ArrayList<>();
            }
            for (i = 0;i < q;i++) {
        
                ss = scanner.nextLine().split(": ");
                sentence[map.get(ss[0])].add(ss[1]);
            }
            for (i = 0;i < n;i++) {
        
                guilty = people[i];
                for (j = 0;j < weekDay.length;j++) {
        
                    truePeople.clear();
                    falsePeople.clear();
                    unKnown.clear();
                    today = weekDay[j];
                    // 按people中的人的顺序遍历发言
                    for (k = 0;k < n && fail == 0;k++) {
        
                        man = people[k];
                        for (p = 0;p < sentence[k].size();p++) {
        
                            str = sentence[k].get(p);
                            if(!check(str, today, man, guilty, truePeople, falsePeople, unKnown)) {
        
                                fail = 1;
                                break;
                            }
                        }
                    }
                    if (fail == 1) {
        
                        fail = 0;
                        continue;
                    }
                    if (falsePeople.size() <= m && falsePeople.size() + unKnown.size() >= m) {
        
                        if (!"".equals(ans) && !ans.equals(guilty)) {
        
                            System.out.println("Not sure");
                            return;
                        }
                        ans = guilty;
                    }
                }
            }
            if (!"".equals(ans)) {
        
                System.out.println(ans);
                return;
            }
            System.out.println(-1);
        }
    
        static boolean check(String str, String today, String man, String guilty, Set<String> truePeople, Set<String> falsePeople, Set<String> unKnown) {
        
            String who, sayToday;
            if ("I am guilty.".equals(str)) {
        
                return sayTruth(guilty, null, null, man, man, truePeople, falsePeople, unKnown);
            } else if ("I am not guilty.".equals(str)) {
        
                return sayFalse(guilty, man, man, truePeople, falsePeople, unKnown);
            } else if (str.endsWith(" is guilty.") && map.get(str.substring(0, str.indexOf(" "))) != null) {
        
                who = str.substring(0, str.indexOf(" "));
                return sayTruth(guilty, null, null, man, who, truePeople, falsePeople, unKnown);
            } else if (str.endsWith(" is not guilty.") && map.get(str.substring(0, str.indexOf(" "))) != null) {
        
                who = str.substring(0, str.indexOf(" "));
                return sayFalse(guilty, man, who, truePeople, falsePeople, unKnown);
            } else if (str.startsWith("Today is ") && set.contains(str.substring(9, str.length() - 1))) {
        
                sayToday = str.substring(9, str.length() - 1);
                return sayTruth(null, today, sayToday, man, null, truePeople, falsePeople, unKnown);
            } else {
        
                if (!unKnown.contains(man)) {
        
                    unKnown.add(man);
                }
            }
            return true;
        }
    
        static boolean sayTruth(String guilty, String today, String sayToday, String man, String who, Set<String> truePeople, Set<String> falsePeople, Set<String> unKnown) {
        
            if (sayToday == null) {
        
                if (who.equals(guilty)) {
        
                    if (falsePeople.contains(man)) {
        
                        return false;
                    }
                    truePeople.add(man);
                } else {
        
                    if (truePeople.contains(man)) {
        
                        return false;
                    }
                    falsePeople.add(man);
                }
            } else {
        
                if (today.equals(sayToday)) {
        
                    if (falsePeople.contains(man)) {
        
                        return false;
                    }
                    truePeople.add(man);
                } else {
        
                    if (truePeople.contains(man)) {
        
                        return false;
                    }
                    falsePeople.add(man);
                }
            }
            if (unKnown.contains(man)) {
        
                unKnown.remove(man);
            }
            return true;
        }
    
        static boolean sayFalse(String guilty, String man, String who, Set<String> truePeople, Set<String> falsePeople, Set<String> unKnown) {
        
            if (who.equals(guilty)) {
        
                if (truePeople.contains(man)) {
        
                    return false;
                }
                falsePeople.add(man);
            } else {
        
                if (falsePeople.contains(man)) {
        
                    return false;
                }
                truePeople.add(man);
            }
            if (unKnown.contains(man)) {
        
                unKnown.remove(man);
            }
            return true;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1cbd4712a6e14b9c811521b72395f475.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/7d3d6a7b12fd49a08a0c2576ec8fa50a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/4c0ed1aff9f54effbb3e21070d09f818.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[a993a6914fa94aab826d4b0f994926a3.png]: https://img-blog.csdnimg.cn/a993a6914fa94aab826d4b0f994926a3.png