「LYOI2020 Summer Day4」Solution

因为自己写的博客$\LaTeX$挂了还没修所以就把题解放$luogu$上了。 ### A. Nemure 既然要使次大公因数最大，先看看次大公因数怎么求。定义正整数$x$的最小质因子为$d(x)$。那么显然一个数$n$的不等于$n$的最大因子就是$\dfrac{n}{d(n)}$。因为$a,b$的所有公因数都是$\gcd(a,b)$的因子，所以$a,b$的次大公因数$sgcd(a,b)=\dfrac{\gcd(a,b)}{d(\gcd(a,b))}$，即最大公因数除以它的最小因子。下面分析一下$a,b,n$的关系： 对于$a,b$的任意一个公因数$x$，都有$x(\dfrac{a}{x}+\dfrac{b}{x})=n$，即$x$是$n$的因子。 对于$n$的任意一个因子$x$，可以令$a=x,b=n-x=x\times(\dfrac{n}{x}-1)$，即对于$n$的任意一个因子，都可以构造出$a,b$使得$x$是$a,b$的公因子。 综上所述，集合$\bigcup_{a+b=n}\{x\ |\ x|a,x|b\}$等于集合$\{x\ |\ x|n\}$。 所以$\max_{a+b=n}\gcd(a,b)=\max\bigcup_{a+b=n}\{x\ |\ x|a,x|b\}=\max\{x\ |\ x|n\}$，即最大公因数的集合等于$n$的因子集合。 显然，集合$\{x\ |\ x|n\}$中的每一个数除以它的最小质因子后，得到的集合就是次大公因数的集合。而次大公因数的集合最大值，等于最大公因数的集合最大值除以它的最小质因子，这是因为虽然每个数除以的最小质因子可能不同，但越大的数除以的最小质因子越小。 所以说$\max_{a+b=n}sgcd(a,b)=\dfrac{\max\{x\ |\ x|n\}}{d(\max\{x\ |\ x|n\})}$，即最大的次大公因数等于$\dfrac{n}{d(n)}$。但是我们要求$a,b$是正整数，如果$sgcd(a,b)=\dfrac{n}{d(n)}$，由次大公因数的计算公式可得$\gcd(a,b)=n$，即$a=0,b=n$或$a=n,b=0$，不符合题目要求。因此，满足题意的$n$的最大因子是$\dfrac{n}{d(n)}$，即答案是$\dfrac{\dfrac{n}{d(n)}}{d(\dfrac{n}{d(n)})}$。 可以用线性筛$O(n)$预处理每个数的最小质因子，然后对于每个询问$O(1)$计算答案。如果$n$是质数，则不存在合法方案。 ```cpp #include<cstdio> const int MAXN = 10001000; int t, n[MAXN], prime[MAXN], d[MAXN], maxn, pcnt; bool isprime[MAXN]; struct tools { static inline int max(int a, int b) { return a > b ? a : b; } }; inline int read() { register int ans = 0; register char c = getchar(); while (c == ' ' || c == '\n' || c == '\r') c = getchar(); while ('0' <= c && c <= '9') { ans = ans * 10 + c - '0'; c = getchar(); } return ans; } int main() { freopen("Nemure.in", "r", stdin); freopen("Nemure.out", "w", stdout); t = read(); for (int i = 1; i <= t; i++) n[i] = read(), maxn = tools::max(maxn, n[i]); for (int i = 2; i <= maxn; i++) isprime[i] = true; for (int i = 2; i <= maxn; i++) { if (isprime[i]) prime[++pcnt] = i, d[i] = i; for (int j = 1; j <= pcnt && i * prime[j] <= maxn; j++) { isprime[i * prime[j]] = false; d[i * prime[j]] = prime[j]; if (!(i % prime[j])) break; } } for (int i = 1; i <= t; i++) { if (isprime[n[i]]) printf("-1\n"); else printf("%d\n", n[i] / d[n[i]] / d[n[i] / d[n[i]]]); } return 0; } ``` ### B. ceramics 如果没有相邻边权的限制，本题就是求树上的边权和最大路径即树的直径。因为有负边权，所以假如要求直径的话只能树形$\texttt{DP}$。那么先来复习一下树形$\texttt{DP}$的方法(可以跳过)： 设点$x$到它的子树内的节点的最大边权和路径的边权和为$dp[x]$，$x$的子节点集合为$T$，点$t$到父节点的边权为$w_t$。则$dp[x]=\max_{t\in T}dp[t]+w_t$。树的直径就是$\max_{1\le x\le n}\max_{t_1\in T,t_2\in T,t_1\not=t_2}dp[t_1]+w_{t_1}+dp[t_2]+w_{t_2}$。所以对于每个节点可以枚举两个不相等的子节点并计算答案，复杂度$O(n^2)$。 考虑$dp[x]$更新的过程，在遍历到子节点$t$,且还未更新$dp[x]$时，$dp[x]=\max_{s\in T,s<t}dp[s]+w_s$，这里的$s<t$指$s$比$t$先被遍历到。因此可以用$dp[x]+dp[t]+w_t$来更新答案，省去了找已被遍历的最大值的时间。复杂度$O(n)$。 下面回到本题。我们魔改一下树形$\texttt{DP}$。设$dp[x]$为$x$到它的子树内的节点的最大边权和路径的边权和，且必须满足$|w_x-w_t|\le k$，其中$t$是路径上$x$的子节点。 在上面求树的直径时，我们让当前遍历到的节点加上已经遍历过的节点的最大值来更新答案，现在改成当前遍历到的节点加上已经遍历过并且符合相邻边权限制的节点的最大值，即$|w_t-w_s|\le k$。同样的，我们仍然可以$O(n^2)$枚举更新答案。 为了得到更优的复杂度，可以考虑把$x$的所有子节点$t$按照$w_t$排序，那么已经遍历过且符合相邻边权限制的节点集合是一个连续区间，随着$t$的增加(增加，指位置向右移)而单调递增，即滑动窗口，可以用单调队列$O(n)$维护，加上$O(nlogn)$的排序，总复杂度$O(nlogn)$。 现在考虑题目的另一个特殊条件：按照边权递增的顺序给出边。那么我们对每个节点维护它的子节点序列，每次加边就在序列末尾加入节点，这样加完边后整个序列的$w$就是递增的，无需排序，总复杂度$O(n)$。 ```cpp #include<cstdio> #include<vector> #include<queue> const int MAXN = 500100; int n, k; long long root; long long d[MAXN], diameter; bool ischild[MAXN]; struct node { int x, w; node(int xv = 0, int wv = 0): x(xv), w(wv) {} }; std::vector<node> children[MAXN]; inline int abs(int x) { return x > 0 ? x : -x; } inline long long max(long long a, long long b) { return a > b ? a : b; } void dfs(int x, int fa, int lstw) { for (int i = 0, s = (int)children[x].size(); i < s; i++) dfs(children[x][i].x, x, children[x][i].w); std::deque<node> q; for (int i = 0, s = (int)children[x].size(); i < s; i++) { int &t = children[x][i].x, w = children[x][i].w; while (!q.empty() && abs(q.front().w - w) > k) q.pop_front(); if (!q.empty()) diameter = max(diameter, d[q.front().x] + q.front().w + d[t] + w); diameter = max(diameter, d[t] + w); while (!q.empty() && d[q.back().x] + q.back().w <= d[t] + w) q.pop_back(); q.push_back(node(t, w)); if (!fa || abs(lstw - w) <= k) d[x] = max(d[x], d[t] + w); } q.clear(); } int main() { freopen("ceramics.in", "r", stdin); freopen("ceramics.out", "w", stdout); scanf("%d%d", &n, &k); root = n * (n + 1) / 2; for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); children[u].push_back(node(v, w)); root -= v; } dfs(root, 0, 0); printf("%lld\n", diameter); return 0; } ``` ### C. S.S.K $\texttt C$题标程写错了...dbq 不过把题目改成图中只有一个白点的话标程还是没问题的，所以最后把题目改成了只有一个白点，即出发点。 要使每个黑点到出发点的最短距离之和最小，就要使每个黑点到出发点的最短距离最小，因为黑点之间互不影响。那么很显然求的就是图的最短路径生成树。第一问只要把所有黑点的最短路长度加起来就好了，第二问是最短路径树计数。 首先看看普通的最短路径树计数怎么做。对于一条端点为$x,t$，边权为$w$的边，如果$dis[t]=dis[x]+w$，那么这就是一条可以出现在最短路径树上的边。这是一个类似$\texttt{Prim}$算法的过程，按照最短路从小到大的顺序枚举点$x$并把它加入生成树，遍历$x$的每一条出边，看看有几条边可以出现在最短路径树上，并把答案乘上数量。这是因为每次加入的边都互不影响，所以由乘法原理可以得出。 但本题中有边权为$0$的边，而$0$边可能被计算两次，解决方法是对图进行$\texttt{dfs}$，找出由$0$边连起来的所有连通块(也可能是单个的点)，然后把每个连通块同时加入生成树中。具体来说，在计算可以出现在最短路径树上的边时忽略掉连通块内部的边，然后把从点$x$找到的边的个数记为$cnt[x]$，然后计算整个连通块的方案数。每个点既可以选择直接连向生成树的边，也可以选择连向连通块的其他节点的边，两种选择互不影响，可以用乘法原理计算。因此，把连通块内所有节点的$cnt$值看作一个集合，那么整个连通块的方案数就是集合的所有子集的元素乘积之和。 设集合中前$x$个数字的所有子集的乘积之和为$dp[x]$，集合的第$x$个元素为$cnt[x]$，那么转移方程就是$dp[x]=dp[x-1]+dp[x-1]\times a[x]+a[x]$，可以$O(n)$计算。 求方案数的复杂度为$O(n+m)$，求最短路的复杂度为$O(nlogn)$，总复杂度$O(nlogn)$。而这题还有个特殊条件：边权$w\in\{0,1,2\}$。对于这个条件，可以用类似双端队列优化边权为$0,1$的最短路的方法，把最短路的复杂度降到$O(n)$。 我们求最短路时，要求队列中的元素是单调的，这样才能保证每次取出的是最小的节点。而双端队列优化的思路就是如果当前遍历的边权是$0$，就把到达的节点放在队首，否则如果是$1$，就放在队尾。显然，这样做仍然能保证队列的单调性，而复杂度降到了$O(n)$。 本题多出来一种边权为$2$的边，那么我们可以用类似的思路，开三个队列，并记下当前的队首所在的队列序号为$f$。如果当前遍历的边权是$0$，就放到序号$f$对应的队列里，如果边权是$1$就放到$(f+1)\bmod 3$对应的队列里，同理边权是$2$就放到$(f+2)\bmod 3$对应的队列里，然后剩下的操作就都很好实现了。这样求最短路复杂度就降到了$O(n+m)$，总复杂度也降到了$O(n+m)$。 不过$\texttt{STL}$实在是太快了，实测后面的测试点使用自己写的队列和$\texttt{STL}$的$\texttt{priority\_queue}$相比仅仅快了$\texttt{0.1s}$左右。 ```cpp #include<cstdio> #include<cstring> #include<queue> #include<vector> const int MAXN = 500100, MOD = 19260817; int n, m, s, dis[MAXN], cnt[MAXN]; long long ans, anscnt = 1; bool vis[MAXN]; struct edge { int to, next, w; }; struct graph { int ecnt = 1, head[MAXN]; edge edges[2000100]; inline void addedge(int u, int v, int w) { edges[++ecnt].to = v; edges[ecnt].w = w; edges[ecnt].next = head[u]; head[u] = ecnt; } }g; struct node { int x, dis; node(int xv = 0, int dv = 0): x(xv), dis(dv) {} }; struct queue { int f; std::queue<node> q[3]; inline int idx(int w) { return (f + w) % 3; } inline bool empty() { return q[0].empty() && q[1].empty() && q[2].empty(); } inline void refront() { if (q[f].empty()) { if (!q[idx(1)].empty()) f = idx(1); else if (!q[idx(2)].empty()) f = idx(2); } } inline void push(node x, int w) { q[idx(w)].push(x); } inline void pop() { q[f].pop(); } inline node front() { return q[f].front(); } }q; std::vector<int> nodes; inline int read() { register int ans = 0; register char c = getchar(); while (c == ' ' || c == '\n' || c == '\r') c = getchar(); while ('0' <= c && c <= '9') { ans = ans * 10 + c - '0'; c = getchar(); } return ans; } inline void dijkstra() { memset(dis, 0x3f, sizeof(int) * (n + 1)); q.push(node(s, 0), 0); dis[s] = 0; while (!q.empty()) { q.refront(); node f = q.front(); q.pop(); if (vis[f.x]) continue; vis[f.x] = true; for (int i = g.head[f.x]; i; i = g.edges[i].next) { int &t = g.edges[i].to, w = g.edges[i].w; if (dis[t] > dis[f.x] + w) { dis[t] = dis[f.x] + w; q.push(node(t, dis[t]), w); } } } } void dfs(int x, int lst) { if (x == s) return; nodes.push_back(x); vis[x] = true; for (int i = g.head[x]; i; i = g.edges[i].next) { if (i == (lst ^ 1)) continue; int &t = g.edges[i].to, w = g.edges[i].w; if (!w) dfs(t, i); } } int main() { freopen("S.S.K.in", "r", stdin); freopen("S.S.K.out", "w", stdout); n = read(); m = read(); s = read(); for (int i = 1; i <= m; i++) { int u, v, w; u = read(); v = read(); w = read(); g.addedge(u, v, w), g.addedge(v, u, w); } dijkstra(); for (int i = 1; i <= n; i++) if (i ^ s) ans += dis[i]; for (int x = 1; x <= n; x++) { if (x == s) continue; for (int i = g.head[x]; i; i = g.edges[i].next) { int &t = g.edges[i].to, w = g.edges[i].w; if (dis[x] == dis[t] + w && (t == s || ((t ^ s) && w))) cnt[x]++; } } memset(vis, 0, sizeof(bool) * (n + 1)); for (int x = 1; x <= n; x++) { if (x == s) continue; if (!vis[x]) { dfs(x, 0); int s = nodes.size(); long long cnttot = 0; for (int i = 1; i <= s; i++) { int a = cnt[nodes[i - 1]]; cnttot = ((cnttot + cnttot * a % MOD) % MOD + a) % MOD; } anscnt = (anscnt * cnttot) % MOD; nodes.clear(); } } printf("%lld %lld\n", ans, anscnt); return 0; } ``` ### Afterword 题目名称来源于日本后摇乐队$\texttt{3nd}$的样稿专辑《$\texttt{DEMO}$》。