[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-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!