化妆品网站建设经济可行性分析,美食网站功能建设,扬州网络品牌营销推广,无锡网站制作推荐[NOI2002] 银河英雄传说
题目背景
公元 580158015801 年#xff0c;地球居民迁至金牛座 α\alphaα 第二行星#xff0c;在那里发表银河联邦创立宣言#xff0c;同年改元为宇宙历元年#xff0c;并开始向银河系深处拓展。
宇宙历 799799799 年#xff0c;银河系的两大军…[NOI2002] 银河英雄传说
题目背景
公元 580158015801 年地球居民迁至金牛座 α\alphaα 第二行星在那里发表银河联邦创立宣言同年改元为宇宙历元年并开始向银河系深处拓展。
宇宙历 799799799 年银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。
题目描述
杨威利擅长排兵布阵巧妙运用各种战术屡次以少胜多难免恣生骄气。在这次决战中他将巴米利恩星域战场划分成 300003000030000 列每列依次编号为 1,2,…,300001, 2,\ldots ,300001,2,…,30000。之后他把自己的战舰也依次编号为 1,2,…,300001, 2, \ldots , 300001,2,…,30000让第 iii 号战舰处于第 iii 列形成“一字长蛇阵”诱敌深入。这是初始阵形。当进犯之敌到达时杨威利会多次发布合并指令将大部分战舰集中在某几列上实施密集攻击。合并指令为 M i j含义为第 iii 号战舰所在的整个战舰队列作为一个整体头在前尾在后接至第 jjj 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而老谋深算的莱因哈特早已在战略上取得了主动。在交战中他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时莱因哈特为了及时了解当前杨威利的战舰分布情况也会发出一些询问指令C i j。该指令意思是询问电脑杨威利的第 iii 号战舰与第 jjj 号战舰当前是否在同一列中如果在同一列中那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员你被要求编写程序分析杨威利的指令以及回答莱因哈特的询问。
输入格式
第一行有一个整数 TTT1≤T≤5×1051 \le T \le 5 \times 10^51≤T≤5×105表示总共有 TTT 条指令。
以下有 TTT 行每行有一条指令。指令有两种格式 M i jiii 和 jjj 是两个整数1≤i,j≤300001 \le i,j \le 300001≤i,j≤30000表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令并且保证第 iii 号战舰与第 jjj 号战舰不在同一列。 C i jiii 和 jjj 是两个整数1≤i,j≤300001 \le i,j \le 300001≤i,j≤30000表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
输出格式
依次对输入的每一条指令进行分析和处理
如果是杨威利发布的舰队调动指令则表示舰队排列发生了变化你的程序要注意到这一点但是不要输出任何信息。如果是莱因哈特发布的询问指令你的程序要输出一行仅包含一个整数表示在同一列上第 iii 号战舰与第 jjj 号战舰之间布置的战舰数目。如果第 iii 号战舰与第 jjj 号战舰当前不在同一列上则输出 −1-1−1。
样例 #1
样例输入 #1
4
M 2 3
C 1 2
M 2 4
C 4 2样例输出 #1
-1
1提示
战舰位置图表格中阿拉伯数字表示战舰编号 带权并查集 我一开始的代码
#include bits/stdc.husing namespace std;const int maxn30000;int pre[maxn5],d[maxn5],lazy[maxn5],num[maxn5],ind[maxn5];
int T;
char op;void init()
{for(int i0;imaxn;i){pre[i]i;d[i]0;lazy[i]0;num[i]1;ind[i]0;}
}int findroot(int x)
{if(pre[x]x) return x;int y pre[x];int rootyfindroot(y);d[x] lazy[y];lazy[x] lazy[y];if(--ind[y]0){lazy[y]0;}pre[x]rooty;ind[rooty];return rooty;
}
void join(int x,int y)
{int rootxfindroot(x);int rootyfindroot(y);pre[rootx]rooty;d[rootx]num[rooty];lazy[rootx]num[rooty];num[rooty]num[rootx];ind[rooty];
}void query(int x,int y)
{int rootxfindroot(x);int rootyfindroot(y);if (rootx!rooty){puts(-1);return;}int maximax(d[x],d[y]);int minimin(d[x],d[y]);printf(%d\n, max(maxi-mini-1,0) );}
int main()
{int x,y;while(~scanf(%d,T)){init();while(T--){scanf( %c%d%d,op,x,y);if(opM){join(x,y);}else if(opC){query(x,y);}}}return 0;
}看了题解发现不用使用lazy数组。 因为d[]维护的是当前结点相对于根结点的距离。 每个结点x的d[x]初始化时是0只有一次机会作为根结点合并到其它根结点rooty此时d[x]会有更新。 同时当x的父亲节点ypre[x]指向新的父结点时会更新d[y]之后调用findroot(x)也会更新d[x]。
#includeiostream
#includecmath
using namespace std;
int f[30001],s[30001],b[30001];
int find(int o)//查找
{if(f[o]o) return o;int kf[o];f[o]find(f[o]);//路径压缩s[o]s[k];//更新当前节点到根的距离return f[o];
}
int main()
{int n;cinn;for(int i1;i30000;i) {f[i]i;s[i]0;b[i]1;}for(int i1;in;i){char ch;int x,y,dx,dy;cinchxy;if(chM){dxfind(x);//查找x的根dyfind(y);//查找y的根f[dx]dy;//把x放在y后面s[dx]b[dy];//更新x的根到新的根的距离b[dx]b[dy];//更新集合大小b[dy]b[dx];//更新集合大小}if(chC){dxfind(x);dyfind(y);if(dx!dy){cout-1endl;continue;}//不在同一个集合中coutabs(s[x]-s[y])-1endl;//中间战舰的数量等于x到根的距离减y到根的距离减一。}}return 0;
}总结
使用并查集当一个结点x指向的结点变化时pre[x] 无非一下两种情况: 1) x作为根结点 合并到 另一个树的根结点。
x或其子树内结点调用查找操作将x指向了根结点rootx。
