宇月幸成

用户名：3350680655

访问量：14958

签　名：

题解都沉没在OJ里了..

等　　级
排　　名	402
经　　验	5068
参赛次数	1
文章发表	47
年　　龄	24
在职情况	学生
学　　校
专　　业	软件工程

　　自我简介：

刷题打发时间，没别的事做了

TA的其他文章

简洁明了的代码（C++）
浏览：591

蓝桥杯算法提高VIP-密码锁-C++超简单BFS
浏览：489

蓝桥杯算法训练VIP-FBI树C++超简单题解
浏览：323

你可能喜欢

蓝桥杯算法训练VIP-新生舞会-题解(C++小题大做，并查集解法)

　　作者: 宇月幸成　　　　发表时间：2020-03-18 21:52:48 浏览：304　|　评论：0　

原题链接：蓝桥杯算法训练VIP-新生舞会

### 把男生看成一个集合，女生看成一个集合，所以可用并查集
下面两大串注释是我在写这个题目之前的思路，最后确定为并查集是因为离散化的思路不成熟，而且也没必要。为什么要用并查集？因为在考虑性别之间的关系时脑子里突然闪出了一个树，自然而然的联想到了并查集。~~明明是因为太无聊了~~
```cpp
#include <iostream>
#include <map>
using namespace std;

// 不知道为什么又想用离散化做，但似乎不行，
// 因为询问不止有下标，还有字符串（名字），那干脆用一个map，用
// 名字映射，一个vector存名字，这样就可以应对字符串和下标两种询问了

// 突然觉得上面的方法有点麻烦，想到了用并查集搞，男生统一祖先为第一个
// 男生，女生统一祖先为第一个女生，然后把名字和id映射下，如果输入的名字
// 去map里找id，再用这个id去找它的祖先，如果一次询问祖先相同，说明
// 不可行，否则可行，学号如果用字符串的话可能有10位数字之多，所以得
// 用输入顺序映射，映射关系式姓名->顺序下标以及学号->顺序下标，这样
// 就能在两种不同的询问情况下去查找了

// 并查集模板 
struct unionFind {
	int bin[1010];
	unionFind () {
		for (int i = 1; i <= 1010; i++) bin[i] = i;
	}
	int anc(int x) {
		if (x == bin[x]) return x;
		bin[x] = anc(bin[x]);
		return bin[x];
	}
	void uni(int x, int y) {
		bin[anc(x)] = anc(y);
	}
	bool ask(int x, int y) {
		return anc(x) == anc(y);
	}
};
unionFind u;
map<string, int > m, im;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int n;
	cin >> n;
	bool mFlag = false, wFlag = false;
	// fM记录第一个男生的下标， fW记录第一个女生的 
	int fM, fW;
	for (int i = 1; i <= n; i++) {
		string name, id, gender;
		cin >> name >> id >> gender;
		// 名字和下标的映射 
		m[name] = i;
		// id和下标的映射
		im[id] = i; 
		// 一下四行为记录第一个男生/女生的下标，以及将之后的学生的祖宗映射到他们上 
		if (!mFlag && gender == "M") fM = i, mFlag = !mFlag;
		else if (gender == "M") u.uni(fM, i);
		if (!wFlag && gender == "F") fW = i, wFlag = !wFlag;
		else if (gender == "F") u.uni(fW, i);
	}
	int k;
	cin >> k;
	while (k--) {
		string a, b;
		cin >> a >> b;
		int fId, sId;
		// 获取对应关系 
		if (m.count(a)) fId = m[a];
		else fId = im[a];
		if (m.count(b)) sId = m[b];
		else sId = im[b];
		// 查询是否为同一性别 
		if (u.ask(fId, sId)) cout << "N";
		else cout << "Y";
		cout << endl;
	}
	return 0;
}
```
突然感觉小题大做也挺有意思的...

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

宇月幸成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

地宫取宝（C语言代码）

【绝对值排序】（C语言代码）

K-进制数（C++代码）

C语言训练-列出最简真分数序列* （C语言代码）

蓝桥杯算法训练VIP-新生舞会-题解(C++小题大做，并查集解法)

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

打水问题（C语言代码）

字符串比较（C语言代码）答案错误？？？？

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

Hello, world! （C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

字符逆序（C语言代码）

Hello, world! （C语言代码）

震宇大神的杀毒软件（C语言代码）

宇月幸成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

地宫取宝 （C语言代码）

【绝对值排序】 （C语言代码）

K-进制数 （C++代码）

C语言训练-列出最简真分数序列* （C语言代码）

蓝桥杯算法训练VIP-新生舞会-题解(C++小题大做，并查集解法)

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

打水问题 （C语言代码）

字符串比较 （C语言代码）答案错误？？？？

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

Hello, world! （C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

字符逆序 （C语言代码）

Hello, world! （C语言代码）

震宇大神的杀毒软件 （C语言代码）

地宫取宝（C语言代码）

【绝对值排序】（C语言代码）

K-进制数（C++代码）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

打水问题（C语言代码）

字符串比较（C语言代码）答案错误？？？？

字符逆序（C语言代码）

震宇大神的杀毒软件（C语言代码）