当前位置: 首页 > news >正文

SZMS 251009 订题赛 题解

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} + $

http://www.hskmm.com/?act=detail&tid=31678

相关文章:

  • Debian 12安装docker的正确方法
  • 【流量网关】k8s与apisix统一的流量入口方案(内网版)
  • 基于STM32F4系列MCU和CS5530 24位SDADC的称重传感器系统实现
  • 2025 年环保板材厂家最新推荐榜:硬包板 / 竹木纤维板等全品类 企业深度解析
  • kong 网关下集成 Consul服务注册与发现
  • cad圆滑连接两段线:blend
  • 在 gitea 服务器端查询 lfs 文件占用情况
  • HDR图像生成算法详解
  • Introduction: Why Optimization?
  • 基于MATLAB的二自由度机械臂PID控制仿真
  • Spring AOP原理
  • Ventoy引导Kali live USB持久化
  • 知识库管理工具深度测评:ONES、Confluence 等10款工具全面对比
  • 好的测试数据管理,到底要怎么做?
  • 【面试题】人工智能工程师高频面试题汇总:循环神经网络篇(题目+答案)
  • 做了个手机上的“视频播放器”,获益匪浅
  • CEF关闭流程
  • AI一周资讯 251005-251015
  • 2025 年中空百叶源头厂家最新推荐排行榜:聚焦国内优质供货商,助力客户精准选购可靠产品光能/光伏/电动/光动中空百叶厂家推荐
  • 2025年学校家具定制厂家最新权威推荐榜:全屋定制/衣柜/厨柜/酒柜/鞋柜/猫柜/酒店办公家具/电视柜/书包柜/图书架/宿舍上下床
  • iOS框架内存中占用很高的ttc文件是否正常
  • Linux配置SSH名称通信
  • MPC模型预测控制:原理、设计与MATLAB实现
  • 2025年焊接变位机厂家最新权威推荐榜:双轴变位机专业制造商,高效稳定助力智能焊接升级
  • 体育视频分析中的计算机视觉技术创新
  • 2025年法兰罩厂家最新权威推荐榜:专业防护与精密制造,工业管道安全守护者优选品牌
  • 2025 年膜结构厂家最新推荐排行榜:含车棚 / 看台 / 景观等产品实力企业盘点与选择指南
  • 题解:qoj7303 City United
  • 多网融合实战指南:4G、Wi-Fi与以太网的智能协同之道
  • 最佳实践:基于Apache SeaTunnel从MySQL同步到PostgreSQL