[ 题解 ] [ JZOJ5777 ] 小 x 玩游戏

news/2024/2/27 20:31:53

题面

今天,小 x 因为太无聊,就在玩游戏。这个游戏有两个队伍,然后他们在游戏里面打来打去。

但小 x 遇到了难题。他不知道自己的队友是谁。他只知道总共有两个队伍,每队有 n n n 个人和很多组击杀情况。他想问你,现在他能否知道两个队伍分别有谁。你可以帮助小 x 吗?由于小 x 是个游戏狂魔,所以他玩了很多局游戏。

输入
第一行有一个 t t t,表示小 x 共玩了 t t t 局游戏。

接下来有 t t t 组数据,每组数据第一行有一个 n , m n, m n,m,表示每队有 n n n 个人,有 m m m 组击杀情况,接下来 m m m 行每行两个字符串 s 1 , s 2 s_1,s_2 s1s2,表示 s 1 s_1 s1 杀了 s 2 s_2 s2,其中 s 1 , s 2 s_1,s_2 s1s2 的长度均不超过 10 10 10(数据保证两个字符串都由小写字母组成)。注意一个人可以被击杀多次、一个人可以被曾经杀死过的人给杀死。

输出
总共有 t t t 行,每行一个 YESNOYES 表示符合题目条件,NO 表示不符合。

Example
Input

1
2 3
a b
c d
a d

Output

YES

数据范围
对于 100 100% 100 的数据, t ≤ 10 , n ≤ 2000 , m ≤ 100000 t \leq 10,n \leq 2000,m \leq 100000 t10n2000m100000
数据保证不会有矛盾的关系。

题解

对每个联通块染色,得到两种颜色的个数。
把所有的个数都塞到一个列表里(颜色不重要,当作没有就好)
暴力枚举,取列表中一半的数,看有没有可能使得取的一半的和与另一半相等。
可能就 YES
不可能就 NO

复杂度:联通块个数的阶乘(少一些) O ( 能 过 ) O(能过) O()

Code(C++11): 4068KB 248ms

#include <unordered_map>
#include <iostream>
#include <cstring>
#include <vector>const int MAX_N = 4e3 + 50;using pii = std::pair<int, int>;std::unordered_map<std::string, int> id;
int id_cnt;std::vector<int> g[MAX_N];
std::vector<int> nums;
int tot;int color[MAX_N];void init()
{id.clear();id_cnt = 0;for (int _i = 0; _i < MAX_N; _i++)g[_i].clear();nums.clear();tot = 0;memset(color, 0, sizeof(color));
}pii dfs(int u)
{pii res{0, 0};if (color[u] == -1)res.first = 1;elseres.second = 1;for (auto v : g[u]){if (color[v] == 0){color[v] = (color[u] == 1 ? -1 : 1);const auto ret = dfs(v);res.first += ret.first;res.second += ret.second;}}return res;
}bool dfs2(std::size_t step, std::size_t last, int sum, const std::size_t size)
{if (step == size / 2)return 2 * sum == tot;for (std::size_t i = last + 1; i < size; i++){const bool ret = dfs2(step + 1, i, sum + nums[i], size);if (ret)return true;}return false;
}int main()
{std::ios::sync_with_stdio(false);std::cout.tie(0);std::cin.tie(0);int t;std::cin >> t;for (int _i = 0; _i < t; _i++){int n, m;std::cin >> n >> m;init();for (int _i = 0; _i < m; _i++){std::string u, v;std::cin >> u >> v;if (!id[u])id[u] = ++id_cnt;if (!id[v])id[v] = ++id_cnt;g[id[u]].emplace_back(id[v]);g[id[v]].emplace_back(id[u]);}if (2 * n - id_cnt >= 2){std::cout << "NO\n";continue;}for (int i = 1; i <= id_cnt; i++){if (color[i] == 0){color[i] = 1;const auto ret = dfs(i);tot += ret.first + ret.second;nums.emplace_back(ret.first);nums.emplace_back(ret.second);}}const bool ret = dfs2(0, -1, 0, nums.size());std::cout << (ret ? "YES" : "NO") << "\n";}return 0;
}

http://www.ppmy.cn/news/745980.html

相关文章

小 X 与煎饼达人(flip)c++做法

题目描述 玩着玩着小 X 觉得有点饿了&#xff0c; 他想出门买些吃的。 刚刚走出大门&#xff0c;小 X 就看到有位大叔在做煎饼&#xff0c;而且做法十分有趣。 只见此人将 n 块煎饼排成一排&#xff0c;手持一把大铲&#xff0c;将煎饼铲得上下翻飞&#xff0c; 煞是好看。 小…

深度学习循环神经网络

循环神经网络&#xff08;Recurrent Neural Network&#xff0c;RNN&#xff09;是一种广泛应用于序列数据、自然语言处理等领域的神经网络。与传统的前馈神经网络不同&#xff0c;循环神经网络的输入不仅取决于当前输入&#xff0c;还取决于之前的状态。这使得循环神经网络可以…

小X转进制

小X转进制 题目描述 小X喜欢研究进制转换。 在了解了进制转换的一般流程后&#xff0c;小X突然想起了以前学过的回文数&#xff08;正着读倒着读都一样的数&#xff09;&#xff0c;于是开始思考一个奇怪的问题&#xff1a;1到N 中有多少个整数的平方在M进制下是回文数呢&…

小 X 玩游戏(game)c++

题目描述 听完了故事&#xff0c;小 XXX 又想去玩一会儿游戏了。 这是一个很奇特的单机游戏&#xff0c; 游戏规则如下&#xff1a; 游戏中一共有 4n4 n4n 张牌&#xff0c;每张牌上有一个数字&#xff0c; 这些数字恰好是 111&#xff5e;4n4 n4n。一开始电脑会把这 4n4 …

小X转进制 C++

小X喜欢研究进制转换。 在了解了进制转换的一般流程后&#xff0c;小X突然想起了以前学过的回文数&#xff08;正着读倒着读都一样的数&#xff09;&#xff0c;于是开始思考一个奇怪的问题&#xff1a;1到N 中有多少个整数的平方在M进制下是回文数呢&#xff1f; 小X随手列了几…

小X与机器人(c++)

题目描述 小X的老师很喜欢围棋。众所周知&#xff0c;围棋的棋盘有19行19列&#xff0c;共有361个交叉点。为方便起见&#xff0c;我们把这些行列按顺序编号为1&#xff5e;19&#xff0c;并用(x, y)表示第x列第y行的位置。例如下图中&#xff0c;A用(16,4)表示&#xff0c;B用…

小X算排名

说明 小X很关心自己在学校的表现。 班主任手上有一本“个人得分记录本”&#xff0c;如果一位同学表现好就会加分&#xff0c;表现差则会扣分。学期结束&#xff0c;每位同学都得知了自己的个人得分。小X想知道其他同学情况如何&#xff0c;但由于排名不公布&#xff0c;他只好…

小 X的密室

【题目背景】 小 X正困在一个密室里&#xff0c;他希望尽快逃出。 【题目描述】 密室中有 N个房间&#xff0c;初始时小 X在 1号房间&#xff0c;而出口在 号房间&#xff0c;而出口在 N号房间。 密室的每一个房间中可能有着些钥匙和传送门&#xff0c;会 密室的每一个房间中可…

小X与缩写

题目&#xff1a; 时间限制 : 1 Sec 内存限制 : 128 Mb 提交 : 91 解决 : 50 题目描述 小X注意到&#xff0c;生活中有很多用到首字母缩写的例子。例如UOJ就是通用在线评测(Universal Online Judge)的缩写。 我们定义一个英文词组的首字母缩写为&#xff1a;取出词组中每个单词…

东方博宜oj-1542: 【提高】小X算排名

题目描述 小X很关心自己在学校的表现。 班主任手上有一本“个人得分记录本”&#xff0c;如果一位同学表现好就会加分&#xff0c;表现差则会扣分。学期结束&#xff0c;每位同学都得知了自己的个人得分。小X想知道其他同学情况如何&#xff0c;但由于排名不公布&#xff0c;…

小X与三角形(c++)

题目描述 小X很喜欢三角形&#xff0c;原因之一是三角形具有稳定性。也就是说&#xff0c;给定三角形的三条边长&#xff0c;它的形状也随之确定了。 现在小X想画一个三条边长都是正整数的三角形&#xff0c;其中两条边的长度分别是a和b&#xff0c;第三条边的长度还没有确定。…

如何用 TDengine 预测 “未来”

介绍 TDengine™ 是一种开源的云原生时序数据库&#xff08;Time Series Database&#xff0c;TSDB&#xff09;&#xff0c;专为物联网&#xff08;IoT&#xff09;、连接汽车和工业物联网进行了优化。它能够高效地实时摄取、处理和监控一天内由数十亿个传感器和数据收集器产…

【Kafka】Kafka基础操作笔记

【Kafka】Kafka基础操作笔记 文章目录 【Kafka】Kafka基础操作笔记1. 两种模式1.1 点对点模式1.2 发布/订阅模式 2. 基础架构3. Topic命令行操作3.1 查看 Topic 操作3.2 创建 Topic3.3 查看所有 Topic3.4 查看 Topic 的详情3.5 修改分区数3.6 删除 Topic 1. 两种模式 Kafka作为…

一文带你分析骗子和被骗的心里

兄弟们&#xff0c;坐稳了&#xff0c;我要一语道破天机&#xff0c;被骗的本质了&#xff0c;这是我看了&#xff0c;很多案例&#xff0c;研究了很多案例之后&#xff0c;特别想写的文章 今天我就要用投资的心得中最经典的一句话&#xff1a;不懂不要碰&#xff0c;一定要先了…

第九章 深入拨号方案

现在&#xff0c;我们已经对FreeSwitch的XML配置及其强大的XML拨号方案的工作原理有了更多的基本了解。 现在是时候超越那种“我知道怎么做&#xff0c;但不完全理解为什么他们会那样做”的感觉了。 这是漫长而且困难的一章&#xff0c;请给我点耐心。读完这一章&#xff0c;你…

php 电话中转 保护用户隐私,打车APP的隐私保护通话是如何保护用户号码隐私的...

原标题&#xff1a;打车APP的隐私保护通话是如何保护用户号码隐私的 隐私保护通话&#xff0c;拿百数的号码隐私保护业务举例来说&#xff0c;是防止用户手机/座机号码隐私泄露的解决方案&#xff0c;适用于网购、出行、求职、外卖等各种场景&#xff0c;可申请全国各地市号码&…

谈谈如何在简历筛选中尽可能 “存活下来“, 如何在面试过程中 “游刃有余“

本文只是个人学习总结出来的技巧, 仅供参考 如果有不认同的地方, 也不必太较真, 因人而异 目录 1. 为什么要做简历 1.2 好简历与差简历的区别 2. 如何做一份好的简历 2.1 知己知彼 2.2 构思内容 2.3 模板的选择 2.4 填充内容 2.5 不断的更新迭代 2.6 其他注意事项 3…

VoIP的落地通信模型和要考虑几个大的方面问题及基本概念和交互流程整理

目录 一、VoIP的落地通信模型和要考虑几个大的方面问题... 1 关于SIP NAT防火墙穿越的汇总... 2 2.1 ALG&#xff08;Application Level Gateway&#xff09;... 3 2.2 MidCom&#xff08;IETF MIDCOM(Middlebox Communications&#xff09;... 3 2.3 STUN(Simple Travers…

以数字技术推动行业跃迁,容联云抢先迈进云联络中心智能化阶段

“很高兴为您服务&#xff01;” 这句大多数人耳熟能详的话&#xff0c;如今更多被智能客服所发出。 假如你是个细心的人&#xff0c;你一定会发现如今拨打电信运营商、银行等机构的客服电话&#xff0c;最先和你聊天已经是高度智能化的机器人&#xff0c;只有复杂的问题才会转…

从人工客服到人机协同,容联云用AI重塑联络中心

“很高兴为您服务&#xff01;” 这句大多数人耳熟能详的话&#xff0c;如今更多被智能客服所发出。 假如你是个细心的人&#xff0c;你一定会发现如今拨打电信运营商、银行等机构的客服电话&#xff0c;最先和你聊天已经是高度智能化的机器人&#xff0c;只有复杂的问题才会转…
最新文章