devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

10.7 a.m.小结_h 城是一个旅游胜地,每年都有成千上万的人前来观光。为方便游客,巴士公司在各个旅

作者：知新_RL | 2024-05-17 09:11:35

赞

踩

h 城是一个旅游胜地,每年都有成千上万的人前来观光。为方便游客,巴士公司在各个旅

T1：问题 F: 最优乘车

题目描述

H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达 S 公园。
现在用整数 1,2,…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。
写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到 S 公园的过程中换车的次数最少。

输入

第一行有两个数字 M 和 N(1<=M<=100 1<N<=500），表示开通了 M 条单程巴士线路，总共有 N 个车站。从第二行到第 M 刊行依次给出了第 1 条到第 M 条巴士线路的信息。其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。

输出

只有一行。如果无法乘巴士从饭店到达 S 公园，则输出"N0"，否则输出你的程序所找到的最少换车次数，换车次数为 0 表示不需换车即可到达。

样例输入

3 7
6 7
4 7 3 6
2 1 3 5

样例输出

2

题解

这一道题可以考虑建图。假设站k可以被a，b，c三辆巴士经过，那么可以想象，无论从哪一辆车下，再次通向a,b,c巴士路线上任意一站的距离都是1（这里定义的距离为转车次数），尽管会有重复，但是现在完全可以不管，就从建边的角度而言这是毫无问题的。这意味着什么，同一个巴士所经过的站台间是可以相互建边的，意义同上。故直接求最短路即可，如果能从1走到n，dis[1][n]必然有值。数据量很小，直接用FLOYD也能过。用求最短路的方式就可以把很多无用的，看似同站不需要转站的情况全部规避掉，只用走巴士与巴士之间的相互换站才能得到“最小”。注意最后的答案还要处理一下（虽然我觉得没必要，但是题目要求）。

参考代码

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<string> 
  4. using namespace std;
  5. int n,m,a[2000],tot,dis[1001][1001];
  6. char s[2000];
  7. int main()
  8. {
  9. 	memset(dis,127/3,sizeof(dis));
  10. 	scanf("%d%d\n",&m,&n);
  11. 	for(int i=1;i<=m;i++)
  12. 	{
  13. 		gets(s);
  14. 		tot=0;
  15. 		memset(a,0,sizeof(a));
  16. 		for(int j=0;j<strlen(s);j++)
  17. 		{
  18. 			if(isdigit(s[j]))
  19. 			{
  20. 				if(j==0) tot++;
  21. 				a[tot]=a[tot]*10+s[j]-'0';
  22. 			}
  23. 			else if(isdigit(s[j+1])&&!isdigit(s[j]))
  24. 			{
  25. 				++tot;
  26. 			}
  27. 		}
  28. 		for(int i=1;i<=tot;i++)
  29. 		{
  30. 			dis[a[i]][a[i]]=0;
  31. 			for(int j=i+1;j<=tot;j++)
  32. 			{
  33. 				dis[a[i]][a[j]]=1;
  34. 			}
  35. 		}
  36. 	}
  37. 	for(int k=1;k<=n;k++)
  38. 	  for(int i=1;i<=n;i++)
  39. 		for(int j=1;j<=n;j++)
  40. 		  if(dis[i][j]>dis[i][k]+dis[k][j])
  41. 			dis[i][j]=dis[i][k]+dis[k][j];
  42. 	if(dis[1][n]==dis[0][0]) printf("NO\n");
  43. 	else printf("%d",dis[1][n]-1);
  44. 	return 0;
  45. }

T2：问题 A: Sightseeing Cows

题目描述

Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time.

Fortunately, they have a detailed city map showing the L (2 <= L <= 1000) major landmarks (conveniently numbered 1.. L) and the P (2 <= P <= 5000) unidirectional cow paths that join them. Farmer John will drive the cows to a starting landmark of their choice, from which they will walk along the cow paths to a series of other landmarks, ending back at their starting landmark where Farmer John will pick them up and take them back to the farm. Because space in the city is at a premium, the cow paths are very narrow and so travel along each cow path is only allowed in one fixed direction.

While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values F_i (1 <= F_i <= 1000) for each landmark i.

The cows also know about the cowpaths. Cowpath i connects landmark L1_i to L2_i (in the direction L1_i -> L2_i) and requires time T_i (1 <= T_i <= 1000) to traverse.

In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off.
 

Help the cows find the maximum fun value per unit time that they can achieve.

给定一张 L 个点、PP条边的有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

输入

* Line 1: Two space-separated integers: L and P

* Lines 2..L+1: Line i+1 contains a single one integer: F_i
 

* Lines L+2..L+P+1: Line L+i+1 describes cow path i with three space-separated integers: L1_i, L2_i, and T_i

第一行包含两个整数 L 和 P。

接下来 L 行每行一个整数，表示 f[i]。

再接下来 P 行，每行三个整数 a，b，t[i]，表示点 a和 b之间存在一条边，边的权值为 t[i]。

输出

* Line 1: A single number given to two decimal places (do not perform explicit rounding), the maximum possible average fun per unit time, or 0 if the cows cannot plan any trip at all in accordance with the above rules.

输出一个数表示结果，保留两位小数。

样例输入

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

样例输出

6.00

提示


OUTPUT DETAILS:


The trip 1 -> 2 -> 3 -> 5 -> 1 has a total fun value of 60 and a length of 10 units for an average fun per unit time of 6. The trip 2 -> 3 -> 5 -> 2 only has an average fun per unit time of 30/6 = 5, and any trip involving landmark 4 has an average fun per unit time of less than 4.


2≤L≤1000  
 2≤P≤50002≤P≤5000
1≤f[i],t[i]≤1000

题解

这道题要用01分数规划（考试时根本没想到）。由于是权值之和除以权值之和，符合分数规划的基本形式，化简之后就可以变成斜率式……先不说那些，完全可以二分一个答案吧。然后考虑这个答案应该满足什么性质？首先，要足够大，同时，这个环要能找到。根据分数规划的原理，经过一条边到达一个点，权值dis可以视作：边权*ans-点权（ans是二分枚举的答案），或者是相反数。因此就有两种写法，如果是第一种，那就是判断有没有负环，有就说明能够取到这个答案（全部加起来就OK）。如果是相反数，就是判正环。至于为什么用那种方式表示dis，加起来就是题目中所求的。如何判断负环（正环），SPFA不就行了。这里只用找存不存在环，而不是找准确的dis，因此起点初值可以不为0，同时注意全部都要赋值成极大值（极小值）。

参考代码（判负环）

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #define EXP 0.00000001
  5. using namespace std;
  6. struct tree
  7. {
  8. 	int nxt,to,dis;
  9. }tr[10001];
  10. int head[10001],cnt=0,num[10001];
  11. int l,p,f[1001],vis[10001];
  12. double dis[10001];
  13. void build_tree(int u,int v,int d)
  14. {
  15. 	tr[++cnt].nxt=head[u];
  16. 	tr[cnt].dis=d;
  17. 	tr[cnt].to=v;
  18. 	head[u]=cnt;
  19. }
  20. queue<int>q;
  21. bool check(double x)
  22. {
  23. 	memset(num,0,sizeof(num));
  24. 	memset(vis,0,sizeof(vis));
  25. 	memset(dis,0x3f,sizeof(dis));
  26. 	for(int i=2;i<=l;i++) q.push(i),vis[i]=1;
  27. 	while(!q.empty())
  28. 	{
  29. 		int k=q.front();q.pop();
  30. 		vis[k]=0;
  31. 		for(int i=head[k];i;i=tr[i].nxt)
  32. 		{
  33. 			int to=tr[i].to;
  34. 			if(dis[to]>dis[k]+x*tr[i].dis-f[to])
  35. 			{
  36. 				dis[to]=dis[k]+x*tr[i].dis-f[to];
  37. 				num[to]=num[k]+1;
  38. 				if(num[to]>=l) return true;
  39. 				if(!vis[to])
  40. 				{
  41. 					vis[to]=1;
  42. 					q.push(to);
  43. 				 } 
  44. 			}
  45. 		}
  46. 	}
  47. 	return false;
  48. }
  49. int main()
  50. {
  51. 	scanf("%d%d",&l,&p);
  52. 	for(int i=1;i<=l;i++) scanf("%d",&f[i]);
  53. 	for(int i=1;i<=p;i++)
  54. 	{
  55. 		int a,b,c;
  56. 		scanf("%d%d%d",&a,&b,&c);
  57. 		build_tree(a,b,c);
  58. 	} 
  59. 	double l1=0,r1=1e9;
  60. 	while(r1-l1>EXP)
  61. 	{
  62. 		double mid=(l1+r1)/2.0;
  63. 		if(check(mid)) l1=mid;
  64. 		else r1=mid;
  65. 	}
  66. 	printf("%.2lf",l1);
  67. 	return 0;
  68. }

参考代码（判正环）

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #define EXP 0.00000001
  5. using namespace std;
  6. struct tree
  7. {
  8. 	int nxt,to,dis;
  9. }tr[10001];
  10. int head[10001],cnt=0,num[10001];
  11. int l,p,f[1001],vis[10001];
  12. double dis[10001];
  13. void build_tree(int u,int v,int d)
  14. {
  15. 	tr[++cnt].nxt=head[u];
  16. 	tr[cnt].dis=d;
  17. 	tr[cnt].to=v;
  18. 	head[u]=cnt;
  19. }
  20. queue<int>q;
  21. bool check(double x)
  22. {
  23. 	memset(num,0,sizeof(num));
  24. 	memset(vis,0,sizeof(vis));
  25. 	memset(dis,0xc0,sizeof(dis));
  26. 	for(int i=2;i<=l;i++) q.push(i),vis[i]=1;
  27. 	while(!q.empty())
  28. 	{
  29. 		int k=q.front();q.pop();
  30. 		vis[k]=0;
  31. 		for(int i=head[k];i;i=tr[i].nxt)
  32. 		{
  33. 			int to=tr[i].to;
  34. 			if(dis[to]<dis[k]-x*tr[i].dis+f[to])
  35. 			{
  36. 				dis[to]=dis[k]-x*tr[i].dis+f[to];
  37. 				num[to]=num[k]+1;
  38. 				if(num[to]>=l) return true;
  39. 				if(!vis[to])
  40. 				{
  41. 					vis[to]=1;
  42. 					q.push(to);
  43. 				 } 
  44. 			}
  45. 		}
  46. 	}
  47. 	return false;
  48. }
  49. int main()
  50. {
  51. 	scanf("%d%d",&l,&p);
  52. 	for(int i=1;i<=l;i++) scanf("%d",&f[i]);
  53. 	for(int i=1;i<=p;i++)
  54. 	{
  55. 		int a,b,c;
  56. 		scanf("%d%d%d",&a,&b,&c);
  57. 		build_tree(a,b,c);
  58. 	} 
  59. 	double l1=0,r1=1e9;
  60. 	while(r1-l1>EXP)
  61. 	{
  62. 		double mid=(l1+r1)/2.0;
  63. 		if(check(mid)) l1=mid;
  64. 		else r1=mid;
  65. 	}
  66. 	printf("%.2lf",l1);
  67. 	return 0;
  68. }

T3：问题 D: 导弹防御塔

题目描述

Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。
所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。
现在，给出N座导弹防御塔的坐标，M个入侵者的坐标，T1、T2和V，你需要求出至少要多少分钟才能击退所有的入侵者。

输入

第一行五个正整数N,M,T1,T2,V。
接下来M行每行两个整数，代表入侵者的坐标。
接下来N行每行两个整数，代表防御塔的坐标。

输出

输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。

样例输入

3 3 30 20 1
0 0
0 50
50 0
50 50
0 1000
1000 0

样例输出

91.500000

提示

对于40%的数据，N,M<=20.

对于100%的数据， 1≤N≤50, 1≤M≤50，坐标绝对值不超过10000，T1,T2,V不超过2000.

题解

显然，考试时我想到了网络流（太像了），但是没做出来。

至于为什么没做出来，是因为根据距离的不同，导弹所需时间也不同，就很难二分时间。

但是考完试后想一想，这不就是标准的二分图吗？只不过导弹要分成：第一次发射的导弹，第二次发射的导弹……直到时间到了。然后对于每一个位置的每一个导弹，看一下能打到哪些入侵者，建边即可。因为看到好多题解都是匈牙利算法，因此也尝试写了一个。（网上的建边好多都是神仙，我完全写（kan）不（bu）出（dong））至于参数是看的一个大佬的，因为我怎么调都是错（人弱自带bug）。还要注意换算单位，对比匈牙利和网络流，应付二分图感觉还是匈牙利要方便一点（网络流自然也不差哈哈）

参考代码

  1. #include<cstring>
  2. #include<cstdio>
  3. #include<cmath>
  4. #define EXP 0.00000001
  5. using namespace std;
  6. struct tree
  7. {
  8. 	int nxt,to;
  9. }tr[200000];
  10. int dt[100000],bz[100000];
  11. int n,m,cnt=0,head[200000];
  12. double X[10000],Y[10000],dis[1000][1000],l,r,t1,t2,v;
  13. void build_tree(int u,int v)
  14. {
  15. 	tr[++cnt].nxt=head[u];
  16. 	tr[cnt].to=v;
  17. 	head[u]=cnt;
  18. }
  19. bool dfs(int k)
  20. {
  21. 	for(int i=head[k];i;i=tr[i].nxt)
  22. 	{
  23. 		int to=tr[i].to;
  24. 		if(bz[to]==0)
  25. 		{
  26. 			bz[to]=1;
  27. 			if(dt[to]==0||dfs(dt[to]))
  28. 			{
  29. 				dt[to]=k;
  30. 				return true;
  31. 			}
  32. 		}
  33. 	}
  34. 	return false;
  35. }
  36. bool judge(double x)
  37. {
  38. 	memset(dt,0,sizeof(dt));
  39. 	memset(head,0,sizeof(head));
  40. 	double T=x;
  41. 	int k=0;cnt=0;
  42. 	while(T-t1>=EXP)
  43. 	{
  44. 		T-=t1;
  45. 		k++;
  46. 		for(int i=1;i<=m;i++)
  47. 		{
  48. 			for(int j=1;j<=n;j++)
  49. 			{
  50. 				if(dis[j][i]-T<=EXP)
  51. 				{
  52. 					build_tree(i,n*(k-1)+j);
  53. 				}
  54. 			}
  55. 		}
  56. 		T-=t2;
  57. 	}
  58. 	for(int i=1;i<=m;i++)
  59. 	{
  60. 		memset(bz,0,sizeof(bz));
  61. 		if(!dfs(i)) return false;
  62. 	}
  63. 	return true;
  64. }
  65. int main()
  66. {
  67. 	scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&v);
  68. 	t1/=60.0;
  69. 	for(int i=1;i<=m;i++)
  70. 	{
  71. 		scanf("%lf%lf",&X[i],&Y[i]);
  72. 	}
  73. 	for(int i=1;i<=n;i++)
  74. 	{
  75. 		double x1,y1;
  76. 		scanf("%lf%lf",&x1,&y1);
  77. 		for(int j=1;j<=m;j++)
  78. 		{
  79. 			dis[i][j]=sqrt(1.0*(x1-X[j])*(x1-X[j])+(y1-Y[j])*(y1-Y[j]))/v;
  80. 		}
  81. 	}
  82. 	l=0;r=3e4;
  83. 	while(r-l>EXP)
  84. 	{
  85. 		double mid=(l+r)/2.0;
  86. 		if(judge(mid)) r=mid;
  87. 		else l=mid;
  88. 	}
  89. 	printf("%.6f",l);
  90. 	return 0;
  91. }

T4：问题 B: 升降梯上

题目描述

开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。
Nescafé 之塔一共有N 层，升降梯在每层都有一个停靠点。手柄有M 个控制槽，第i个控制槽旁边标着一个数Ci，满足C1<C2<C3<...<CM。如果Ci>0，表示手柄扳动到该槽时，电梯将上升Ci 层；如果Ci<0，表示手柄扳动到该槽时，电梯将下降-Ci 层；并且一定存在一个Ci=0，手柄最初就位于此槽中。注意升降梯只能在1~N 层间移动，因此扳动到使升降梯移动到1 层以下、N 层以上的控制槽是不允许的。
电梯每移动一层，需要花费2 秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费1 秒钟时间。探险队员现在在1 层，并且想尽快到达N 层，他们想知道从1 层到N 层至少需要多长时间？

输入

第一行两个正整数N、M。
第二行M 个整数C1、C2...CM。

输出

输出一个整数表示答案，即至少需要多长时间。若不可能到达输出-1。

样例输入

6 3
-1 0 2

样例输出

19

提示

【数据范围与约定】

对于30% 的数据，满足1≤N≤10，2<=M<=5。

对于 100% 的数据，满足1≤N≤1000，2<=M<=20，-N<C1<C2<……<CM<N。

【样例解释】

手柄从第二个槽扳到第三个槽（0 扳到2），用时1 秒，电梯上升到3 层，用时4 秒。

手柄在第三个槽不动，电梯再上升到5 层，用时4 秒。

手柄扳动到第一个槽（2 扳到-1），用时2 秒，电梯下降到4 层，用时2 秒。

手柄扳动到第三个槽（-1 扳倒2），用时2 秒，电梯上升到6 层，用时4 秒。

总用时为(1+4)+4+(2+2)+(2+4)=19 秒。

题解

搜索？图论。对于一个状态，只能是一个楼层是由另一个楼层（可以不计）通过把按钮从i拨到j到达的。因此只需要记录当前楼层和当前手柄位置，就可以作为点。至于边就是单向边，尝试拨动每一个手柄的位置（不动的位置除外），然后看看能不能到达规定楼层，能的话就建边（实际上写的时候可以预处理，但是数据量不大，因此就每次枚举手柄的位置（比较慢，看卡不卡空间））。之后就是跑一边SPFA，然后枚举第n层每一个手柄的状态，累计答案。如果无法到达说明该dis为无穷大，未曾更改过，判断一下就行了。还有一个细节就是算边权时注意看清楚楼层移动和手柄移动 的速度不一样。

参考代码

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. int n,m,dp[1002][22],vis[1002][22],c[22],now,maxn;
  6. struct node
  7. {
  8. 	int num,op;
  9. };
  10. bool pd(int x) { return (x>0)&&(x<=n); }
  11. int abs1(int p) { return p>0?p:-p; }
  12. queue<node>q;
  13. int main()
  14. {
  15. 	memset(dp,127/3,sizeof(dp));
  16. 	scanf("%d%d",&n,&m);
  17. 	for(int i=1;i<=m;i++) 
  18. 	{
  19. 		scanf("%d",&c[i]);
  20. 		if(c[i]==0) now=i;
  21. 	}
  22. 	node pt;
  23. 	pt.num=1;pt.op=now;
  24. 	q.push(pt);dp[1][now]=0;
  25. 	while(!q.empty())
  26. 	{
  27. 		node k=q.front();q.pop();
  28. 		vis[k.num][k.op]=0;
  29. 		for(int i=1;i<=m;i++)
  30. 		{
  31. 			if(!pd(k.num+c[i])) continue;
  32. 			if(dp[k.num+c[i]][i]>dp[k.num][k.op]+2*abs1(c[i])+abs1(k.op-i))
  33. 			{
  34. 				dp[k.num+c[i]][i]=dp[k.num][k.op]+2*abs1(c[i])+abs1(k.op-i);
  35. 				if(!vis[k.num+c[i]][i])
  36. 				{
  37. 					vis[k.num+c[i]][i]=1;
  38. 					node tt;
  39. 					tt.num=k.num+c[i];
  40. 					tt.op=i;
  41. 					q.push(tt);
  42. 				}
  43. 			}
  44. 		}
  45. 	}
  46. 	maxn=707406378;
  47. 	for(int i=1;i<=m;i++)
  48. 	if(dp[n][i]<maxn)
  49. 	maxn=dp[n][i];
  50. 	if(maxn>=707406378) printf("-1");
  51. 	else printf("%d",maxn);
  52. 	return 0;
  53. }

T5：问题 C: 银河英雄传说

题目描述

公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 
宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 
最终的决战已经展开，银河的历史又翻过了一页…… 

输入

第一行有一个整数T（1 <= T <= 500,000），表示总共有T条指令。 
以下有T行，每行有一条指令。指令有两种格式： 
1. M i j ：i和j是两个整数（1 <= i , j <= 30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 
2. C i j ：i和j是两个整数（1 <= i , j <= 30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

输出

你的程序应当依次对输入的每一条指令进行分析和处理： 
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息； 
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

样例输入

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

样例输出

-1
1

题解

读完题就知道第一问很简单，并查集嘛。然后与普通的不同之处在于要维护一个size和pos（我的代码中就叫size1和size2），表示以此为首队列后面有多少舰队和此前有多少舰队。size的维护就不说了，没啥技术含量。主要是pos的维护。对于一个M，可以很清楚的知道，第i列的所有pos都要更改，但是一个一个改又太慢了，有什么方式呢？只改头就可以了。只需要把头i的pos从0改成size[j]即可。之后由于i后面的点跳father时，会经过i买就可以加上size[j]也就是pos[i]了。注意同时还要路径压缩，避免重复相加。

参考代码

  1. #include<cstdio>
  2. using namespace std;
  3. int t,size1[30010],size2[30010],fa[30010];char s[50];
  4. int abs1(int p) { return p>0?p:-p; }
  5. int find(int v,int t)
  6. {
  7. 	if(fa[v]==v) return v;
  8. 	int root=find(fa[v],t);
  9. 	size2[v]+=size2[fa[v]]; 
  10. 	return fa[v]=root;
  11. }
  12. int main()
  13. {
  14. 	scanf("%d",&t);
  15. 	for(int i=1;i<=30000;i++)
  16. 	{
  17. 		size1[i]=1;fa[i]=i;
  18. 	}
  19. 	while(t--)
  20. 	{
  21. 		scanf("%s",s);
  22. 		int i,j;
  23. 		scanf("%d%d",&i,&j);
  24. 		if(s[0]=='M')
  25. 		{
  26. 			i=find(i,i);
  27. 			j=find(j,j);
  28. 			size2[i]=size1[j];
  29. 			size1[j]+=size1[i];
  30. 			fa[i]=j;
  31. 		} 
  32. 		else if(s[0]=='C')
  33. 		{
  34. 			if(find(i,i)!=find(j,j)) printf("-1\n");
  35. 			else printf("%d\n",abs1(size2[i]-size2[j])-1);
  36. 		}
  37. 	}
  38. 	return 0;
  39. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/582893
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号