AutumnKite's Blog

一个 ZJ 小蒟蒻的博客

完全爆蛋,小号三场上橙无望 /kk

爆蛋链接

A - EhAb AnD gCd

题目传送门

题意

构造正整数 \(a,b\) 满足 \(\gcd(a,b)+\operatorname{lcm}(a,b)=x\)

\(x\le 10^9\)

题解

构造 \(a=1,b=x-1\) 即可。

代码

1
2
3
4
5
int x;
void solve(){
read(x);
print(1, ' '), print(x - 1);
}

B - CopyCopyCopyCopyCopy

题目传送门

题意

求将一个长度为 \(n\) 的序列 \(a\) 复制 \(n\) 次后的 LIS 长度。

\(n\le 10^5\)

题解

显然最优方案是在复制的第一份中选最小值,第二份中选次小值……

所以 LIS 长度就是所有数去重后的数量。

代码

1
2
3
4
5
6
7
int n, a[100005];
void solve(){
read(n);
for (register int i = 1; i <= n; ++i) read(a[i]);
std::sort(a + 1, a + 1 + n);
print(std::unique(a + 1, a + 1 + n) - a - 1);
}

C - Ehab and Path-etic MEXs

题目传送门

题意

给定一棵 \(n\) 个点的树,你需要给每条边定上互不相同的 \(0\sim n-2\) 的整数权值,使得 \(\max\limits_{u,v} \operatorname{mex}(\operatorname{path}(u,v))\) 最小。\(\operatorname{path}(u,v)\) 表示 \(u\)\(v\) 路径上所有边边权组成的集合。

\(n\le 10^5\)

题解

对于 \(n>2\) 时,我们始终可以找到一条包含 \(0,1\) 的路径,所以有答案 \(\ge 2\)

我们只要找到一个度数 \(\ge 3\) 的点,把 \(0,1,2\) 放在这个点连出去的边中,就可以保证不存在某条路径同时包含 \(0,1,2\),即达到了答案的下界。

若没有度数 \(\ge 3\) 的点,此时树的形态是一条链,答案显然为 \(n-1\),任意构造即可。

代码

考场上想复杂了,尝试以某个叶子节点为根以后去考虑 \(0,1,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
const int N = 100005;
int n, ans[N];
std::vector<std::pair<int, int>> E[N];
void solve(){
read(n);
for (register int i = 0, u, v; i < n - 1; ++i)
read(u), read(v), E[u].push_back({v, i}), E[v].push_back({u, i}), ans[i] = -1;
int id = 0, cnt = 0;
for (register int i = 1; i <= n; ++i)
if (E[i].size() == 1) ++cnt, id = i;
if (cnt == 2){
for (register int i = 0; i < n - 1; ++i) print(i);
return;
}
ans[E[id][0].second] = 0;
int u = E[id][0].first, lst = id, now = 0;
while (E[u].size() == 2){
int v = E[u][0].first ^ E[u][1].first ^ lst;
lst = u, u = v;
}
for (auto p : E[u]) if (p.first != lst) ans[p.second] = ++now;
for (register int i = 0; i < n - 1; ++i)
if (ans[i] == -1) ans[i] = ++now;
for (register int i = 0; i < n - 1; ++i) print(ans[i]);
}

D - Ehab the Xorcist

题目传送门

题意

构造一个最短的序列使得异或和为 \(u\),和为 \(v\)

\(u,v\le 10^{18}\)

题解

考场上尝试从高位到低位逐位构造,但是他先 WA9 然后 WA18 了。

神仙 Froggy 告诉我本题考查了 if 语句。

我离当场去世真的只差一点.jpg

代码

1
2
3
4
5
6
7
8
9
10
11
12
long long u, v;
void solve(){
read(u), read(v);
if (v < u || (v - u) & 1) return print(-1), void(0);
if (u == 0){
if (v == 0) return print(0), void(0);
else return print(2), print(v >> 1, ' '), print(v >> 1), void(0);
}
if (u == v) return print(1), print(u), void(0);
if (u & ((v - u) >> 1)) return print(3), print(u, ' '), print((v - u) >> 1), print((v - u) >> 1), void(0);
else return print(2), print(u + ((v - u) >> 1), ' '), print((v - u) >> 1), void(0);
}

E - Ehab's REAL Number Theory Problem

题目传送门

题意

给定一个长度为 \(n\) 的序列 \(a\),求出所有乘积为完全平方数的子序列(可以不连续)的最短长度。

保证 \(a_i\) 的因数个数不超过 \(7\)

\(n\le 10^5,a_i\le 10^6\)

题解

由于包含三个不同质因子的数至少有 \((1+1)^3=8\) 个因数,所以因数个数不超过 \(7\) 说明不同质因子数量不超过 \(2\)

并且,我们可以去掉 \(a_i\) 中包含的完全平方因子,这样处理后 \(a_i\) 只会包含至多两个次数为 \(1\) 的质因子。

于是我们可以把 \(a_i\) 表示成 \(p\times q\) 的形式,其中 \(p,q\) 为质数或 \(1\)。我们把这样的 \(a_i\) 看成一条连接 \(p,q\) 的无向边。

现在问题是在这样得到的图中选择最少数量的边(至少一条),使得只保留这些边后图中每个点的度数为偶数。

显然存在度数 \(>2\) 的点是不优的,所以我们可以强制最后每个点的度数为 \(2\)(不考虑度数为 \(0\) 的点)。

这意味着我们要求新图的最小环。


考场上被人误导想了一个假算法,就是把 \(>1000\) 的点扔掉,直接在他连的点之间互相连边以后跑 Floyd。

但是显然这样做是错的,会导致一个数被选多次。


考场上只想到了上面部分,于是当场去世了。

我们需要求出一个无向图的最小环。那么我们考虑枚举一个点 \(s\) 以及一条边 \((u,v)\),得到以 \(s\) 为起点的最短路树,求出包含点 \(s\)非树边 \((u,v)\) 的最小环。

考虑最短路树上加入 \((u,v)\),我们得到了一个包含 \((u,v)\) 但有可能不包含 \(s\) 的环。

可以发现,我们直接用 \(\operatorname{dist}(s,u)+\operatorname{dist}(s,v)\) 更新答案一定是对的,因为如果上面得到的环不包含 \(s\),一定会在枚举其他起点时被计算入答案,并且一定优于 \(\operatorname{dist}(s,u)+\operatorname{dist}(s,v)\),所以我们并不需要判断这个环是否包含 \(s\)

我们仍然需要考虑的是上述算法是否能覆盖到最优解。考虑最优解环上任意一个点 \(s\),环上一定存在一条边 \((u,v)\) 不在以 \(s\) 为起点形成的最短路树上。如果 \(u,v\) 在这棵树上的 LCA 不是 \(s\),说明存在一个更小的环,与假设矛盾;否则此时 \(\operatorname{dist}(s,u)+\operatorname{dist}(s,v)\) 一定就是最优解的环长。由于我们枚举了所有 \(s,u,v\),所以一定能覆盖到最优解。


然而上面的算法是 \(O(nm)\) 的。

\(m=\max \{a_i\}\),可以发现我们需要求最小环的图与一般的图有一个很大的区别是,两个点 \(u,v\)\(uv>m\) 是不可能有边的,所以一定不会存在 \(u,v>\sqrt{m}\) 的连边。

那么显然一个环内至少存在一个点的编号是 \(\le \sqrt{m}\) 的。根据上面算法能覆盖到最优解的证明过程,我们只要能够枚举到环上任意一个点作为 \(s\) 就可以覆盖到这个环。所以,我们只要将上面求最小环的算法中 \(s\) 的枚举范围缩小到 \(\sqrt{m}\) 即可。

时间复杂度根据实现为 \(O(n\frac{\sqrt{m}}{\log m})\)\(O((n+\frac{m}{\log m})\frac{\sqrt{m}}{\log m})\)

除以 \(\log m\) 是因为只需要考虑质数。

代码

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
const int N = 1000005, M = 100005, INF = 0x3f3f3f3f;
int n;
int cnt, p[N], vis[N];
void init(int n){ // 欧拉筛预处理所有质数
for (register int i = 2; i <= n; ++i){
if (!vis[i]) p[++cnt] = i, vis[i] = cnt;
for (register int j = 1; j <= cnt && p[j] * i <= n; ++j){
vis[p[j] * i] = 1;
if (i % p[j] == 0) break;
}
}
}
std::vector<int> v[M];
std::vector<std::pair<int, int>> E[N];
int ans, ont[M], tim[N], dis[N];
void bfs(int S){ // bfs 求出最短路树
for (register int i = 1; i <= n; ++i) ont[i] = 0;
std::vector<int> Q;
Q.push_back(S), tim[S] = S, dis[S] = 0;
// 将 tim 置为每次 bfs 的起点,可以避免每次需要重置 dis 数组导致复杂度变劣
for (register int i = 0; i < (int)Q.size(); ++i){
int u = Q[i];
for (auto p : E[u]){
int v = p.first, eid = p.second;
if (tim[v] != S) Q.push_back(v), tim[v] = S, dis[v] = dis[u] + 1, ont[eid] = 1;
}
}
for (register int i = 1; i <= n; ++i) // 枚举每条非树边,更新答案
if (!ont[i] && tim[v[i][0]] == S && tim[v[i][1]] == S)
ans = std::min(ans, dis[v[i][0]] + dis[v[i][1]] + 1);
}
void solve(){
read(n);
init(1000000), p[0] = 1, vis[1] = 0;
for (register int i = 1, x; i <= n; ++i){
read(x);
for (register int j = 1; j <= cnt && 1ll * p[j] * p[j] <= x; ++j)
if (x % p[j] == 0){
int k = 0;
while (x % p[j] == 0) x /= p[j], k ^= 1;
if (k) v[i].push_back(j);
}
if (x > 1) v[i].push_back(vis[x]);
while (v[i].size() < 2) v[i].push_back(0);
E[v[i][1]].push_back({v[i][0], i}), E[v[i][0]].push_back({v[i][1], i});
// 连边
}
for (register int i = 0; i <= cnt; ++i) tim[i] = -1;
ans = INF;
for (register int i = 0; i <= cnt; ++i)
if (p[i] <= 1000) bfs(i); else break; // 只需要考虑编号 <=1000 且为质数的点
if (ans == INF) print(-1); else print(ans);
}

F - Ehab's Last Theorem

题目传送门

咕咕咕...


深深明白自己的弱小

评论

如需要头像服务请在「邮箱」中填写 Gravatar 中绑定的邮箱