当前位置: 首页 > news >正文

[ABC398G] Not Only Tree Game

因为不存在奇环,所以显然构成一个二分图。

我们进行一些变量的定义:

  • \(x\) 表示在满足添加了之后不改变图的联通性且不产生奇环的情况下,可以添加的变数。
  • \(ee\) 表示两侧都是偶数个节点的联通块的数量。
  • \(oo\) 表示两侧都是奇数个节点的联通块的数量。
  • \(eo\) 表示一侧是偶数一侧是奇数的联通块的数量。
  • \(iso\) 表示孤点的数量。

先说结论:

不存在平局的情况,如果先手不赢肯定是后手赢,下面只考虑先手。

如果 \(n\) 是奇数:

先手胜利当且仅当 \(m\) 是奇数。

如果 \(n\) 是偶数:

如果 \(eo=0\),那么先手胜利当且仅当 \(iso/2+x\) 是奇数。
如果 \(eo\in\{1,2\}\),那么先手必定赢。
如果 \(eo>2\),那么先手胜利当且仅当 \(m\) 是奇数。

下面我们直接开始证明。

如果 \(n\) 是奇数:

显然我们最后得到的图一定是一个联通的二分图。
那么因为 \(n\) 是奇数,所以必然会划分成一侧偶数个点,一侧奇数个点。
于是形成的边一定是偶数个,所以最后的胜利就只和原本已经添加的边的数量有关了。

如果 \(n\) 是偶数,且 \(eo=0\)

因为 \(oo\)\(ee\) 的点数都是偶数,所以 \(iso\) 的数量肯定是偶数。
因为 \(eo=x=iso=0\) 的情况是必败的,其满足 \(iso/2+x\) 是偶数,那么我们只需要保证让对面不论怎么操作,我们都可以进行一个操作让 \(iso/2+x\) 在回到对手手里时是奇数就可以通过数学归纳法证明了。
我们考虑现在都可以进行什么操作:

  1. 添加一条不影响联通性的边。

这会让 \(x\) 的奇偶性改变,于是 \(ios/2+x\) 是奇数,我们直接跟着进行一次同样的操作就行了。
如果 \(x=0\) 那么,显然我们直接把两个孤立点点起来。

  1. 在孤立点之间连接一条边。

类似上面的,我们考虑把孤立点连起来,或者连接不改变联通性的边即可。

  1. 在孤立点和联通块之间连接一条边。

我们也拿一个孤立点,和他在对称的位置连接,这样我们两个人增加的奇偶性就是一样的。
这是因为不存在任何一个操作会导致在对手操作的时候出现 \(eo\) 的情况(包括下面的操作)。

  1. 在联通块和联通块之间连接一条边。

因为全部都是 \(ee\)\(oo\),这显然也会改变 \(x\) 的奇偶性,于是我们直接操作一次不改变联通性的边就行了,因为合并了新的联通块所以不用担心 \(x=0\)

于是我们拿到之后直接合并两个孤立点或者链一个不影响连通性的边,这样就把 \(iso/2+x\) 是偶数的局面给了对手。
然而,我们上面又证明了不论对手怎么操作,我们都可以把 \(iso/2+x\) 是奇数的情况还回去,所以我们必胜。

如果 \(n\) 是偶数,且 \(oe=1\)

容易理解 \(iso\) 是奇数,那么我们拿出一个奇点与 \(eo\) 连接,这样可以归纳到上面的情况。
如果 \((iso-1)/2+x\) 是奇数,那么我们把孤点和 \(eo\) 的奇数侧连边,给对手一个 \(eo=0,iso/2+x\) 是偶数的局面,
反之,我们把孤点向 \(eo\) 的偶数侧连边,也可以达到同样的效果。

如果 \(n\) 是偶数,且 \(oe=2\)

我们可以把两个 \(oe\) 合并起来,来回到 \(eo=0\) 的情况。
如果 \(iso/2+x\) 是偶数,那么我们把两个 \(eo\) 的奇数和偶数放在一边,这样不会改变 \(x\) 的奇偶性,反之转过来放就行了。

如果 \(n\) 是偶数,且 \(oe\ge 2\)

我们每一次操作可以把 \(oe\) 减少 \(1\)\(2\),又因为如果某个人把 \(eo\) 操作到小于 \(3\) 就必败,所以一个结论就是最终 \(oe\) 会保持在 \(3\)
于是这就相当于一个 \(n\) 是奇数的问题了。

我们直接模拟即可。

#include<iostream>
#include<bitset>
#include<vector>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,iso,eo,ee,oo,x;
bitset<N> vis;
vector<int> v[N];
void dfs(int x,int &s1,int &s2){if(vis[x]) return;vis[x]=1,s1++;swap(s1,s2);for(int i:v[x]) dfs(i,s1,s2);swap(s1,s2);
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>m,x=-m;for(int i=1,x,y;i<=m;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}for(int i=1;i<=n;i++){if(vis[i]) continue;if(v[i].empty()){iso++;continue;}int s1=0,s2=0;dfs(i,s1,s2);if(s2&1) swap(s1,s2);if(s1&1){if(s2&1) oo++;else eo++;}else ee++;x+=s1*s2;}if(n&1||eo>2) cout<<((m&1)?"Aoki\n":"Takahashi\n");else if(!eo) cout<<((iso/2+x&1)?"Aoki\n":"Takahashi\n");else cout<<"Aoki\n";return 0;
}
http://www.hskmm.com/?act=detail&tid=24696

相关文章:

  • 深入解析:Java基础(二):八种基本数据类型详解
  • 物理_备忘
  • 越秀凭一己之力打破了行业天花板 - 智慧园区
  • 在AI技术唾手可得的时代,挖掘JavaScript学习资源的新需求成为关键
  • 洛谷P9676 [ICPC 2022 Jinan R] Skills
  • 读人形机器人31未来30年
  • 【java面试】redis篇 - 指南
  • 洛谷P8421 [THUPC 2022 决赛] rsraogps
  • NLP学习路线图(十四):词袋模型(Bag of Words) - 详解
  • 实用指南:苍茫命令行:linux模拟实现,书写微型bash
  • 2025 年压滤机厂家最新推荐排行榜:隔膜压滤机,污泥压滤机,真空压滤机,板框压滤机,带式压滤机优质企业权威评选及选购指南
  • 2025 年搅拌器厂家最新推荐排行榜:涵盖立式、不锈钢、侧入式等多类型设备,深度解析实力厂商
  • 2025 年最新推荐承烧板厂家排行榜:筛选优质企业,破解采购难题,赋能高温工业生产
  • 一文看懂AI SoC芯片
  • 月球尘埃电解技术实现资源就地利用
  • 漏洞赏金计划公开后的三个阶段与应对策略
  • Python 在科学计算与工程模拟中的应用
  • Python 在大数据与分布式计算中的应用
  • Python 在教育与科研中的应用与价值
  • Python 在自动化测试与质量保障中的应用
  • 玩转树莓派屏幕之三:lvgl移植到树莓派
  • enthalpy/entropy
  • Day26自定义异常
  • 谈谈redis的热key问题如何解决
  • Stimulsoft 引入无代码脚本编程 —— Blockly 让报表与仪表盘更智能
  • 理解、学习与使用 Java 中的 Optional
  • 211 粉了整个小 QA 吧
  • 玩转树莓派屏幕之二:自定义屏幕显示
  • INFINI Labs 产品更新 - Coco AI v0.8 与 Easysearch v1.15 全新功能上线,AI 搜索体验再进化!
  • 玩转树莓派屏幕之一:LCD屏幕显示