0%

CF Round 1325

。。。构造杀我

$\text{A}$

显然 $a = 1, b = x-1$ 满足条件。

有一个 $\tt{Bonus Problem}$:如何找到所有解?先鸽着。

$\text{B}$

很显然答案就是数的种数。明显这是一个上界并且可以通过在每个数列里都挑一个来达成上界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int t, n;
map <int, int> mp;
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--) {
mp.clear();
cin >> n;
int ans = 0;
for (int i = 0, x; i < n; ++i)
cin >> x, ans += !mp[x], mp[x] = 1;
cout << ans << '\n';
}
}

$\text{C}$

不会

题目要求我们 $mex$ 的最大值尽量小,也就是我们考虑不让小的数尽量同时出现。

$mex = 0/1$ 显然不可能,因为你不论这两条边放在哪里都会有一条路径穿过它。

考虑 $mex = 2$ 能否构造,其实是可以的。只需要挑一个度数 $\geq 3$ 的点,把 $0, 1, 2$ 都塞到他的邻边上就可以了,这样的话过这个点的路径最大 $mex = 2$,不过 $mex = 0$。

如果挑不出来度数 $\geq 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
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int N = 200020;
int n, deg[N], ans[N];
vector <int> g[N];
int main() {
scanf ("%d", &n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
scanf ("%d%d", &u, &v);
g[u].push_back(i);
g[v].push_back(i);
}
for (int i = 1; i <= n; ++i) deg[i] = g[i].size();
if (*max_element(deg + 1, deg + n + 1) <= 2) {
for (int i = 0; i < n - 1; ++i) printf("%d\n", i);
return 0;
} else {
memset(ans, -1, sizeof(ans));
for (int i = 1; i <= n; ++i) if (deg[i] > 2) {
// cout << "find " << i << '\n';
ans[g[i][0]] = 0;
ans[g[i][1]] = 1;
ans[g[i][2]] = 2;
break;
}
vector <int> v;
for (int i = 3; i < n - 1; ++i) v.push_back(i);
int cnt = 0;
for (int i = 0; i < n - 1; ++i) {
if (ans[i] == -1) printf("%d\n", v[cnt++]);
else printf("%d\n", ans[i]);
}
}
}

$\text{D}$

又是毒瘤构造

考虑 $\text{xor}$ 和 $+$ 的关系。由韦恩图我们知道

所以任意两个数的 $xor$ 值肯定不大于算术加和,并且加和 - $\text{xor}$ 值肯定是个偶数,要不然就无解。

如果有解如何构造呢?很 $naiive$ 的构造方法是令 $d = (v - u) / 2$,直接构造 $d, d, u$ 这三个数即可,因为 $d$ 可以消掉。

当然这也不一定是最优的:如果 $d\and u$ 是空集,就可以直接把 $d, u$ 换成 $d\or u$,就变成了两个数。

当然一个数和零个特判一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll u, v;
int main() {
cin >> u >> v;
ll d = (v - u);
if (d < 0 || d % 2) {
puts("-1");
return 0;
}
if (u == v && v == 0) {
cout << 0 << endl;
return 0;
}
if (u == v) {
cout << 1 << endl << u << endl;
return 0;
}
d >>= 1;
if (!(d & u)) cout << 2 << endl << d << " " << d + u << endl;
else cout << 3 << endl << d << " " << d << " " << u << endl;
}

$\text{E}$

想到每个数最多有两个质因子就没有继续往下想

这其实是个特别好的性质,因为“两个”往往可能是连边操作。

想一想,如果我们把每个数的唯一分解上的幂次模 $2$ 显然不会对答案产生影响,因为消去了完全平方数。但是这有一个好处:每个幂次上的值都为 $0$ 或 $1$,如果只有一个质因子就连一条 $(1, p)$ 的双向边,有两个质因子就连 $(p, q)$ 的双向边。

然后答案就变成了找一个无向图中的最小简单环,这可能是个套路:如果没边权就 $bfs$,有就 $floyd$。注意到环上一定存在一个 $\leq 1000$ 的质数,所以只需要拿这些东西来 $bfs$ 即可。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 1000010;
int n, a[N], cnt, num[M], dis[N], id[M], ans;
vector <int> g[N];
bool np[M];
void bfs(int s) {
queue < pair <int, int> > q;
for (int i = 1; i <= cnt; ++i) dis[i] = 0x3f3f3f3f;
dis[s] = 0;
q.push({s, 0});
int t = 0;
while (!q.empty()) {
int u = q.front().first, fa = q.front().second;
q.pop();
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (v == fa) continue;
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
q.push({v, u});
} else ans = min(ans, dis[u] + dis[v] + 1);
}
}
}
int main() {
cnt = 1; ans = 0x3f3f3f3f;
for (int i = 2; i <= 1000000; ++i) if (!np[i]) {
id[i] = ++cnt;
num[cnt] = i;
for (int j = i + i; j <= 1000000; j += i) np[j] = 1;
}
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]);
for (int i = 1; i <= n; ++i) {
int x = a[i];
vector <int> d, cnt;
for (int j = 2; j * j <= x; ++j) {
if (x % j == 0) {
bool hav = 0;
while (x % j == 0) x /= j, hav ^= 1;
if (hav) d.push_back(j);
}
}
if (x > 1) d.push_back(x);
if (d.size() == 0) return puts("1"), 0;
else if (d.size() == 1) {
g[1].push_back(id[d[0]]);
g[id[d[0]]].push_back(1);
} else if (d.size() == 2) {
g[id[d[1]]].push_back(id[d[0]]);
g[id[d[0]]].push_back(id[d[1]]);
}
}
for (int i = 1; i; ++i) {
if (num[i] > 1000) break;
bfs(i);
}
if (ans != 0x3f3f3f3f) cout << ans << '\n';
else cout << "-1" << '\n';
return 0;
}

$\text{F}$

首先如何找环?直接在 $dfs$ 树上找返祖边,看长度够不够即可。

如果找不到怎么办?首先注意到如果一个点返祖边个数 $\geq \sqrt n$,那根据抽屉原理,一定能找到一个环。所以如果这么找找不到的话,剩下的东西肯定每个点返祖边个数 $< \sqrt n$。

既然没有这么多条,我们就贪心地将其选入独立集:每次从底向上,能选就选,把返祖边毙掉。每次最多毙掉 $O(\sqrt n)$ 个点,所以也可以选进来 $O(\sqrt n)$ 个点。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m, t, f[N], vis[N], dep[N];
vector <int> g[N], store[N];
void dfs(int u) {
store[dep[u] % t].push_back(u);
vis[u] = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!dep[v]) {
dep[v] = dep[u] + 1;
f[v] = u;
dfs(v);
} else if (dep[u] - dep[v] + 1 >= t + (t * t < n)) {
int pos = u;
printf("2\n");
printf("%d\n", dep[u] - dep[v] + 1);
while (true) {
printf("%d ", pos);
if (pos == v) break;
else pos = f[pos];
}
exit(0);
}
}
}
int main() {
scanf ("%d%d", &n, &m);
t = sqrt(n);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf ("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dep[1] = 1;
dfs(1);
cout << 1 << endl;
for (int i = 0; i < t; ++i) if (store[i].size() >= t + (t * t < n)) {
int num = t + (t * t < n);
for (int j = 0; j < num; ++j) printf("%d ", store[i][j]);
return 0;
}
return 0;
}