[AcWing 258] 石头剪刀布
2022/8/16 23:29:46
本文主要是介绍[AcWing 258] 石头剪刀布,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
带扩展域的并查集
点击查看代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 10; int n, m; int p[N]; struct Node { int a, b; char op; } s[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void merge(int a, int b) { int pa = find(a), pb = find(b); p[pa] = pb; } bool same(int a, int b) { return find(a) == find(b); } bool check(int a, int b, char c) { if (c == '=') { if (same(a, b + n) || same(a + n, b)) return false; merge(a, b); merge(a + n, b + n); merge(a + n + n, b + n + n); } else if (c == '>') { if (same(a, b) || same(a + n, b)) return false; merge(a, b + n); merge(a + n, b + n + n); merge(a + n + n, b); } else { if (same(a, b) || same(a, b + n)) return false; merge(a + n, b); merge(a + n + n, b + n); merge(a, b + n + n); } return true; } void solve() { while (cin >> n >> m) { for (int i = 1; i <= m; i ++) { int a, b; char op; cin >> a >> op >> b; s[i] = {a, b, op}; } // 记录裁判的个数 int cnt = 0; // 记录裁判的编号 int res = 0; // 记录得到裁判信息的行号 int the_line = 0; // 假设编号为 t 的人是裁判 for (int t = 0; t < n; t ++) { // 每次都要将集合初始化 for (int i = 0; i < 3 * n; i ++) p[i] = i; bool is_ok = true; for (int i = 1; i <= m; i ++) { auto& [a, b, op] = s[i]; // 将裁判跳过 if (a == t || b == t) continue; // 检查是否合法,合法则合并集合,不会进入if中 if (!check(a, b, op)) { // 不合法才会进入 is_ok = false; // 其他人不是裁判的最大轮数 if (the_line <= i) the_line = i; break; } } if (is_ok) { res = t; cnt ++; } } if (!cnt) printf("Impossible\n"); else if (cnt > 1) printf("Can not determine\n"); else printf("Player %d can be determined to be the judge after %d lines\n", res, the_line); } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
- 判断裁判的思路
先假设一定存在裁判,枚举把每个人当作裁判,然后将包含他的数据跳过,判断其他数据是否会推出矛盾,如果没有矛盾,则说明这个人可能是裁判,就把 \(cnt + 1\),考虑以下几种情况:
① 如果没有裁判,
② 如果只有一位裁判,那么只有当枚举到把他当作裁判时,其他数据才会没有矛盾,\(cnt + 1\) 只会执行一次,最终 \(cnt = 1\)
③ 如果有裁判,但是不能确定哪个是裁判,那么有多个人选,把他当作裁判时,其他数据没有矛盾,\(cnt + 1\) 会执行超过一次,\(cnt > 1\) - 扩展域
对于 \(a\) 号小朋友,\(a\) 代表该小朋友出的是石头,\(a + n\) 代表该小朋友出的是剪刀,\(a + n + n\) 代表该小朋友出的是布 - 最早的找到裁判的时间 \(\Leftrightarrow\) 判断出除他以外的人都不是裁判的时间 \(\Leftrightarrow\) 判断出其他人不是裁判的时间的最大值
这篇关于[AcWing 258] 石头剪刀布的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25安卓NDK 是什么?-icode9专业技术文章分享
- 2024-12-25caddy 可以定义日志到 文件吗?-icode9专业技术文章分享
- 2024-12-25wordfence如何设置密码规则?-icode9专业技术文章分享
- 2024-12-25有哪些方法可以实现 DLL 文件路径的管理?-icode9专业技术文章分享
- 2024-12-25错误信息 "At least one element in the source array could not be cast down to the destination array-icode9专业技术文章分享
- 2024-12-25'flutter' 不是内部或外部命令,也不是可运行的程序 或批处理文件。错误信息提示什么意思?-icode9专业技术文章分享
- 2024-12-25flutter项目 as提示Cannot resolve symbol 'embedding'提示什么意思?-icode9专业技术文章分享
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享