【题解】牛客NOIP暑期七天营-提高组1
T1: 最短路
对于第一档部分分,构造一朵菊花,直接从 向其他节点连对应权值的边即可。期望得分 分。
对于第二档部分分,我们希望每一个点都从最近的那个点连过来。也就是说,对于某个点 ,我们可以找到一个 ,满足 并且 尽可能大,然后从 向 连一条权值为 的边。可以证明这样构造出的图一定是最优的(最大边边权最小的),因此若找不到点 (即 )或 ,则一定无解。暴力找前驱 可以做到 的复杂度。结合上一档部分分可以拿到 分。
对于所有数据,可以优化这个找点的过程。我们不妨将所有节点按照权值先排序,然后我们发现,随着 的增大,点 一定不会减小,因此用双指针扫描法即可找到这个 。当然用二分查找也是可以的。复杂度 ,期望得分 分。
#include <algorithm> #include <cstdio> #include <cstring> const int MaxN = 50000 + 5, MaxM = 100000 + 5; int N, M, S; int A[MaxN], Lnk[MaxN]; int U[MaxM], V[MaxM], W[MaxM]; void init() { scanf("%d %d", &N, &S); for (int i = 1; i <= N; ++i) { scanf("%d", &A[i]); Lnk[i] = i; } } inline bool cmp(int x, int y) { if (A[x] != A[y]) return A[x] < A[y]; else return x < y; } void solve() { std::sort(Lnk + 1, Lnk + 1 + N, cmp); for (int i = 2, j = 1; i <= N; ++i) { while (j < N && A[Lnk[j + 1]] != A[Lnk[i]]) j++; M++; U[M] = Lnk[j], V[M] = Lnk[i], W[M] = A[Lnk[i]] - A[Lnk[j]]; } bool ok = true; for (int i = 1; i <= M; ++i) if (W[i] < 1 || W[i] > S) ok = false; if (ok == false) printf("%d\n", -1); else { printf("%d\n", M); for (int i = 1; i <= M; ++i) printf("%d %d %d\n", U[i], V[i], W[i]); } } int main() { // freopen("a.in", "r", stdin); // freopen("a.out", "w", stdout); init(); solve(); return 0; }
T2: 最小生成链
首先简单地说一下某几档部分分的做法:
,枚举每条链,得到最小值即可。时间复杂度 。
,类似于旅行商问题的做法,状压 DP 维护一个数组 表示目前这条链延伸到节点 ,链中包含的节点集合为 时,链中最大值的最小值。每次 枚举下一个节点直接转移过去即可。时间复杂度 ,由于遍历到的状态不多,是可以通过 的数据的。
,能够证明最小生成链最大边权一定是最小生成树的最大边权。暴力写个 Prim 可以做到 ,用 Boruvka + Trie 树求最小生成树可以做到复杂度 ,详见 CF888G Xor-MST。
证明:首先最小生成树的最大边一定不大于最小生成链的最大边,然后按照下文的做法分为 两块后,中间这条边就是最小生成链最大边。如果不连上这条边,那么 的连通块和 的连通块无法连通。因此这条边一定在最小生成树中,也就是说最小生成树的最大边不小于最小生成链的最大边。于是就证明了两种的最大边相等。
原问题在完全图上,边数达到了 级别。直接在原图上处理显然是不行的,因此考虑转化问题。
众所周知,我们可以从左往右唯一的遍历一条链,这样得到的遍历序实际上就是一个序列。因此,一条链与一个序列是可以一一对应的。也就是说,对于一个 个点若干条边的图,它当中存在的所有生成链对应的就是 到 的一个排列,且这个排列满足相邻元素间在原图中有边。
由于题目中给出的图是完全图,因此 到 的所有 种排列都是符合要求的。于是原题就可以转化为:
给出一个长度为 的序列 ,请找出一个排列,使得相邻两元素间异或值的最大值最小。
现在我们看到特殊性质:序列中的元素只有 或 。
相信大家都能推得出来这个子任务的结论:当序列中所有元素都是 或都是 时,答案为 ;否则——序列中既有元素 又有元素 时,答案为 。
为什么会这样呢?感性理解一下,就是原序列中既有 也有 ,那么无论如何都避免不了有至少一组 和 相邻,因此最大值至少就为 。
我们把这个情况推广一下。由于位运算任意两位是不会互相影响的,我们考虑提取出原数列中的第 位,单独考虑这一位的情况。我们容易发现,对于这独立的一位,同样满足类似性质——当原序列中所有数在这一位上都是 或都是 时,这位的答案一定是 ;否则这位答案一定是 。
相信大家可以已经有一些想法了。
接下来我们需要回想起进制的一个有趣的性质,这也是我们经常利用的来做贪心的性质。也就是对于该进制的某一位 ,如果有两个数 ,满足 高于 的位全部相等并且 在第 位比 在第 位上的数大,那么无论低于 的位是什么样的, 一定大于 。
二进制也满足这个性质。因此我们考虑找出最高的一位满足原数列中所有数在这一位上既有 也有 ,那么我们就可以根据这一位的值将原序列分成这一位为 和这一位为 的两部分。我们不难发现,对于这每个部分内,由于这个最高位是 ,因此永远不可能出现最大值。这个序列的最大值一定是出现在 和 交界的部分。
我们希望这个交界的部分两元素异或值最小。也就是说,我们需要从这一位为 的元素中和这一位为 的元素中各找出一个元素,使得这两个元素的异或值最小。
于是有一个显而易见的 做法,枚举任意两个元素,找出异或值的最小值。解决了 。
接下来这个找最小值的过程可以进行优化。这里有异或操作,很自然地能够想到 0-1 Trie。我们可以维护一棵 0-1 Trie,我们将序列中所有这一位为 的元素插入这棵 Trie,然后用所有这一位为 的元素去 Trie 中查异或最小值。最后所有最小值的最小值就是答案了。
要注意特判一下所有元素都相同的情况,因为这会找不到这个最高的位满足这一位上有 和 。
时间复杂度和空间复杂度都是 。
#include <algorithm> #include <cstdio> #include <cstring> #include <vector> const int MaxN = 1000000 + 5; const long long INF = 0x7F7F7F7F7F7F7F7F; int N; long long A[MaxN]; struct Trie { int cntv; std::vector<int> ch[2]; Trie() { cntv = 1; } inline void insert(long long x) { int u = 1; for (int i = 59; i >= 0; --i) { int c = (x & (1LL << i)) ? 1 : 0; if (ch[c][u] == 0) ch[c][u] = ++cntv; u = ch[c][u]; } } inline long long qmin(long long x) { long long res = 0; int u = 1; for (int i = 59; i >= 0; --i) { int c = (x & (1LL << i)) ? 1 : 0; if (ch[c][u] != 0) u = ch[c][u]; else { res |= (1LL << i); u = ch[c ^ 1][u]; } } return res; } }; Trie T; void init() { scanf("%d", &N); for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]); T.ch[0].resize(N * 60 + 5); T.ch[1].resize(N * 60 + 5); } void solve() { std::sort(A + 1, A + 1 + N); int maxBit = -1; for (int i = 59; i >= 0; --i) if ((A[1] ^ A[N]) & (1LL << i)) { maxBit = i; break; } if (maxBit == -1) { printf("%d\n", 0); return; } long long Ans = INF; for (int i = 1; i <= N; ++i) { if (A[i] & (1LL << maxBit)) Ans = std::min(Ans, T.qmin(A[i])); else T.insert(A[i]); } printf("%lld\n", Ans); } int main() { // freopen("b.in", "r", stdin); // freopen("b.out", "w", stdout); init(); solve(); return 0; }
T3: 最小字典最短路
这是一道码农题 QwQ 思路可能很简单,但是代码写起来有点麻烦。我在此为自己的毒瘤向大家致歉。。。
对于 均不超过 的部分分,每次询问的时候都枚举起点 ,然后跑 SPFA 并路径还原找到 和 这两条最短路径,求一下公共路径长度,然后更新一下最大值即可。复杂度 。
对于数据随机的部分分,可以把询问先读入进来。将出发点提前枚举,求出到每个点的最短路径,然后再处理这个出发点对每个询问的贡献。由于数据随机,因此最短路经过边数的期望可以视作小常数 ,应该不会超过 。复杂度 。
的部分分是准备给写挂或者被卡空间的正解的。
对于 的数据,使用 SPFA 算法(您应该能猜到为什么不是“对于所有数据”了)跑出每个起点到其它点的最短路树。最短路树是一种满足如下条件的树:
- 这是一棵有根树,以起点 为根节点。
- 每个节点的父亲就是它在起点 到它的最短路径上的前驱节点。换句话说, 点的父亲节点 就是在最短路转移时最终的 这个 节点。
最短路树拥有一个很重要的性质:每个节点 到根 的这条路径,就是原图上 到 的最短路。
于是本问题转化为,对每个询问,找到一个根节点,使得 在最短路树上的 LCA 到根距离最长。
这样本题就基本完成了,先用 DFS 跑出每个点的最短路树,然后对最短路树树剖,然后枚举每个询问,用树剖查找在这个最短路树上的 LCA,用根到 LCA 的最短路长度直接更新这个询问对应的答案即可。但是这题空间只开 32 MiB,建出 棵最短路树会炸空间。因此要把询问离线读进来,枚举最短路树的根,然后再对每一个询问进行查询,用完后把最短路树滚动掉,让下一个起点接着用。复杂度 ,~~ 是基于图的小常数~~。
不知道 SPFA 加一些奇奇怪怪的优化能不能通过本题,至少我的 SLF+LLL 优化都被卡了。如果想要做到满分,需要一种类似于解决费用流时我们学过的原始对偶算法的 Johnson 算法。
Johnson 算法大致过程是,先建一个虚拟的 号点,从 号点向 号点都连一条权值为 的有向边,然后跑一遍 SPFA。得到的最短路数组我们记作 , 称为 号点的势。
之后我们把原图进行一些奇妙的改造:将原图上每条边——不妨记作一条 连向 权值为 的有向边——的边权变为 。这样一来所有边权就都是非负的了,可以直接把 SPFA 换成 Dijkstra 算法(这是因为最短路满足三角形不等式 ,移项之后可得 )。
而且对于一条路径 ,则路径长度为 ,中间所有 项全部消掉了,最后剩下 项之和加上 减掉 。也就是说,在这张新图上任意两节点最短路 ,都与它们在原图上最短路 有如下等式关系:。由于 是一个常数,因此在新图上最短路路径的形状也是不会改变的,改变的只是路径长度而已,而路径长度改变量又是可以推回去的,因此 Johnson 算法就没有问题了。
在 做法的基础上,用 Johnson 替代 SPFA 即可,时间复杂度 ,空间复杂度 。
#include <algorithm> #include <cstdio> #include <cstring> #include <functional> #include <queue> #include <utility> #include <vector> const int MaxV = 2000 + 5, MaxE = 8000 + 5; const int MaxQ = 6000 + 5; const int INF = 0x7F7F7F7F; struct Graph { int cnte; int Head[MaxV], To[MaxE], Next[MaxE], Val[MaxE]; inline void add_edge(int from, int to, int val) { cnte++; To[cnte] = to; Val[cnte] = val; Next[cnte] = Head[from]; Head[from] = cnte; } }; struct Tree { int cnte; int Head[MaxV], To[MaxV], Next[MaxV], Val[MaxV]; int fa[MaxV], dep[MaxV], siz[MaxV], wson[MaxV], top[MaxV], dis[MaxV]; inline void clear() { cnte = 0; memset(Head, 0, sizeof Head); memset(To, 0, sizeof To); memset(Next, 0, sizeof Next); memset(Val, 0, sizeof Val); memset(fa, 0, sizeof fa); memset(dep, 0, sizeof dep); memset(siz, 0, sizeof siz); memset(wson, 0, sizeof wson); memset(top, 0, sizeof top); memset(dis, 0, sizeof dis); } inline void add_edge(int from, int to, int val) { cnte++; To[cnte] = to; Val[cnte] = val; Next[cnte] = Head[from]; Head[from] = cnte; } void dfs1(int u) { siz[u] = 1; for (int i = Head[u]; i; i = Next[i]) { int v = To[i], w = Val[i]; fa[v] = u; dep[v] = dep[u] + 1; dis[v] = dis[u] + w; dfs1(v); siz[u] += siz[v]; if (siz[v] > siz[wson[u]]) wson[u] = v; } } void dfs2(int u, int chain) { top[u] = chain; if (wson[u] != 0) dfs2(wson[u], chain); for (int i = Head[u]; i; i = Next[i]) { int v = To[i]; if (v == wson[u]) continue; dfs2(v, v); } } void getRelation(int rt) { dfs1(rt); dfs2(rt, rt); } inline int getLca(int u, int v) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) std::swap(u, v); u = fa[top[u]]; } return dep[u] < dep[v] ? u : v; } }; int N, M, Q; int X[MaxQ], Y[MaxQ], Ans[MaxQ]; int H[MaxV], dis[MaxV]; Graph G1, G2; Tree T; std::vector<int> G[MaxV]; void init() { scanf("%d %d %d", &N, &M, &Q); for (int i = 1; i <= M; ++i) { int u, v, w; scanf("%d %d %d", &u, &v, &w); G1.add_edge(u, v, w); } for (int i = 1; i <= Q; ++i) scanf("%d %d", &X[i], &Y[i]); } void SPFA(int s) { std::queue<int> que; static bool in_queue[MaxV]; memset(in_queue, false, sizeof in_queue); memset(H, 0x7F, sizeof H); H[s] = 0; que.push(s); in_queue[s] = true; while (!que.empty()) { int u = que.front(); que.pop(); in_queue[u] = false; for (int i = G1.Head[u]; i; i = G1.Next[i]) { int v = G1.To[i], w = G1.Val[i]; if (H[u] + w < H[v]) { H[v] = H[u] + w; if (in_queue[v] == false) { que.push(v); in_queue[v] = true; } } } } } void Dijkstra(int s) { std::priority_queue< std::pair<int, int> > pq; static bool vis[MaxV]; memset(vis, false, sizeof vis); memset(dis, 0x7F, sizeof dis); dis[s] = 0; pq.push(std::make_pair(dis[s], s)); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u] == true) continue; vis[u] = true; for (int i = G2.Head[u]; i; i = G2.Next[i]) { int v = G2.To[i], w = G2.Val[i]; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; pq.push(std::make_pair(-dis[v], v)); } } } } bool bsptVis[MaxV]; void buildShortestPathTree(int u) { for (std::vector<int>::iterator it = G[u].begin(); it != G[u].end(); ++it) { int v = *it; if (bsptVis[v] == false) { bsptVis[v] = true; buildShortestPathTree(v); T.add_edge(u, v, dis[v] - dis[u] + H[v] - H[u]); } } } void solve() { memset(Ans, -1, sizeof Ans); for (int i = 1; i <= N; ++i) G1.add_edge(0, i, 0); SPFA(0); for (int u = 1; u <= N; ++u) { for (int i = G1.Head[u]; i; i = G1.Next[i]) { int v = G1.To[i], w = G1.Val[i]; G2.add_edge(u, v, w + H[u] - H[v]); } } for (int i = 1; i <= N; ++i) { T.clear(); Dijkstra(i); for (int u = 1; u <= N; ++u) { G[u].clear(); for (int e = G2.Head[u]; e; e = G2.Next[e]) { int v = G2.To[e], w = G2.Val[e]; if (dis[u] != INF && dis[v] != INF && dis[u] + w == dis[v]) { G[u].push_back(v); } } std::sort(G[u].begin(), G[u].end()); } memset(bsptVis, false, sizeof bsptVis); bsptVis[i] = true; buildShortestPathTree(i); T.getRelation(i); for (int q = 1; q <= Q; ++q) { int u = X[q], v = Y[q]; if (i != u && T.dep[u] == 0) continue; if (i != v && T.dep[v] == 0) continue; Ans[q] = std::max(Ans[q], T.dis[T.getLca(u, v)]); } } for (int i = 1; i <= Q; ++i) printf("%d\n", Ans[i]); } int main() { // freopen("c.in", "r", stdin); // freopen("c.out", "w", stdout); init(); solve(); return 0; }#内推#