洛谷 P1196 [NOI2002]银河英雄传说【带权并查集】
发布日期:2021-07-01 02:50:44
浏览次数:3
分类:技术文章
本文共 2375 字,大约阅读时间需要 7 分钟。
题目背景
公元5801
年,地球居民迁至金牛座 α \alpha α 第二行星,在那里发表银河联邦创立宣言,同年改元为宇宙历元年,并开始向银河系深处拓展。 宇宙历 799
年,银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征,气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 题目描述
杨威利擅长排兵布阵,巧妙运用各种战术屡次以少胜多,难免恣生骄气。在这次决战中,他将巴米利恩星域战场划分成 30000 30000 30000 列,每列依次编号为 1 , 2 , … , 30000 1, 2,\ldots ,30000 1,2,…,30000 。之后,他把自己的战舰也依次编号为 1 , 2 , … , 30000 1, 2, \ldots , 30000 1,2,…,30000 ,让第 i i i 号战舰处于第 i i i 列,形成“一字长蛇阵”,诱敌深入。这是初始阵形。当进犯之敌到达时,杨威利会多次发布合并指令,将大部分战舰集中在某几列上,实施密集攻击。合并指令为 M i j
,含义为第 i i i 号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第 j j j 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而,老谋深算的莱因哈特早已在战略上取得了主动。在交战中,他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。在杨威利发布指令调动舰队的同时,莱因哈特为了及时了解当前杨威利的战舰分布情况,也会发出一些询问指令:C i j
。该指令意思是,询问电脑,杨威利的第 i i i 号战舰与第 j j j 号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员,你被要求编写程序分析杨威利的指令,以及回答莱因哈特的询问。
输入格式
第一行有一个整数 T T T( 1 ≤ T ≤ 5 × 1 0 5 1 \le T \le 5 \times 10^5 1≤T≤5×105),表示总共有 T T T 条指令。以下有 T T T 行,每行有一条指令。指令有两种格式:M i j
: i i i 和 j j j 是两个整数( 1 ≤ i , j ≤ 30000 1 \le i,j \le 30000 1≤i,j≤30000),表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令,并且保证第 i i i 号战舰与第 j j j 号战舰不在同一列。C i j
: i i i 和 j j j 是两个整数( 1 ≤ i , j ≤ 30000 1 \le i,j \le 30000 1≤i,j≤30000),表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
输出格式
依次对输入的每一条指令进行分析和处理:- 如果是杨威利发布的舰队调动指令,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息。
- 如果是莱因哈特发布的询问指令,你的程序要输出一行,仅包含一个整数,表示在同一列上,第 i i i 号战舰与第 j j j 号战舰之间布置的战舰数目。如果第 i i i 号战舰与第 j j j 号战舰当前不在同一列上,则输出
-1
。
输入输出样例
输入 #14M 2 3C 1 2M 2 4C 4 2
输出 #1
-11
说明/提示
战舰位置图:表格中阿拉伯数字表示战舰编号题意:和 POJ 1988 Cube Stacking
类似。
思路:简单的带权并查集。代码如下:
#includeusing namespace std;const int maxn = 30010;int father[maxn], height[maxn], size[maxn]; //height[i]表示某结点的高度是多少 void init() { for (int i = 1; i < maxn; ++i) { father[i] = i; height[i] = 0; size[i] = 1; }}int find(int x) { if (father[x] == x) return x; int t = father[x]; father[x] = find(t); height[x] += height[t]; return father[x];}void merge(int a, int b) { //a所在的战舰队列整体移动到b所在的战舰队列之后 int x = find(a), y = find(b); if (x == y) return; father[x] = y; height[x] += size[y]; size[y] += size[x];}bool query(int a, int b) { return find(a) == find(b); }int main() { int t, a, b; char c[2]; scanf("%d", &t); init(); while (t--) { scanf("%s%d%d", c, &a, &b); if (c[0] == 'M') merge(a, b); else if (c[0] == 'C') { if (!query(a, b)) printf("-1\n"); else printf("%d\n", abs(height[a] - height[b]) - 1); } } return 0;}
转载地址:https://memcpy0.blog.csdn.net/article/details/108314087 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月13日 02时07分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
没钱没公司,怎么做一款付费产品
2019-05-01
代码整洁之道-编写 Pythonic 代码
2019-05-01
树莓派程序开机自启动
2019-05-01
连锁门店无线通信方案
2019-05-01
配置Lotus Domino集群视频详解
2019-05-01
Linux软件万花筒
2019-05-01
全球开源软件发展趋势分析
2019-05-01
Linux常用的安全工具
2019-05-01
python 多进程之进程池的操作
2019-05-01
flask整理之 flask程序中的debug模式
2019-05-01
比特币,父母这一辈能接受吗?
2019-05-01
为什么要反对比特币,这不代表是空气币
2019-05-01
SnapEx的新感觉,对新手很友好
2019-05-01
首个聚合器怎么产生的,并运用领域在什么
2019-05-01
区块链技术应用,最先医疗行业
2019-05-01
新币上市旧币会降价吗
2019-05-01
当博士进入币圈会怎么样
2019-05-01