AtCoder Beginner Contest 049

A - UOIAUAI

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	char c;
	cin >> c;
	if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cout << "vowel";
	else cout << "consonant";
	return 0;
}

B - Thin

观察样例发现规律后直接模拟。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int H, W;
	cin >> H >> W;
	vector<char> v(W);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> v[j];
			cout << v[j];
		}
		cout << "\n";
		for (int j = 0; j < W; j++) cout << v[j];
		cout << "\n";
	}
	return 0;
}

D - Connectivity

道路涉及连通性的问题，即同一道路相互连接的各条道路之间都可相互通行，因此可以使用两个并查集，一个记录道路，一个记录铁路。

不管是道路还是铁路，对于每个城市来说一定与其连通的肯定是它在该并查集的祖先，（城市在该并查集中有祖先即说明该城市在并查集中）

一开始想数组 \(f[i][j]\) 表示与 \(i\) 和 \(j\) 分别连通的城市个数，那么对于城市 \(u\)，答案即为 \(\rm f[find(u,p_1)][find(u,p_2)]\)。初始化过程就是遍历每一个城市，\(\rm f[find(i,p_1)][find(i,p_2)]\)++。

发现空间复杂度为 \(O(n^2)\) ，舍弃。

观察到，对于每个点，我们只会把这个数组的一个位置+1，所以至多用到 \(N\) 个位置。可以开 \(\rm map\)<\(\rm pair\)<\(\rm int,int\)>\(\rm,int\)>，将 \((x,y)\) 当成坐标映射，即可实现空间复杂度 \(O(n)\)。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int p1[200005], p2[200005];

int find(int x, int* p) {
	if (x != p[x]) return p[x] = find(p[x], p);
	return p[x];
} 

void merge(int x, int y, int* p) {
	p[find(x, p)] = find(y, p);	
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int N, K, L;
	cin >> N >> K >> L;
	for (int i = 1; i <= N; i++) {
		p1[i] = i;
		p2[i] = i;
	}
	
	for (int i = 1; i <= K; i++) {
		int a, b;
		cin >> a >> b;
		merge(a, b, p1);
	}
	for (int i = 1; i <= L; i++) {
		int c, d;
		cin >> c >> d;
		merge(c, d, p2);
	}
	
	map<pair<int, int>, int> ans;
	for (int i = 1; i <= N; i++) {
		ans[{find(i, p1), find(i, p2)}]++;
	}
	for (int i = 1; i <= N; i++) cout << ans[{find(i, p1), find(i, p2)}] << " ";
	return 0;
}

\(\rm plus:\) 可以使用 \(\rm AtCoder\) 自己的并查集板子：

#include<bits/stdc++.h>
#include<atcoder/dsu>

using namespace std;
using namespace atcoder; 

int main() {
    int N, K, L; 
    cin >> N >> K >> L;
    dsu uf1(N), uf2(N);
    for (int i = 0; i < K; i++) {
        int p, q; 
        cin >> p >> q; 
        p--, q--; 
        uf1.merge(p,q);
    }
    for (int i = 0; i < L; i++) {
    	int l, r; 
    	cin >> l >> r; 
    	l--, r--; 
    	uf2.merge(l,r);
    }
    map<pair<int, int>, int> m;
    for (int i = 0; i < N; i++) m[{uf1.leader(i),uf2.leader(i)}]++;
    for (int i = 0; i < N; i++) cout << m[{uf1.leader(i),uf2.leader(i)}] << " ";
    return 0;
}