Codeforces Round #628 (Div. 2) 爆蛋记
完全爆蛋，小号三场上橙无望 /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) 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 ; 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 ; if (ans == INF) print (-1 ); else print (ans); }
F - Ehab's Last Theorem
