Codeforces Round #628(Div.2) 문제 해결

카탈로그

Codeforces Round #628 (Div. 2)

A. EhAb AnD gCd

B. CopyCopyCopyCopyCopy

C. Ehab and Path-etic MEXs

D. Ehab the Xorcist

E. Ehab's REAL Number Theory Problem

F. Ehab's Last Theorem

Codeforces Round #628 (Div. 2)
A. EhAb AnD gCd
제목: 그룹\(((a, b)\) 만족\(GCD (a, b) + LCM (a, b) = x\) 을 구성합니다.
분석:\(a=1, b=x-1\).

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include 
#define SIZE 200010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll n, t;

int main() {
	io(); cin >> t;
	rep(ii, 1, t) {
		cin >> n;
		cout << 1 << ' ' << n - 1 << '
';
	}
}

B. CopyCopyCopyCopyCopy
제목: 서열\(a\) 을 정하고, 이 서열을 무수히 복사해서 연결합니다. 이 무한장 서열 중 가장 긴 상승 서열을 구하십시오.
분석: 무한 복제했기 때문에 답은 다양한 종류의 숫자의 수량이다.

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include 
#define SIZE 1000010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int n, t, ans;
 
int main() {
	io(); cin >> t;
	rep(ii, 1, t) {
		cin >> n;
		vector a(n);
		rep(i, 0, (n - 1)) cin >> a[i];
		sort(a.begin(), a.end());
		a.erase(unique(a.begin(), a.end()), a.end());
		cout << a.size() << '
';
	}
}

C. Ehab and Path-etic MEXs
제목: (n\) 점의 나무를 지정하면, 나무 가장자리에\(0, 1, 2,..., n-2\) 를 표시할 수 있습니다.정의\(MEX(u, v)\)는 점\(u\)에서\(v\)까지의 경로에 나타나지 않은 가장 작은 표호(예를 들어 경로의 표호가\(0,2,3\)이면 결과는\(1\))로 모든\(u, v)\)에 대한 최대치를 최소화하는 구조 방안을 제시한다.
분석: 만약에 최소한 하나의 점의 도수\(\geq3\)(즉 체인이 아니다)가 있다면\(0,1,2\) 이 세 개의 숫자를 이 점의 세 개의 이웃에 분배할 수 있다. 그러면 내가 선택한 경로에 이 세 개의 최소 숫자가 동시에 존재할 수 없다는 것을 보장할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include 
#define SIZE 200010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int n, t, cnt;
int deg[SIZE];
vector vec[SIZE];
struct Node {
	int x, y;
	int id;
	int val;
	Node() {}
	Node(int x_, int y_) : x(x_), y(y_) {}
	bool operator < (const Node& b) const {
		return (x == b.x ? y < b.y : x < b.x);
	}
}p[SIZE];
map MP;
 
int main() {
	io(); cin >> n;
	rep(i, 2, n) {
		int x, y; cin >> x >> y;
		if (x > y) swap(x, y);
		vec[x].emplace_back(y);
		vec[y].emplace_back(x);
		MP[Node(x, y)] = -1;
		p[i - 1] = Node(x, y); p[i - 1].id = i;
		++deg[x], ++deg[y];
	}
	bool f = false;
	rep(i, 1, n) {
		if (deg[i] > 2) {
			for (auto it : vec[i]) {
				int x = i, y = it;
				if (x > y) swap(x, y);
				MP[Node(x, y)] = cnt++;
			}
			break;
		}
	}
	rep(i, 1, (n - 1)) {
		if (MP[Node(p[i].x, p[i].y)] != -1) cout << MP[Node(p[i].x, p[i].y)] << '
';
		else cout << cnt++ << '
';
	}
}

D. Ehab the Xorcist
제목: 두 개의 숫자\(u\)와\(v\)를 지정하고 가장 짧은 수열\(a n\)을 구성하여\(a 1\oplus a 2\oplus...\oplus a n=u\)를 충족시키고\(\sum^n {i=1}a i=v\)
분석: 우선 구성할 수 없는 상황을 고려하면\(u>v\)가 구성할 수 없는 것을 쉽게 발견할 수 있고, 짝수에 따라\(v-u\)가 홀수일 때 구성할 수 없는 것을 발견할 수 있다.본 문제의 일부 특판, 예를 들어\(u=v=0\),\(u=v\)를 배제한 후에 본 문제는\(v-u\)가 짝수로 바뀔 때의 구조 문제로 바뀐다.\(v-u\)가 짝수이기 때문에 우리는 곧 구조의 상계가\(3\)이기 때문이다(v - u) / 2 ^ (v - u) / 2 ^ u = u.하지만 길이가\(2\)인 수열(v - u) / 2 ^ ((v - u) / 2 ^ u) = u을 구성할 수 있는지도 특판해야 한다.

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include 
#define SIZE 200010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll n, m;

int main() {
	io(); cin >> n >> m;
	if (n > m) cout << -1;
	else if (!n && !m) cout << 0;
	else if (n == m) cout << 1 << '
' << m;
	else {
		if ((m - n) % 2 == 0) {
			ll x = n, y = (m - n) / 2;
			ll z = (x ^ y);
			if (z + y == m) cout << "2
" << z << ' ' << y;
			else cout << "3
" << x << ' ' << y << ' ' << y;
		}
		else cout << -1;
	}
}

E. Ehab's REAL Number Theory Problem
제목: 수조\(a n\)를 정하고 수조에 있는 임의의 원소의 인자수가\(7\)를 초과하지 않도록 하며 가장 짧은 서열을 찾아 이 서열의 축적을 완전 제곱수로 만족시킨다.
분석: 임의의 요소 인자 수가\(7\)를 초과하지 않기 때문에\(a i\)의 질량 인자 수\(\leq 2\)(질량 인자 수가\(3\)인 경우\(8\)개의 인자가 있을 수 있습니다.따라서 우리는 모든 주어진 원소를 미리 처리하고 모든 제곱 인자 (원소가\(2^2\cdot 3\) 라고 가정하면\(3\) 와 같다. 그리고 모든 원소는\(1, p, pq\) 중의 한 형식 (\(p, q\) 만 질수) 일 뿐이다.사전 처리가 완료된 후\(1\)가 존재하면 가장 짧은 하위 시퀀스 길이가\(1\)인 것을 발견하기 어렵지 않다.동일한 요소가 두 개 있으면 결과는\(2\)입니다.
그리고 우리는 처리된 원소에 따라 그림을 만들 수 있다. 원소가\(pq\)라고 가정하면\(p\)와\(q\) 사이에 가장자리를 만들 수 있다.원소가\(p\)라고 가정하면\(p\)와\(1\) 사이에 테두리를 설정합니다.이 문제의 답은 바로 이 그림의 가장 작은 고리이다. 점마다 두 변이 연결되어 있기 때문에 점마다 짝수가 선택되었다는 것을 설명한다.경계가 모두\(1\)이기 때문에\(bfs\)로 바로 가면 되지만 노드마다 검색할 때 복잡도가\(O(NM)\)입니다. 본 문제에서 우리는 소유권 값\(\leq\sqrt{max\{a i}}}\)의 노드만 검색할 수 있습니다. 권한\(>\sqrt{max\{a i}}}}\)의 노드는\(1\)회만 나타날 수 있기 때문에 기수는 없습니다.

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include 
#define SIZE 1000010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int n, ans = 2e9;
vector a, fac;
vector vec[SIZE];
int dis[SIZE];
bool vis[SIZE];

int init(int x) {
	for (int i = 2; i * i <= x; ++i) {
		if (x % i) continue;
		int cnt = 0;
		while (x % i == 0) x /= i, ++cnt;
		if (cnt & 1) x *= i;
	}
	return x;
}

void bfs(int x) {
	for (auto i : fac) dis[i] = 2e9, vis[i] = 0;
	dis[x] = 0;
	queue q;
	q.push(x);
	vis[x] = true;
	while (!q.empty()) {
		int top = q.front();
		q.pop();
		vis[top] = false;
		for (auto i : vec[top]) {
			if (dis[i] > dis[top] + 1) {
				dis[i] = dis[top] + 1;
				q.push(i);
				vis[i] = true;
			}
			else if (vis[i]) ans = min(ans, dis[top] + dis[i] + 1);
		}
	}
}

int main() {
	io(); cin >> n;
	a.resize(n);
	rep(i, 0, (n - 1)) {
		cin >> a[i];
		a[i] = init(a[i]);
	}
	sort(a.begin(), a.end());
	if (a[0] == 1) { cout << 1; return 0; }
	a.erase(unique(a.begin(), a.end()), a.end());
	if (a.size() < n) { cout << 2; return 0; }

	for (auto i : a) {
		vector tmp(2, -1);
		tmp[0] = i;
		for (int j = 2; j * j <= i; ++j) {
			if (i % j) continue;
			tmp[0] = j;
			i /= j;
			if (i != 1) tmp[1] = i;
			break;
		}
		if (tmp[1] == -1) tmp[1] = 1;
		for (auto j : tmp) fac.emplace_back(j);
		vec[tmp[0]].emplace_back(tmp[1]);
		vec[tmp[1]].emplace_back(tmp[0]);
	}
	sort(fac.begin(), fac.end());
	fac.erase(unique(fac.begin(), fac.end()), fac.end());
	rep(i, 1, 1000) {
		if (vec[i].empty()) continue;
		bfs(i);
	}
	cout << (ans == 2e9 ? -1 : ans);
}

F. Ehab's Last Theorem
제목: 점\(m\) 스트라이프의 무방향도를 지정합니다.점수가\(\lceil\sqrt {n}\rceil\)인 독립 집합을 찾아내거나\(\geq\lceil\sqrt {n}\rceil\)의 고리를 찾아야 합니다.
분석:\(CF1103C\)와는 이곡동공의 묘미가 있으며, 이런 문제형은\(dfs\) 트리를 통해 구성할 수 있다.우선, 링을 찾는 것은 매우 쉽다.\(dfs\) 트리에서 조상으로 돌아가는 테두리(테두리)를 직접 찾으면 된다. 점수\(\geq\lceil\sqrt{n}\rceil\)가 있으면 바로 출력한다.그리고 독립 집합의 구조를 고려하여\(\lceil\sqrt {n}\rceil-1\)의 색깔로\(dfs\) 트리의 노드에\(dep[i]\%(\lceil\sqrt {n}\rceil-1)\)의 규칙에 따라 염색을 합니다.\(dfs\) 트리의 특성상 같은 깊이의 노드는 반드시 독립 집합을 구성하고 모형의 의미에서 같은 두 개의 서로 다른 깊이 노드 사이를 구성합니다.직선 모서리가 있으면 노드 수\(\geq\lceil\sqrt{n}\rceil\)의 루프가 있음을 나타냅니다.따라서 우리는 점수\(\geq\lceil\sqrt{n}\rceil\)의 집합을 찾아서\(\lceil\sqrt{n}\rceil\) 개의 점을 출력하기만 하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include 
#define SIZE 200010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int n, m, lim;
int pa[SIZE], dep[SIZE], num[SIZE];
vector vec[SIZE];

void dfs(int now) {
	++num[dep[now] % (lim - 1)];
	for (auto to : vec[now]) {
		if (to == pa[now]) continue;
		if (dep[to] == -1) {
			dep[to] = dep[now] + 1;
			pa[to] = now;
			dfs(to);
		}
		else if (dep[now] - dep[to] >= lim - 1) {
			cout << "2
";
			cout << dep[now] - dep[to] + 1 << '
';
			for (int i = now; i != pa[to]; i = pa[i]) cout << i << ' ';
			exit(0);
		}
	}
}

int main() {
	io(); cin >> n >> m;
	rep(i, 0, n) dep[i] = -1;
	dep[1] = 0;
	lim = ceil(sqrt(1.0 * n));
	rep(i, 1, m) {
		int x, y; cin >> x >> y;
		vec[x].emplace_back(y);
		vec[y].emplace_back(x);
	}
	dfs(1);
	cout << "1
";
	rep(i, 0, (lim - 2)) {
		if (num[i] < lim) continue;
		int tot = lim;
		rep(j, 1, n) {
			if (dep[j] % (lim - 1) == i) {
				if (tot-- != lim) cout << ' ';
				cout << j;
				if (!tot) return 0;
			}
		}
	}
}