2015年蓝桥杯省赛C/C++ A组 灾后重建题解(100分)

10. 灾后重建

Pear市一共有N(<=50000)个居民点,居民点之间有M(<=200000)条双向道路相连。这些居民点两两之间都可以通过双向道路到达。这种情况一直持续到最近,一次严重的地震毁坏了全部M条道路。
震后,Pear打算修复其中一些道路,修理第i条道路需要Pi的时间。不过,Pear并不打算让全部的点连通,而是选择一些标号特殊的点让他们连通。
Pear有Q(<=50000)次询问,每次询问,他会选择所有编号在[l,r]之间,并且 编号 mod K = C 的点,修理一些路使得它们连通。由于所有道路的修理可以同时开工,所以完成修理的时间取决于花费时间最长的一条路,即涉及到的道路中Pi的最大值。

你能帮助Pear计算出每次询问时需要花费的最少时间么?这里询问是独立的,也就是上一个询问里的修理计划并没有付诸行动。

【输入格式】
第一行三个正整数N、M、Q,含义如题面所述。
接下来M行,每行三个正整数Xi、Yi、Pi,表示一条连接Xi和Yi的双向道路,修复需要Pi的时间。可能有自环,可能有重边。1<=Pi<=1000000。
接下来Q行,每行四个正整数Li、Ri、Ki、Ci,表示这次询问的点是[Li,Ri]区间中所有编号Mod Ki=Ci的点。保证参与询问的点至少有两个。

【输出格式】
输出Q行,每行一个正整数表示对应询问的答案。

【样例输入】
7 10 4
1 3 10
2 6 9
4 1 5
3 7 4
3 6 9
1 5 8
2 7 4
3 2 10
1 7 6
7 6 9
1 7 1 0
1 7 3 1
2 5 1 0
3 7 2 1

【样例输出】
9
6
8
8

【数据范围】
对于20%的数据,N,M,Q<=30
对于40%的数据,N,M,Q<=2000
对于100%的数据,N<=50000,M<=2*10^5,Q<=50000. Pi<=10^6.
Li,Ri,Ki均在[1,N]范围内,Ci在[0,对应询问的Ki)范围内。

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 5000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。

这题比较复杂,算法总共要分为三个部分。

首先,每次询问其实都是给出一个特定点集,要求最小化把这些点连通的边权的最大值。
那么,该问题是MST问题的变体 最小生成树资料
进一步地,对于每次询问,最佳方案的边都在原图的最小生成树中,可由反证法证得。
因此,算法的第一部分就是抛弃原图,只留下最小生成树,边数减少到 n − 1 n-1 n1,并且有很多好用的特征。
任选一点使之成为有根树,树上任意两点有且仅有一条简单路径,也即两点分别向上连到LCA 最近公共祖先资料

本题所取点集与除法取模有关,可以考虑 Big Small 分界。参考资料:fold的毒瘤题
设定一个阈值 T T T

  1. k > T k>T k>T时,点数约为 n k \frac{n}{k} kn,至多为 n T \frac{n}{T} Tn,顺序遍历所有点是可接受的。
    可以对LCA分类讨论证得,点1点3路径的最大值,其实已包含在点1点2路径和点2点3路径。
    因此,对于特定点集并不需要两两求LCA,只需要对“相邻”点顺序求过去就行。
    由于原图的MST不会变动,可以采用倍增预处理的方法作为算法的第二部分。
  2. k < = T k<=T k<=T时, k k k的取值至多有 T T T种,遍历不同的 k k k是可接受的。
    考虑到上述“相邻”的特性,其实对于同一组 ( k , c ) (k,c) (k,c),就是多次查询不同的 ( l , r ) (l,r) (l,r)区间,
    因为本题允许离线处理,可以把所有符合条件的点的路径建立数据结构,这是算法的第三部分。
    同样是没有修改,这里用线段树来优化查询速度 线段树资料

T T T n \sqrt n n 时,总体复杂度最小。

进一步分析发现,该方法还可以简化,下面说明只用线段树方法复杂度仍然是正确的。
考虑最极端情况,每次询问的 ( k , c ) (k,c) (k,c)均不同,每次都需要重新建树,因为 k k k越小点集越大,且对于每个 k k k c c c各有 k k k种取值,因此求LCA和建树的总复杂度为
T ( n ) = n 1 ( log ⁡ n + log ⁡ n 1 ) + ( n 2 ( log ⁡ n + log ⁡ n 2 ) ) × 2 + ( n 3 ( log ⁡ n + log ⁡ n 3 ) ) × 3 + … T(n) = \frac{n}{1}(\log n + \log \frac{n}{1}) + (\frac{n}{2}(\log n + \log \frac{n}{2})) \times 2 + (\frac{n}{3}(\log n + \log \frac{n}{3})) \times 3 + \dots T(n)=1n(logn+log1n)+(2n(logn+log2n))×2+(3n(logn+log3n))×3+
≤ n ⋅ 2 log ⁡ n + n ⋅ 2 log ⁡ n + n ⋅ 2 log ⁡ n + … \le n \cdot 2 \log n + n \cdot 2 \log n + n \cdot 2 \log n + \dots n2logn+n2logn+n2logn+
= O ( n ⋅ n ⋅ log ⁡ n ) = O(\sqrt{n} \cdot n \cdot \log n) =O(n nlogn)

查询的总复杂度显然是 O ( q ⋅ log ⁡ n ) O(q \cdot \log n) O(qlogn),两部分都完全没毛病。

本题从 Big Small 分界出发,到最后发现其实并不需要 Big Small 分界,直接建简化线段树的复杂度也是没有问题的,真是挺有趣的。

不过在线练习系统只给了1s的时限就比较紧,这就必须得套个读入优化才能保证每次都过了,读入量接近百万级(20w*3+5w*4)。

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 50010;
const int M = 200010;
const int FN = 16;
vector<PII> G[N];
int dep[N], ans[N];
int fa[N][FN], val[N][FN];
struct Que {int x, l, r, k, c;
} que[N];
bool debug = false;inline void getmax(int& x, int y)
{if (y > x)x = y;
}namespace Kruskal {
int p[N], ra[N];
struct Edge {int u, v, w;
} eg[M];int cmp(const Edge& p1, const Edge& p2) { return p1.w < p2.w; }int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }int merge(int x, int y)
{x = find(x);y = find(y);if (x == y)return 0;if (ra[x] > ra[y]) {p[y] = x;} else {if (ra[x] == ra[y])ra[y]++;p[x] = y;}return 1;
}void build(int kn, int km)
{int cnt = 0;for (int i = 1; i <= kn; i++) {p[i] = i;ra[i] = 0;}sort(eg + 1, eg + km + 1, cmp);for (int i = 1; i <= km; i++) {if (merge(eg[i].u, eg[i].v)) {G[eg[i].u].push_back(PII(eg[i].v, eg[i].w));G[eg[i].v].push_back(PII(eg[i].u, eg[i].w));if (++cnt == kn - 1)break;}}
}
} // namespace Kruskalclass SegTree {
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
public:int key[N << 2];void build(int a[], int rt, int l, int r){if (l == r) {key[rt] = a[l];return;}int m = (l + r) >> 1;build(a, lson);build(a, rson);push_up(rt);}int query(int rt, int l, int r, int L, int R){if (L <= l && r <= R) {return key[rt];}int m = (l + r) >> 1;int res = 0;if (L <= m)getmax(res, query(lson, L, R));if (m < R)getmax(res, query(rson, L, R));return res;}private:inline void push_up(int rt){key[rt] = max(key[rt << 1], key[rt << 1 | 1]);}
#undef lson
#undef rson
};
SegTree T;void dfs(int u, int x)
{for (size_t i = 0; i < G[u].size(); i++) {int v = G[u][i].first;int w = G[u][i].second;if (v != x) {dep[v] = dep[u] + 1;fa[v][0] = u;val[v][0] = w;dfs(v, u);}}
}bool cmpkc(const Que& p, const Que& q)
{return p.k < q.k || (p.k == q.k && p.c < q.c);
}int query(int x, int y)
{if (x == 0)return 0;if (dep[x] > dep[y])swap(x, y);int res = 0, di = dep[y] - dep[x];for (int k = 0; k < FN; k++) {if ((di >> k) & 1) {getmax(res, val[y][k]);y = fa[y][k];}}int k = FN - 1;while (x != y) {while (k > 0 && fa[x][k] == fa[y][k])--k;getmax(res, val[x][k]);getmax(res, val[y][k]);x = fa[x][k];y = fa[y][k];}return res;
}template <class T>
inline bool read(T& x)
{char c;int neg = 0;if (c = getchar(), c == EOF)return false; // EOFwhile (c != '-' && (c < '0' || c > '9'))c = getchar();if (c == '-')neg = 1, c = getchar();x = (c - '0');while (c = getchar(), c >= '0' && c <= '9')x = (x << 3) + (x << 1) + (c - '0');if (neg)x = -x;return true;
}int main()
{int n, m, q;read(n);read(m);read(q);{using namespace Kruskal;for (int i = 1; i <= m; i++) {read(eg[i].u);read(eg[i].v);read(eg[i].w);}build(n, m);} // now G is MSTfa[1][0] = 1;dep[1] = 1;dfs(1, 0);for (int k = 1; k < FN; k++) {for (int i = 1; i <= n; i++) {fa[i][k] = fa[fa[i][k - 1]][k - 1];val[i][k] = max(val[i][k - 1], val[fa[i][k - 1]][k - 1]);}}for (int i = 1; i <= q; i++) {read(que[i].l);read(que[i].r);read(que[i].k);read(que[i].c);que[i].x = i;}sort(que + 1, que + q + 1, cmpkc);int tmp[N], tlen;for (int x = 1; x <= q; x++) {int k = que[x].k, c = que[x].c;if (k != que[x - 1].k || c != que[x - 1].c) {// not same, rebuild segtreetlen = 0;for (int i = c; i + k <= n; i += k) {tmp[++tlen] = query(i, i + k);}T.build(tmp, 1, 1, tlen);}ans[que[x].x] = T.query(1, 1, tlen, (que[x].l - c + k - 1) / k + 1, (que[x].r - c) / k);}for (int i = 1; i <= q; i++) {printf("%d\n", ans[i]);}return 0;
}

评测记录截图

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/141930.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

拉斯克奖(Lasker Award)2023

拉斯克奖&#xff08;Lasker Award&#xff09;2023 &#x1f508;&#x1f508;&#x1f508;&#xff1a;DeepMind的两位科学家获得了拉斯克奖&#xff0c;这让人不禁对今年的诺贝奖展开大胆的预测。 1. 拉斯克奖&#xff08;Lasker Award&#xff09;简介 Lasker-DeBakey…

k8s手动下载镜像、通过容器创建镜像方法

手动下载镜像 1、首先pull镜像到本地 docker pull <镜像名称>:<标签>2、转储镜像 docker save -o /path/to/save/image.tar 3、解压 tar -xvf /path/to/save/image.tar补充 1、如果要将tar还原成镜像 docker load -i /path/to/save/image.tar或者用输入重定向…

yolov8训练自己的数据集(标注到训练)

yolov8可以用作目标检测&#xff0c;分割&#xff0c;姿态&#xff0c;跟踪。这里举例目标检测从标注到训练的过程。 官网连接 先把代码下载下来&#xff0c;这个不用说了。 然后准备数据集&#xff0c;创建一个文件夹dataset&#xff08;自己命名&#xff09;&#xff0c;下面…

在Linux中通过docker安装宝塔面板

先在Linux中手动安装docker&#xff0c;然后在docker中安装宝塔面板&#xff0c;并进行docker网络端口映射。 手动安装docker 第一步&#xff0c;卸载旧版本docker。 若系统中已安装旧版本docker&#xff0c;则需要卸载旧版本docker以及与旧版本docker相关的依赖项。 命令&…

pdf怎么压缩?pdf压缩方法大全

pdf怎么压缩&#xff1f;PDF是一种广受欢迎的文件格式&#xff0c;相信现在有很多用户都在使用。这是因为PDF具有出色的兼容性&#xff0c;适用于包含数据、图片、表格和文字等各种内容&#xff0c;不管是在电脑、手机、平板上&#xff0c;都可以让文件以最规范的方式打开呈现给…

诊断27服务介绍

在UDS诊断协议中,有一些服务,比如2E服务写入DID数据,2F服务控制输入输出,它们都会改变ECU控制器的内存数据,所以在请求这类服务时需要慎之又慎。诊断协议设计了一个安全解锁机制,让ECU在接收到某些诊断服务(2E、2F等)前需要处于解锁状态,这就是27服务实现。 Tester发…

Lyapunov optimization 李雅普诺夫优化

文章目录 正文引言Lyapunov drift for queueing networks 排队网络的Lyapunov漂移Quadratic Lyapunov functions 二次李雅普诺夫函数Bounding the Lyapunov drift 李亚普诺夫漂移的边界A basic Lyapunov drift theorem 一个基本的李雅普诺夫漂移定理 Lyapunov optimization for…

STM32实现PMBus从机程序

最近在野火的STM32F103VET6开发板上实现PMBus从机程序&#xff0c;这个程序参考了以下这篇博客的关于使用中断法实现I2C从机程序&#xff1a;STM32设置为I2C从机模式_iic从机_柒壹漆的博客-CSDN博客 &#xff0c;实测这个程序是可以正常运行的&#xff0c;感谢博主的分享&#…

MDK工程转换Vscode+EIDE方法

MDK工程转换VscodeEIDE方法 1、VscodeEIDE环境搭建方法 请按下方视频完成环境搭建&#xff0c;并编译成功。下载&#xff0c;单步调试如无视频中芯片可暂不执行。 https://www.bilibili.com/video/BV1Zu4y1f72H/?spm_id_from333.337.search-card.all.click&vd_source73…

Prometheus+Grafana监控K8S集群(基于K8S环境部署)

文章目录 一、环境信息二、部署前准备工作三、部署Prometheus监控系统四、部署Node_exporter组件五、部署Kube_state_metrics组件六、部署Grafana可视化平台七、Grafana可视化显示Prometheus收集数据八、Grafana添加监控模板九、拓展 一、环境信息 1、服务器及K8S版本信息&…

3D科研绘图与学术图表绘制:从入门到精通

&#x1f482; 个人网站:【工具大全】【游戏大全】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 寻找学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 3D科研绘图和学术图表绘…

面试官问:大量的 TIME_WAIT 状态 TCP 连接,对业务有什么影响?怎么处理?

几个方面&#xff1a; 问题描述&#xff1a;什么现象&#xff1f;什么影响&#xff1f; 问题分析 解决方案 底层原理 1.问题描述 模拟高并发的场景&#xff0c;会出现批量的 TIME_WAIT 的 TCP 连接&#xff1a; 短时间后&#xff0c;所有的 TIME_WAIT 全都消失&#xff0…

git的基本操作

git的基本操作 一般思路&#xff1a; 新建个人分支加粗样式–克隆远程仓库代码—编辑本地分支代码–合入master分支&#xff08;先切换到master分支&#xff09;–master分支代码push到远程仓库 1、安装好git之后必须设置用户和邮箱信息之后才能提交代码到缓存区、本地库 git …

(避开网上复制操作)最详细的树莓派刷机配置(含IP固定、更改国内源的避坑操作、SSH网络登录、VNC远程桌面登录)

一、准备工作 SD卡格式化 二、 树莓派系统环境搭建&#xff08;官方&#xff09; 官方镜像 1.1、 必备的配件 读卡器&#xff0c; 内存卡&#xff08;强烈推荐 32GB 内存卡&#xff0c; #lite 命令行界面版本至少需要 8G&#xff0c; 图形化带桌面版镜像需要 16GB&#xf…

气球派对服务小程序商城的效果是什么

气球派对包含多种场景&#xff0c;除了线下服务如生日布置、浪漫小礼、婚礼布置、周岁礼等&#xff0c;还有相关产品销售属性&#xff1b;同时这些服务具备较高的同城场景和定制化需求&#xff0c;在实际生活中&#xff0c;这些服务的需求度较高&#xff0c;但同样需要商家不断…

【C++】手撕string(string的模拟实现)

手撕string目录&#xff1a; 一、 Member functions 1.1 constructor 1.2 Copy constructor&#xff08;代码重构&#xff1a;传统写法和现代写法&#xff09; 1.3 operator&#xff08;代码重构&#xff1a;现代写法超级牛逼&#xff09; 1.4 destructor 二、Other mem…

在Pyppeteer中实现反爬虫策略和数据保护

爬虫是我们获取互联网数据的神奇工具&#xff0c;但是面对越来越严格的反爬虫措施&#xff0c;我们需要一些我们获取数据的利器来克服这些障碍。本文将带您一起探索如何使用Pyppeteer库来应对这些挑战。 Pyppeteer是一个基于Python的无头浏览器控制库&#xff0c;它提供了与Chr…

MySQL 连接查询(多表查询 二)

基本介绍 作用&#xff1a;连接查询&#xff08;Join&#xff09;操作&#xff0c;用于联结多个表以获取更全面和准确的数据 基本分类&#xff1a; 内连接&#xff1a;相当于查询A、B交集部分数据&#xff08;去掉迪卡尔积无效组合&#xff09;外连接&#xff1a; 左外连接&…

VmWare16+Ubuntu安装教程

文章目录 前言一、前期软件和系统镜像准备二、VmWare16安装三、Ubuntu安装&#xff08;1&#xff09;下载Ubuntu镜像&#xff08;2&#xff09;打开VmWare16&#xff0c;点击创建新的虚拟机&#xff08;3&#xff09;选择典型&#xff0c;下一步&#xff08;4&#xff09;选择刚…

MySQL 内部组件结构以及SQL执行逻辑

目录 一、MySQL的的内部组件结构二、连接器三、查询缓存四、分析器五、优化器六、执行器 一、MySQL的的内部组件结构 Server层 主要包括连接器、查询缓存、分析器、优化器、执行器等&#xff0c;涵盖 MySQL 的大多数核心服务功能&#xff0c;以及所有的内置函数 &#xff08;如…