T3 数字
题意
一棵树,每个点 \(u\) 向 \(\frac {u} {\text{minprime}_u}\) 连边,其中 \(\text{minprime}_u\) 表示 \(u\) 的最小质因子。
\(q\) 次询问两个点 \(x,y\) 的 lca。
\(q \le 10 ^ 6, x, y \le 10 ^ 9\)
思路
发现一个点到根的路径上的数实际上是:将这个数分解质因数后,将质因子从大到小排序,前缀积就是路径上的数。
那么两个点的 lca 相当于求这两个数分解质因数后,质因子从大到小排序的最长公共前缀。
暴力分解质因数是可以做到 \(\frac {\sqrt x} {\log _ 2 x}\) 的(在根号枚举因数的基础上改为枚举根号以内的质数)。
考虑如何优化,我们发现最后的答案
(挖坑)
T4 旅行
题意
给一棵树,每个边上有一个区间 \([l,r]\),问树上有多少点对 \((u,v)\) 满足 \(u\) 到 \(v\) 的路径上区间的交不是空集。
\(n \le 5 \times 10 ^ 5\)
思路
点对问题点分治,维护每个点到分治中心的路径上的区间交 \(len\)。
在分治中心 \(u\) 统计答案,枚举当前一个儿子 \(v\) 的子树里的 \(len\) 桶,对一个 \(len = [l,r]\) 去计算和这个区间有交的区间 $ ^ 1$ 个数。
\(^ 1\):此处区间指的是已经遍历过的子树里贡献的区间,不算 \(v\) 的子树,因为我们统计的是经过 \(u\)。
我们发现,只需要统计有多少区间的 \(l'\) 或 \(r'\) 在 \([l,r]\) 里即可,树状数组维护。
时间复杂度 \(O(n \log _ 2 ^ 2 n)\),但是树状数组常数小,可以随便跑。
代码
#define int ll
const int N = 1e6 + 5;
int n;
struct edge{int v;pair<int, int> w;
};
pair<int, int> operator + (pair<int, int> x, pair<int, int> y){if(max(x.first, y.first) > min(x.second, y.second)) return {-1, -1};return {max(x.first, y.first), min(x.second, y.second)};
}
vector<edge> e[N];struct BIT{int c[N];void reset(int n){rep(i, 1, n) c[i] = 0;}inline int lowbit(int x) { return x & -x; }void add(int i, int v){for(; i <= n; i += lowbit(i)){c[i] += v;}}int query(int i){if(i <= 0) return 0;int res = 0;for(; i; i -= lowbit(i)){res += c[i];}return res;}
} BIT_l, BIT_r;int ans;int rt;
int siz[N];
int mxsiz[N];
bool vis[N];
int node_tot;
void get_rt(int u, int fa){siz[u] = 1;mxsiz[u] = 0;for(auto [v, w] : e[u]){if(v == fa || vis[v]) continue;get_rt(v, u);siz[u] += siz[v];chkmx(mxsiz[u], siz[v]);}chkmx(mxsiz[u], node_tot - siz[u]);if(mxsiz[u] < mxsiz[rt]) rt = u;
}
pair<int, int> len[N];
vector<pair<int, int>> bin;
vector<pair<int, int>> toclear;void get_len(int u, int fa){if(len[u].first == -1 && len[u].second == -1){return;}bin.push_back(len[u]);for(auto [v, w] : e[u]){if(v == fa || vis[v]) continue;len[v] = len[u] + w;get_len(v, u);}
}
void calc(int u){toclear.clear();for(auto [v, w] : e[u]){if(vis[v]) continue;bin.clear();len[v] = w;get_len(v, u);ans += bin.size();for(pair<int, int> x : bin){ans += BIT_l.query(x.second) - BIT_r.query(x.first - 1);}for(pair<int, int> x : bin){BIT_l.add(x.first, 1);BIT_r.add(x.second, 1);toclear.push_back(x);}}for(pair<int, int> x : toclear){BIT_l.add(x.first, -1);BIT_r.add(x.second, -1);}toclear.clear();
}
void solve(int u){vis[u] = 1;calc(u);for(auto [v, w] : e[u]){if(vis[v]) continue;node_tot = siz[v];mxsiz[rt = 0] = node_tot;get_rt(v, 0);solve(rt);}
}
void solve_test_case(){n = read();rep(i, 1, n - 1){int u = read(), v = read(), l = read(), r = read();e[u].push_back({v, {l, r}});e[v].push_back({u, {l, r}});}BIT_l.reset(n), BIT_r.reset(n);rt = 0;mxsiz[0] = n;node_tot = n;get_rt(1, 0);solve(rt);write(ans);
}
此后的题目都是2025中山大学程序设计竞赛原题。
Ecosystem
题意
给出一个长为 \(n\) 的序列 \(a\),\(q\) 次询问有多少种用若干 \(a\) 的元素凑出 \(t\) 的方案。
\(n, a_i \leq 100, t \leq 10 ^ 9\)。
思路
dp 题,\(dp_i\) 表示和为 \(i\) 的方案个数。
\(t\) 很大,显然要矩阵乘法。
维护一个向量 $$\begin{bmatrix} dp_{i-99} & dp_{i - 98} & \cdots & dp_{i} \end{bmatrix}$$。
转移矩阵很好构造,只需要注意最后一列,注意 \(a\) 重复的情况即可。
然后发现时间复杂度 \(O(n ^ 3 q \log _ 2 n)\)(\(q\) 次询问,每次快速幂 \(\log _ 2 n\),矩阵乘法 \(n ^ 3\))
过不了,考虑优化,发现向量乘矩阵的复杂度是 \(O(n ^ 2)\),那么我们二进制拆分 $t = {x_0} ^ {\alpha_0} + {x_1} ^ {\alpha_1} + $