P9220 「TAOI-1」椎名真昼

P9220 「TAOI-1」椎名真昼

考点:博弈论、拓扑、强连通分量

难度: 提高+/省选-

题意

​ Alice 和 Bob 玩游戏,给定一个有向图,每个点有初始颜色(黑/白)。

​ 双方轮番操作一次,Alice 先手,每次操作选定一个结点,从这个点开始,能到达的点(包含自身)颜色翻转。如果某次操作后所有结点皆为白色,进行该次操作的人获胜。

​ 假设双方都采用策略使得自己胜利,或者如果自己无法胜利,使得对方无法胜利。

​ 给定节点的初始值,求出最终的胜者,亦或者,没有胜者。

n n n 个点, n ≤ 1 0 5 n \le 10^5 n105 m m m 条边, m ≤ 2 × 1 0 5 m \le 2 \times 10^5 m2×105,T 组数组, T ≤ 15 T \le 15 T15

分析

经典的 博弈类型 问题。

​ 首先,如果这个游戏无法在两步及以内结束的话,就可以直接算 平局。因为若是超过两步,认为自己会输的那一方将会想尽办法不让你赢,具体表现就是重复另一方先前的操作,让图变为另一方操作前的状态,最终陷入死循环。因此我们 只需关注一步定胜负和两步定胜负 的情况。

​ 根据题目中对两点能互相到达的定义,我们很容易知道 – 若对某个 SCC 中的点进行一次操作,那么同处于这个 SCC 的其他点的颜色也都会翻转(但不止这些点的颜色被翻转)。这启发我们处理出原图中的所有强连通分量。

平局:此时不难发现,如果某个 SCC 中存在异色点,那么无论怎么翻转,它们都不会变为统一颜色,于是这种情况可以直接判成平局,否则我们就把这个强连通分量染成内部点的颜色。

在这里插入图片描述

缩点:处理出所有的强连通分量后,我们再把一个强连通分量整体看作一个新点,建在新图上(即缩点),此时新图必定是一个有向无环图 DAG。那么如果在某个强连通分量中的某个点上进行操作,新图中该强连通分量的子节点一定也会受到影响从而变化颜色。至此我们便理清了操作与颜色翻转之间的规律。

在这里插入图片描述

在这里插入图片描述

必胜:因为游戏不会超过两轮,而且先手的 Alice 想要获胜,她就必须在第一轮胜利否则要么 Bob 胜要么平局。也因此,在新建的有向无环图上,有且 仅能存在一个节点(黑色节点为根),使得它的子树包含新图中所有的黑色 SCC,且不包含任何白色 SCC。这样一来先手 Alice 才能一次把这些黑色点转化成白色从而获胜。如果这个子树不完全是黑色 SCC,或者是存在多个节点满足要求,都不能保证 Alice 获胜(但也不代表必输,因为还存在平局)。

在这里插入图片描述

再来看 Bob 这边,他如果想要获胜,就只能抓住第二轮这唯一的机会。有三种可能性:

  1. 全图均为白色节点。这样 Alice 只能选择白色节点染黑,此时 Bob 只需重复她的操作即可恢复全图到全白的状态。

在这里插入图片描述

  1. 仅有两个孤立的黑色 SCC。此时 Alice 选择其一染白,Bob 仅需染白另一个即可。

在这里插入图片描述

  1. 一个白色 SCC 和一个黑色 SCC,并且仅有一条有向边从黑点指向白点。此时无论 Alice 开局选择染哪个点,Bob 总能在第二轮把全图染成白色而获胜。

在这里插入图片描述

其他情况即为二人平局

参考代码

#include <bits/stdc++.h>
#define ll long longconst int N = 100010, M = 200010;
// 原图、缩点后新图边集数组
int h1[N], h2[N], tot1, tot2;
int ne1[M], ne2[M], to1[M], to2[M];
// scc 个数、dfs_cnt = dfn序的结点编号
int scc_cnt = 0, dfs_cnt = 0;
int dfn[N], low[N]; // tarjan()
int scc_id[N];
std::vector<int> scc[N]; // scc 缩点编号
std::stack<int> stk;     // 栈
bool st[N];
bool in_stk[N];              // 压栈 scc
bool color[N], scc_color[N]; // 颜色, scc 缩点新图颜色
int deg[N];                  // topo 入度数组void add_edge(int u, int v)
{to1[tot1] = v, ne1[tot1] = h1[u], h1[u] = tot1++;
}void add_scc_edge(int u, int v)
{to2[tot2] = v, ne2[tot2] = h2[u], h2[u] = tot2++;
}void init()
{tot1 = tot2 = 0;while (!stk.empty())stk.pop();for (int i = 1; i <= scc_cnt; i++)scc[i].clear();scc_cnt = dfs_cnt = 0;memset(h1, -1, sizeof h1), memset(h2, -1, sizeof h2);memset(st, false, sizeof st), memset(scc_id, 0, sizeof scc_id);memset(dfn, 0, sizeof dfn), memset(low, 0, sizeof low);memset(in_stk, false, sizeof in_stk), memset(deg, 0, sizeof deg);memset(to1, 0, sizeof to1), memset(to2, 0, sizeof to2);memset(ne1, 0, sizeof ne1), memset(ne2, 0, sizeof ne2);
}bool tarjan(int u)
{low[u] = dfn[u] = ++dfs_cnt; // 盖戳、进栈stk.push(u), in_stk[u] = true;for (int i = h1[u]; ~i; i = ne1[i]){int v = to1[i];if (!dfn[v]){tarjan(v);low[u] = std::min(low[v], low[u]);}else if (in_stk[v])low[u] = std::min(low[u], dfn[v]);}if (dfn[u] == low[u]){scc_cnt++; // 连通分量scc个数增加int t;do{t = stk.top();stk.pop();in_stk[t] = false;         // 取消标记scc_id[t] = scc_cnt;       // 每个点对应的 scc 编号scc[scc_cnt].push_back(t); // 维护 scc 点集} while (t != u);// 如存在 scc 内异色点,即无解(平局) - 打个擂台,判不同for (int i = 1; i < scc[scc_cnt].size(); i++)if (color[scc[scc_cnt][i]] ^ color[scc[scc_cnt][i - 1]])return false;scc_color[scc_cnt] = color[scc[scc_cnt][0]]; // 同色,给 scc 染色}return true;
}// topo 找 DAG 上第一个黑色 scc
int getFirstBlack()
{std::queue<int> q;for (int i = 1; i <= scc_cnt; i++)if (!deg[i])q.push(i);while (q.size()){int u = q.front();q.pop();if (scc_color[u])return u; // 首个黑色for (int i = h2[u]; ~i; i = ne2[i]){int v = to2[i];if (--deg[v] == 0)q.push(v);}}return 0; // 找不到返回 0 说明不存在黑色点
}// 检查以黑色点 u 为根的子树中是否有混有白色
bool dfs(int u)
{bool ret = scc_color[u]; // 取点颜色st[u] = true;            // 标记该点已访问for (int i = h2[u]; ~i; i = ne2[i]){int v = to2[i];if (st[v])continue;ret &= dfs(v);}return ret;
}// 检测 scc 集,是否只包含黑色 scc
bool check()
{for (int i = 1; i <= scc_cnt; i++)if (scc_color[i] && !st[i]) // 子树必须包含新图的所有黑色 sccreturn false;return true;
}int main()
{std::ios::sync_with_stdio(false), std::cin.tie(nullptr);int t, m, n;std::cin >> t;while (t--){init();std::cin >> n >> m;for (int i = 1; i <= n; i++)std::cin >> color[i];for (int i = 1, u, v; i <= m; i++)std::cin >> u >> v, add_edge(u, v); // 有向图// std::cout << n << " " << m << std::endl;// 平局bool flag = true;for (int i = 1; i <= n; i++)if (!dfn[i])if (!tarjan(i)){flag = false; // scc 中存在异色结点,判无解(平局)std::cout << "N";break;}if (!flag)continue;bool flag_3 = true; // Bob 情况3: 一白一黑,且黑->白for (int i = 1; i <= scc_cnt; i++){for (int u : scc[i]){for (int j = h1[u]; ~j; j = ne1[j]){int v = to1[j];if (scc_id[u] != scc_id[v]){add_scc_edge(scc_id[u], scc_id[v]);                      // 缩点建图flag_3 &= !scc_color[scc_id[v]] && scc_color[scc_id[u]]; // 存在一黑一白,检查是否是黑点指向白点( bob 情况 3 判断) 1->0(必须 黑->白 可以画图理解)deg[scc_id[v]]++;                                        // scc 入度++}}}}int start = getFirstBlack();if (dfs(start) && check()) // Alicestd::cout << "A";else if (!start && !color[1])std::cout << "B";else if (scc_cnt == 2 && scc_color[1] & scc_color[2])std::cout << "B";else if (scc_cnt == 2 && flag_3)std::cout << "B";elsestd::cout << "N";}return 0;
}

本文分析参考 链接 然后自建图分析。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/463474.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机网络:网络层 —— 多播路由选择协议

文章目录 多播路由选择协议多播转发树构建多播转发树基于源树的多播路由选择建立广播转发树建立多播转发树 组共享树的多播路由选择基于核心的生成树的建立过程 因特网的多播路由选择协议 多播路由选择协议 仅使用 IGMP 并不能在因特网上进行IP多播。连接在局域网上的多播路由…

例行性工作

1、单一执行------at-----仅处理执行一次就结束了 1.1工作过程 /etc/at.allow&#xff0c;写在该文件的人可以使用at命令/etc/at.deny&#xff0c;黑名单两个文件如果都不存在&#xff0c;只有root能使用 1.2命令详解------命令格式&#xff1a;at [参数] [时间] 2、循环执行…

使用Kafka构建大规模消息传递系统

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用Kafka构建大规模消息传递系统 引言 Kafka 简介 安装 Kafka 创建主题 生产者 消费者 高级特性 分区 持久化 消费者组 消息确认…

【sqlmap使用】

sqlmap简介 sqlmap 目录结构 sqlmap常用参数 sqlmap实现注入 测试注入点&#xff0c;检测到注入点后&#xff0c;直接爆数据库名 python sqlmap.py –u http://172.16.12.2/7/9/strsql.php --data "usernameadmin" --dbs注意sqlmap在使用过程中可能会出现几个需要…

【java】java的基本程序设计结构07-字符串

字符串 1. 创建字符串 最简单的&#xff1a; String str "hello"; 用构造函数创建字符串&#xff1a; String str2new String("hello"); String 创建的字符串存储在公共池中&#xff0c;而 new 创建的字符串对象在堆上&#xff1a; 注意: String 类…

数组排序简介-基数排序(Radix Sort)

基本思想 将整数按位数切割成不同的数字&#xff0c;然后从低位开始&#xff0c;依次到高位&#xff0c;逐位进行排序&#xff0c;从而达到排序的目的。 算法步骤 基数排序算法可以采用「最低位优先法&#xff08;Least Significant Digit First&#xff09;」或者「最高位优先…

w~Transformer~合集8

我自己的原文哦~ https://blog.51cto.com/whaosoft/12419881 #Batch Normalization 本文聚焦于Batch Normalization&#xff0c;Layer Normalization两个标准化方法&#xff0c;对其原理和优势等进行了详细的阐述。 这一篇写Transformer里标准化的方法。在Transformer中&am…

Hadoop——HDFS

什么是HDFS HDFS&#xff08;Hadoop Distributed File System&#xff09;是Apache Hadoop的核心组件之一&#xff0c;是一个分布式文件系统&#xff0c;专门设计用于在大规模集群上存储和管理海量数据。它的设计目标是提供高吞吐量的数据访问和容错能力&#xff0c;以支持大数…

废弃物分类分割系统:入门训练营

废弃物分类分割系统源码&#xff06;数据集分享 [yolov8-seg-C2f-DCNV2-Dynamic&#xff06;yolov8-seg-C2f-DWR等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Glob…

java项目之微服务在线教育系统设计与实现(springcloud)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的闲一品交易平台。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 微服务在线教育系统设计与…

拆换LED灯珠后测量是短路的,为何

今天更换灯珠遇到一个怪事情&#xff0c;拆换一颗好的灯珠上去&#xff0c;万用表测试是短路的。 后面测试电路板上面&#xff0c;中间的散热部分是跟二极管的正极想通的。而且恰恰此时&#xff0c;LED灯珠的散热部分是跟负极想通的。 遂将线路板上面的散热部分跟二极管正极割…

串口屏控制的自动滑轨(未完工)

序言 疫情期间自己制作了一个自动滑轨&#xff0c;基于无线遥控的&#xff0c;但是整体太大了&#xff0c;非常不方便携带&#xff0c;所以重新设计了一个新的&#xff0c;以2020铝型材做导轨的滑轨&#xff0c;目前2020做滑轨已经很成熟了&#xff0c;配件也都非常便宜&#x…

【NOIP提高组】Hankson的趣味题

【NOIP提高组】Hankson的趣味题 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; Hanks 博士是BT (Bio-Tech&#xff0c;生物技术) 领域的知名专家&#xff0c;他的儿子名叫Hankson。现在&#xff0c;刚刚放学回家的Hankson 正在思考一个有趣…

Matlab车牌识别课程设计报告(附源代码)

Matlab车牌识别系统 分院&#xff08;系&#xff09; 信息科学与工程 专业 学生姓名 学号 设计题目 车牌识别系统设计 内容及要求&#xff1a; 车牌定位系统的目的在于正确获取整个图像中车牌的区域&#xff0c; 并识别出车牌号。通过设计实现车牌识别系…

【Unity基础】初识UI Toolkit - 运行时UI

Unity中的UI工具包&#xff08;UI Toolkit&#xff09;不但可以用于创建编辑器UI&#xff0c;同样可以来创建运行时UI。 关于Unity中的UI系统以及使用UI工具包创建编辑器UI可以参见&#xff1a; 1. Unity中的UI系统 2. 初识UI Toolkit - 编辑器UI 本文将通过一个简单示例来…

【重生之我要苦学C语言】深入理解指针4

深入理解指针4 字符指针变量 指针指向字符变量 char ch w; char* p &ch;指针指向字符数组 char arr[10] "abcdef"; char* p arr;printf("%s\n", arr); printf("%s\n", p);结果是一样的 也可以写成&#xff1a; char* p "abc…

Freertos学习日志(1)-基础知识

目录 1.什么是Freertos&#xff1f; 2.为什么要学习RTOS&#xff1f; 3.Freertos多任务处理的原理 1.什么是Freertos&#xff1f; RTOS&#xff0c;即&#xff08;Real Time Operating System 实时操作系统&#xff09;&#xff0c;是一种体积小巧、确定性强的计算机操作系统…

勒索软件通过易受攻击的 Cyber​​Panel 实例攻击网络托管服务器

一个威胁行为者&#xff08;或可能多个&#xff09;使用 PSAUX 和其他勒索软件攻击了大约 22,000 个易受攻击的 Cyber​​Panel 实例以及运行该实例的服务器上的加密文件。 PSAUX 赎金记录&#xff08;来源&#xff1a;LeakIX&#xff09; Cyber​​Panel 漏洞 Cyber​​Pane…

基于vue3和elementPlus的el-tree组件,实现树结构穿梭框,支持数据回显和懒加载

一、功能 功能描述 数据双向穿梭&#xff1a;支持从左侧向右侧转移数据&#xff0c;以及从右侧向左侧转移数据。懒加载支持&#xff1a;支持懒加载数据&#xff0c;适用于大数据量的情况。多种展示形式&#xff1a;右侧列表支持以树形结构或列表形式展示。全选与反选&#xf…

Linux入门-基础指令和权限

1.压缩打包 1.1压缩是什么 压缩是通过特定的算法&#xff0c;使文件减小体积&#xff0c;从而达到节省空间的目的。 1.2.为什么要压缩 a.压缩将文件大小减小&#xff0c;在本地可能不太明显&#xff0c;但是在网络传输中&#xff0c;减小了网络传输的成本。 b.将多个文件压…