https://codeforces.com/contest/1325

C. Ehab and Path-etic MEXs

 

题意：给定一棵树，要求对边赋值，且所有点的路径上的MEX值的最大值最小。

构造

把叶子连出的边从0开始赋值，剩下的边随便赋值。

可知任意两点的路径上不会有大于两个叶子，则MEX最多为3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
typedef pair<int, int> pii;
pii es[N];
int ans[N], n, d[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		d[u]++; d[v]++;
		es[i] = pii(u, v);
	}
	memset(ans, -1, sizeof(ans));
	int cnt = 0;
	for (int i = 1; i < n; i++) {
		if (d[es[i].first] == 1 || d[es[i].second] == 1) {
			ans[i] = cnt++;
		}
	}
	for (int i = 1; i < n; i++)if (ans[i] == -1)ans[i] = cnt++;
	for (int i = 1; i < n; i++)printf("%d\n", ans[i]);
	return 0;
}

 

D. Ehab the Xorcist

 

题意：要求构造出一个数组，满足异或和为u，和为v，要求长度最短。

在异或值的基础上再加两个相等的数，异或和不变，但是和增加了。根据这样的特性可以想到解法。

若和与异或和的差值为奇数，则无解，否则有解，且数组长度最多为3，为3时是最简单的情况，只要在异或和上加上两个一样的数即可，而2时则要考虑在异或和上先加上一个，把它们合成一个值，合成时要判断是否有位置冲突。

还要注意判断和一定要大于等于异或和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
ll u, v;
bool vis[N];
bool check(ll x, ll y) {
	for (int i = 0; i <= 60; i++) {
		if (x&(1ll << i))vis[i] = 1;
	}
	for (int i = 0; i <= 60; i++) {
		if (y&(1ll << i)) {
			if (vis[i])return false;
		}
	}
	return true;
}
int main() {
	cin >> u >> v;
	if (u > v) { puts("-1"); return 0; }
	if (u == v) {
		if (u == 0)puts("0");
		else {
			printf("1\n%lld\n",u);
		}
		return 0;
	}
	if ((v - u) & 1)puts("-1");
	else {
		ll a = (u + v) / 2, t = (v - u) / 2;
		if (check(u, t)) {
			printf("2\n%lld %lld\n", a, t);
		}
		else {
			printf("3\n%lld %lld %lld\n", u, (v - u) / 2, (v - u) / 2);
		}
	}
	return 0;
}

 

E. Ehab’s REAL Number Theory Problem

 

题意：给定一个数列，每个数最多只有7个因数，求最短的子序列使得元素乘积为完全平方数。1≤ai≤1061 \le a_i \le 10^6

bfs求最小环

最多只有7个因数，那么最多只有2个质因数。

把数列中每个数变成一条边，连接它的两个质因数，如果它只有1个质因数，则那就用1凑数，连1和那个质因数。

然后就是求最小环的边数。

由于数据量不能Floyd删边，也不能用枚举所有点作为起点，再bfs求两条路径的方法求，但是可以发现每个数都小于 10610^6，那么不会有一条边连接两个大于1000的数，也就是说如果只用大于1000的数绝不会成环，那么既然每个环里都有小于1000的数，枚举起点时也只要枚举小于1000的数就够了。

注意会有重边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10, M = 1e6 + 10;
int n;
int a[N];
vector<int>vc[N];
int head[M], nx[N << 1], to[N << 1], used[N << 1], tot;
void add(int u, int v) {
	to[tot] = v, nx[tot] = head[u], head[u] = tot++;
}
bool isPrime[M], vis[M];
void sieve(int n) {
	for (int i = 2; i <= n; i++) {
		if (vis[i])continue;
		isPrime[i] = 1;
		for (int j = i; j <= n; j += i)vis[j] = 1;
	}
}
int d[M], ans = INF;
queue<int>q;
void bfs(int s) {
	memset(d, -1, sizeof(d));
	fill(used, used + 2 * n, 0);
	d[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i != -1; i = nx[i]) {
			if (used[i])continue;
			int v = to[i];
			if (d[v] == -1) {
				q.push(v);
				d[v] = d[u] + 1;
				used[i] = used[i ^ 1] = 1;
			}
			else ans = min(ans, d[u] + d[v] + 1);
		}
	}
}
int main() {
	sieve(1000);
	scanf("%d", &n);
	memset(head, -1, sizeof(head));
	memset(nx, -1, sizeof(nx));
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j*j <= a[i]; j++) {
			if (a[i] % j == 0 && isPrime[j]) {
				int cnt = 0;
				while (a[i] % j == 0) {
					a[i] /= j;
					cnt++;
				}
				if (cnt & 1)vc[i].push_back(j);
				else vc[i].push_back(1);
			}
		}
		vc[i].push_back(a[i]);
		if ((int)vc[i].size() < 2)vc[i].push_back(1);
		if (vc[i][0] == vc[i][1]) { puts("1"); return 0; }
		add(vc[i][0], vc[i][1]);
		add(vc[i][1], vc[i][0]);
	}
	for (int i = 1; i <= 1000; i++)bfs(i);
	printf("%d\n", ans == INF ? -1 : ans);
	return 0;
}

 

F. Ehab’s Last Theorem

 

题意：给定一张无向图，求一个包含 ⌈n⌉\lceil\sqrt{n}\rceil 的独立集或者一个边数大于等于 ⌈n⌉\lceil\sqrt{n}\rceil 的环。

dfs树

要知道如果直接求环的话，不一定能找到最大的环，那么也就不一定能满足条件。

首先建出dfs树，然后在dfs树上根据非树边找环，如果找到了，就结束。找不到就表明在dfs树上不存在深度相差大于等于 ⌈n⌉−1\lceil\sqrt{n}\rceil-1 且相连的点。

把所有点按照dfs树上的深度%(⌈n⌉−1)\%(\lceil\sqrt{n}\rceil-1)分类，同一类的点要么深度相同，要么深度相差 ⌈n⌉−1\lceil\sqrt{n}\rceil-1，由上一段已知，深度差为 ⌈n⌉−1\lceil\sqrt{n}\rceil-1 的点之间一定不相连，并且由于是dfs树，所以深度相同的点一定也不相连（否则先访问到的那个点一定会直接访问后访问到的那个点，两点必定有父子关系，深度一定不同），所以这些点就是独立集。再由抽屉原理得到必定存在一类，点数大于等于 ⌈n⌉\lceil\sqrt{n}\rceil，从中选出 ⌈n⌉\lceil\sqrt{n}\rceil 个即可。

这里一直强调是dfs树上不存在深度差大于等于 ⌈n⌉−1\lceil\sqrt{n}\rceil-1 的两点，是因为如果在原图上看，是有可能会有大于等于 ⌈n⌉−1\lceil\sqrt{n}\rceil-1 的环的，只不过我们没找到，所以也是有可能有距离相差大于等于 ⌈n⌉−1\lceil\sqrt{n}\rceil-1 的两点的，但是用了dfs树就没有可能了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, m, sq;
vector<int>G[N], ans[N];
int dep[N], fa[N];
void dfs(int u, int _fa) {
	fa[u] = _fa;
	dep[u] = dep[_fa] + 1;
	ans[dep[u] % (sq - 1)].push_back(u);
	for (int v : G[u]) {
		if (v == _fa)continue;
		if (dep[v] == -1)dfs(v, u);
		else {
			if (dep[u] - dep[v] + 1 >= sq) {
				puts("2");
				printf("%d\n", dep[u] - dep[v] + 1);
				for (int i = u; i != fa[v]; i = fa[i])
					printf("%d ", i);
				puts("");
				exit(0);
			}
		}
	}
}
int main() {
	memset(dep, -1, sizeof(dep));
	scanf("%d%d", &n, &m);
	sq = (int)ceil(sqrt(1.0*n));
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0);
	for (int i = 0; i < sq - 1; i++) {
		if ((int)ans[i].size() >= sq) {
			puts("1");
			for (int j = 0; j < sq; j++)
				printf("%d%s", ans[i][j], j == sq - 1 ? "\n" : " ");
			return 0;
		}
	}
	return 0;
}