葡京娱乐开元棋牌_开元棋牌靠谱吗_f1娱乐开元棋牌先锋网 葡京娱乐开元棋牌_开元棋牌靠谱吗_f1娱乐开元棋牌片段及技术文章聚合

银河英雄传说(边带权并查集)

题目:

有一个划分为N列的星际战场,各列依次编号为1,2,…,N。

有N艘战舰,也依次编号为1,2,…,N,其中第i号战舰处于第i列。

有T条指令,每条指令格式为以下两种之一:

1、M i j,表示让第i号战舰所在列的全部战舰保持原有顺序,接在第j号战舰所在列的尾部。

2、C i j,表示询问第i号战舰与第j号战舰当前是否处于同一列中,如果在同一列中,它们之间间隔了多少艘战舰。

现在需要你编写一个程序,处理一系列的指令。

输入格式

第一行包含整数T,表示共有T条指令。

接下来T行,每行一个指令,指令有两种形式:M i j或C i j。

其中M和C为大写字母表示指令类型,i和j为整数,表示指令涉及的战舰编号。

输出格式

你的程序应当依次对输入的每一条指令进行分析和处理:

如果是M i j形式,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;

如果是C i j形式,你的程序要输出一行,仅包含一个整数,表示在同一列上,第i号战舰与第j号战舰之间布置的战舰数目,如果第i号战舰与第j号战舰当前不在同一列上,则输出-1。

数据范围

N30000,T500000N≤30000,T≤500000

输入样例:

4
M 2 3
C 1 2
M 2 4
C 4 2

输出样例:

-1
1

解题报告:边带权并查集的使用,咱们把每一列的战舰看成一个集合,用并查集维护,最初的时候,n个战舰就是n个独立的集合。
在没有进行路径压缩的时候,far[x]就表示排在第x号战舰前边的那个战舰的编号,一个集合的代表就是位于最前边的战舰,另外,让树上的每条边带权值1,这样树上两点之间的距离减一就是两点之间间隔的战舰数目。
在考虑路径压缩的情况下,咱们需要单独开设一个数组d,d[x]记录战舰x与far[x]之间的边的权值。在路径压缩把x连接到根节点的同时,把d[x]更新为从x到根节点的路径上的所有边权之和。
下边的find函数增加了部分语句,实现了对d数组的维护:
 1 int find(int x)
 2 {
 3     if(far[x]==x)
 4     {
 5         return x;
 6     }
 7     int root=find(far[x]);
 8     data[x]+=data[far[x]];
 9     return far[x]=root;
10 }

当接受到一个C x y 指令时,分别执行find(x) ,find(y) 完成查询和路径压缩,若二者返回值相同,则说明在同一列,因为x,y这时都指向了根节点,所以d[x]存放了位于x之前的战舰数目,d[y]存放了位于y之前的战舰数目,二者之差的绝对值再减一,就是x,y之间间隔战舰的数目。

当接受到一个M x y指令时,把x的根节点作为y的根节点的子结点,连接新边的权值应该设为合并之前集合y的大小,因此我们还需要一个size数组,在每个树根上记录集合的大小。

merge函数:

1 void merge(int x,int y)
2 {
3     x=find(x);
4     y=find(y);
5     far[x]=y;
6     data[x]=size[y];
7     size[y]+=size[x];
8 }

 

ac葡京娱乐开元棋牌_开元棋牌靠谱吗_f1娱乐开元棋牌:

//from:Onion
//acwing 238 银河英雄传说 边带权并查集 
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;

const int maxn=3e4+1000;
int size[maxn],far[maxn],data[maxn];
void init()
{
	for(int i=0;i

  

原文地址:银河英雄传说(边带权并查集)