【春训团队赛第四场】MST上倍增 | LCA | DAG上最长路 | 思维 | 素数筛 | 找规律 | 计几 | 背包 | 并查集

  • Post author:
  • Post category:其他








春训团队赛第四场



ID A B C D E F G H I J K L M
AC O O O O O O O O O
补题 ? ? O O



传送门





题目链接(CF Gym102021)






题解链接(pdf)




代码 & 简易题解



[A]:LCA

给定一个格状迷宫,保证任意点均可达,且任意两格点间有且仅有一条简单路径。

给定一组移动序列,求按照这个序列走的累计路程。

按照题意对图预处理,得到一棵树,对于每对询问求



LCA

\text{LCA}







LCA






的同时求距离,累加即为答案。

一开始



RE

\text{RE}







RE






了两发,要注意

离散化操作带来的越界

问题…





LCA

\text{LCA}







LCA






,可以


倍增


or


DFS序RMQ


or


Tarjan


,前两者带



l

o

g

log






l


o


g





,后者是离线的不带



l

o

g

log






l


o


g





,本题倍增即可



AC

\text{AC}







AC









AC

\text{AC}







AC






代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#define N 1000010

using namespace std;

char a, str[2005];
char s[2005][2005];


int n, m,lsum=1,L=0,i,j,k,x,y,cnt;
long long Ans;
int head[2*N],v[2*N],d[2*N];
int f[N][22],p[22];
int q[10010],Q[10010];

struct Egde{
	int t,next;
}e[N*8];

vector <int> son[N];
map <int,int> M;

char sw(char a) {
	if (a == ' ') return 'k';
	if (a == '_') return 'h';
	if (a == '|') return 's';
	if (a == '	') return 'z';
	if (a == '\n') return '\n';
}

int ID(int x, int y) {
	if (M[x*10000+y])	return M[x*10000+y];
	else {
		++cnt;
		M[x*10000+y]=cnt;
		return cnt;
	}
}

inline void Swap(int &x,int &y){x^=y^=x^=y;}

inline void add(int s,int t){
	e[lsum].t=t;	e[lsum].next=head[s];	head[s]=lsum++;
	e[lsum].t=s;	e[lsum].next=head[t];	head[t]=lsum++;
}

inline void Maketree(int x){
	int i=0;
	v[x]=1;
	for (i=head[x];i;i=e[i].next){
		if (v[e[i].t])	continue;
		f[e[i].t][0]=x;	d[e[i].t]=d[x]+1;
		Maketree(e[i].t);	son[x].push_back(e[i].t);
	}
}

inline void Dfs(int x){
	int i=0,s=0;
	for (i=1;i<=20;i++)	f[x][i]=f[f[x][i-1]][i-1];
	if (!son[x].size())	return;
	for (s=son[x].size(),i=0;i<s;i++)	Dfs(son[x][i]);
}

inline int LCA(int x,int y){
	int l=0,i=0;	L=0;
	if (d[x]<d[y])	Swap(x,y);
	l=d[x]-d[y];
	for (i=0;i<=20;i++)
		if (l&p[i])	x=f[x][i];
	L=l;
	if (x==y)	return x;
	for (i=20;i>=0;i--)
		if (f[x][i]!=f[y][i]){
			L+=2*p[i],x=f[x][i],y=f[y][i];
		}
	L+=2;
}

int main(){
	scanf("%d%d\n", &n, &m);
	for (i = 1; i <= 2*m+1; i++) scanf("%c", &a);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= 2*m+2; j++) scanf("%c", &s[i][j]);
	}
	for (i = 1; i <= n; i++) {
		int l = 0;
		for (j = 3; j <= 2*m-1; j+=2) {
			l++;
			if (s[i][j] == ' ') add(ID(i, l), ID(i, l+1));
		}
	}
	for (i = 1; i < n; i++) {
		int l = 0;
		for (j = 2; j <= 2*m; j+=2) {
			l++;
			if (s[i][j] == ' ') add(ID(i, l), ID(i+1, l));
		}
	}
	for (i=1,p[0]=1;i<=20;i++)	p[i]=p[i-1]*2;
	d[ID(1,1)]=1;	Maketree(ID(1,1));	Dfs(ID(1,1));
	scanf("%d",&k);
	for (i=1;i<=k;i++)		scanf("%d%d",&q[i],&Q[i]);
	for (i=1;i<k;i++){
		x=ID(q[i],Q[i]);	y=ID(q[i+1],Q[i+1]);
		LCA(x,y);	Ans+=L;
	}
	cout<<Ans<<endl;
	return 0;
}



[B]:简单计几

给定一个蓝圈和红圈,红圈严格在蓝圈内部,再给定蓝圈内两个点,两点连线直线段必穿过红圈。求在不进入红圈的情况下连接两点的曲线段长度最小值。

先求两点与红圈切线段长度,以此求得两切点间的弧上距离,答案为该距离加两切点到两点的距离。

注:



int

\text{int}







int






会带来奇怪的精度问题。




AC

\text{AC}







AC






代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#include<cmath>
using namespace std;

inline double Sqr(double x){
	return (double)1.0*x*x;
}

inline double Dis(double a,double b,double c,double d){
	return (sqrt(Sqr(a-c)+Sqr(b-d)));
}

double X1,X2,X3,X4,Y1,Y2,Y3,Y4,r1,r2;
double d1,d2,d3,dis1,dis2,p,Ans;
double J1,J2,J3;

int main(){
	scanf("%lf%lf",&X1,&Y1);
	scanf("%lf%lf",&X2,&Y2);
	scanf("%lf%lf%lf",&X3,&Y3,&r1);
	scanf("%lf%lf%lf",&X4,&Y4,&r2);
	d1=Dis(X1,Y1,X4,Y4);
	d2=Dis(X2,Y2,X4,Y4);
	d3=Dis(X1,Y1,X2,Y2);
	double hh=sqrt(Sqr(d1)-Sqr(d3/2));
	J1=acos((double)1.0*r2/d1);
	J2=acos((double)1.0*r2/d2);
	p=1.0*Sqr(d1)+Sqr(d2)-Sqr(d3);
	p/=2.0*d1*d2;
	J3=acos(p);
	dis1=sqrt(Sqr(d1)-Sqr(r2));
	dis2=sqrt(Sqr(d2)-Sqr(r2));
	Ans=dis1+dis2+(double)1.0*r2*(J3-J1-J2);
	printf("%.10lf\n",Ans);
	return 0;
}



[C]:DAG最长路,dp





DAG

\text{DAG}







DAG






上的最长路。




DAG

\text{DAG}







DAG






上的



dp

\text{dp}







dp






,状态转移方程:



d

p

[

u

]

=

max

{

w

u

v

+

d

p

[

v

]

}

dp[u] = \max\{w_{u\rightarrow v}+dp[v]\}






d


p


[


u


]




=








max


{




w











u





v





















+








d


p


[


v


]


}






记忆化搜索,或按拓扑序递推都行。

记忆化搜索



AC

\text{AC}







AC






代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int ans = 0, anss[50005];
int tot, adj[50005], fir[50005], nxt[50005], w[50005];

void add(int a, int b, int c) {
	adj[++tot] = b;
	nxt[tot] = fir[a];
	fir[a] = tot;
	w[tot] = c;
	return ;
}

int ask(int a) {
	if (anss[a]) return anss[a];
	int now = 0;
	for (int t = fir[a]; t; t = nxt[t]) {
		now = max(now, w[t]+ask(adj[t]));
	}
	anss[a] = now;
	return now;
}

int main()
{
	int n, m, a, b, c;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	for (int i = 1; i <= n; i++) {
		ans = max(ans, ask(i));
	}
	cout << ans << endl;
	return 0;
}

拓扑序递推



AC

\text{AC}







AC






代码:

#include <cstdio>
#include <cstring>
#include <algorithm>

constexpr int MV(1e3+5), ME(5e3+5);

struct Ed
{
	int v, d;
	Ed *ne;
} ed[ME], *head[MV];
int tot;
#define edd(uu, vv, dd) ed[++tot].ne=head[uu], ed[tot].v=vv, ed[tot].d=dd, head[uu]=ed+tot


int V, E;
int ind[MV], dp[MV];
void topo_sort()
{
	static int q[MV];
	memset(dp, 0, sizeof(*dp) * (V+2));
	int hd = 0, tl = 0;
	for (int u=1; u<=V; ++u)
		if (!ind[u])
			q[tl++] = u;

	while (hd != tl)
	{
		int u = q[hd++];
		for (Ed *p=head[u]; p; p=p->ne)
		{
			int v = p->v;
			dp[v] = std::max(dp[v], dp[u] + p->d);
			if (--ind[v] == 0)
				q[tl++] = v;
		}
	}
}


int main()
{
	scanf("%d %d", &V, &E);
	while (E--)
	{
		int u, v, d;
		scanf("%d %d %d", &u, &v, &d);
		edd(u, v, d);
		++ind[v];
	}

	topo_sort();
	printf("%d\n", *std::max_element(dp+1, dp+V+1));
	
	return 0;
}



[D]:思维

设第一项为x,以此求得之后的每一项,根据非负这一条件求x的范围(或者无解)




AC

\text{AC}







AC






代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#define N 1000010
#define LL long long
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
using namespace std;

int n,i,cnt;
LL up,down;
LL a[N],z[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline int read(){
	int p=0,c=getchar();
	while (c<48||c>57)	c=getchar();
	while (c>=48&&c<=57)	p=(p<<1)+(p<<3)+c-48,c=getchar();
	return p;
}

int main(){
//	freopen("zht.in","r",stdin);
//	freopen("zht.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)	scanf("%lld",&a[i]);
	z[++cnt]=0;
	for (i=1;i<=n;i++){
		z[cnt+1]=a[i]-z[cnt];	cnt++;
	}
	down=-INF*2;	up=INF*2;
	for (i=1;i<=n+1;i++)
		if (i%2)	down=Max(down,-z[i]);
		else up=Min(up,z[i]);
	if (up>=down)	cout<<up-down+1<<endl;
	else cout<<"0"<<endl;
	return 0;
}



[E]:素数,思维




T

\text{T}







T






组数据,每组输入一个比例(两个数



a

b

a b






a


b





),是整数



or

\text{or}







or






最多不超过五位的小数(



a

,

b

(

0

,

100

)

a, b\in (0, 100)






a


,




b













(


0


,




1


0


0


)





),问是否存在质数



p

,

q

p, q






p


,




q





,使得



a

:

b

 

=

=

 

p

:

q

a:b\ ==\ p:q






a




:








b






=






=










p




:








q





。若存在则输出



p

+

q

p+q






p




+








q





最小时的



p

 

q

p\ q






p




q





,若不存在输出



impossible

\text{impossible}







impossible






先都转化为整数,然后求



gcd

\text{gcd}







gcd






化简再检查是否都为质数即可。

注意



a

=

=

b

a==b






a




=






=








b





时答案是



2

 

2

2\ 2






2




2





,而不是



impossible

\text{impossible}







impossible









AC

\text{AC}







AC






代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

int prime[10000005], noprime[10000005], cnt_p;

void Euler(int top) {
	int i, j;
	for (i = 2; i <= top; i++) {
		if (!noprime[i])
			prime[++cnt_p] = i;
		for (j = 1; j <= cnt_p && prime[j]*i <= top; j++) {
			noprime[prime[j]*i] = true;
			if (i%prime[j]==0) {
				break;
			}
		}
	}
	return ;
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
} 

char s[100];
int get() {
	scanf("%s", s);
	int len = strlen(s);
	int point = 0;
	for (int i = 0; i < len; i++)
		if (s[i] == '.') {
			point = i;
			break;
		}
	if (point == 0) {
		int ans = 0;
		int now = 100000;
		for (int i = len - 1; i >= 0; i--) {
			ans += now*(s[i]-'0');
			now *= 10;
		}
		return ans;
	} else {
		int ans = 0;
		int now = 100000;
		for (int i = point - 1; i >= 0; i--) {
			ans += now*(s[i]-'0');
			now *= 10;
		}
		now = 10000;
		for (int i = point + 1; i < len; i++) {
			ans += now*(s[i]-'0');
			now /= 10;
		}
		return ans;
	}
}

int main(){
	int n;
	double a, b;
	Euler(10000000);
	noprime[1] = true;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int aa = get();
		int bb = get();
		int g = gcd(aa, bb);
		aa /= g; bb /= g;
		if (aa == bb) {
			printf("2 2\n");
			continue ;
		}
		if (noprime[aa]||noprime[bb]) {
			printf("impossible\n");
			continue ;
		} else {
			printf("%d %d\n", aa, bb);
		}
	}
	return 0;
}



[F]:找规律,斐波那契

根据题意,有且仅有斐波那契相邻两项符合要求

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#define N 100010
#define LL long long
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
using namespace std;

int n,i,flag;
int a[N],b[30*N],d[30*N];

vector <int> c[30*N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
	int p=0,c=getchar();
	while (c<48||c>57)	c=getchar();
	while (c>=48&&c<=57)	p=(p<<1)+(p<<3)+c-48,c=getchar();
	return p;
}

int main(){
//	freopen("zht.in","r",stdin);
//	freopen("zht.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)	scanf("%d",&d[i]);	
	a[1]=1;	a[2]=2;
	for (i=3;i<=30;i++)	a[i]=a[i-1]+a[i-2];
	for (i=1;i<=30;i++)	b[a[i]]=1;
	for (i=1;i<=n;i++)	c[d[i]].push_back(i);
	if (c[1].size()>=2){
		cout<<c[1][0]<<" "<<c[1][1]<<endl;
		return 0;
	}
	for (i=1;i<30;i++)
		if (c[a[i]].size()&&c[a[i+1]].size()){
			cout<<c[a[i]][0]<<" "<<c[a[i+1]][0]<<endl;
			return 0;
		}
	cout<<"impossible"<<endl;
	return 0;
}



[G(补)]:计几

【计几,待补ing】




[H]:模拟,枚举

给一个数



m

[

1

,

1

0

16

]

m \in [1, 10^{16}]






m













[


1


,




1



0











1


6










]





,问是否存在



n

3

,

s

1

n\ge 3, s\ge 1






n













3


,




s













1





使得



m

=

i

=

1

s

i

(

n

1

)

m = \sum\limits_{i=1}^{s}i^{(n-1)}






m




=

















i


=


1



















s





















i











(


n





1


)














若存在,输入任意一组解即可。若不存在输出



impossible

\text{impossible}







impossible






考虑到



(

x

k

)

(

x

k

+

1

)

(\sum x^k) \sim (x^{k+1})






(








x










k









)













(



x











k


+


1










)





,根据题意幂指数又至少是2,因此暴力枚举也可以接受(最多枚举



1

0

6

10^{6}






1



0











6













次),因此直接莽。超过范围时直接



break

\text{break}







break






掉就行。




AC

\text{AC}







AC






代码:

#include <cstdio>
#define LL long long

int main()
{
	LL x, n;
	scanf("%lld", &x);
	int a1, a2;
	bool ok = false;
	for (int p=2; p<59; ++p)
	{
		LL sum = 0;
		for (int i=1; i<=x; ++i)
		{
			LL pro = 1;
			for (int k=0; k<p; ++k)
			{
				pro *= i;
				if (pro > x)
					break;
			}
			if (pro > x)
				break;

			sum += pro;
			if (sum > x)
				break;

			if (sum == x)
			{
				a1 = p, a2 = i;
				ok = true;
				goto ex;
			}
		}
	}
	
	ex:;
	if (ok)
		printf("%d %d", a1+1, a2);
	else
		puts("impossible");
	
	return 0;
}



[I]:阅读理解

一道阅读理解题…给出长度



n

[

1

,

1000

]

n\in[1, 1000]






n













[


1


,




1


0


0


0


]





,然后给出两个长度均为



n

n






n





的数组



a

[

 

]

,

b

[

 

]

a[\ ], b[\ ]






a


[




]


,




b


[




]





,每个数都



[

1

,

1000

]

\in[1, 1000]















[


1


,




1


0


0


0


]











a

a






a





数组的所有数加上一个非负数



d

d






d





,使得



a

a






a





的字典序

不小于




b

b






b





,问



d

d






d





最小能取多少。

先看看加



0

0






0





行不行,如果不行,那么要么加



b

[

0

]

a

[

0

]

b[0]-a[0]






b


[


0


]













a


[


0


]





,要么加



b

[

0

]

a

[

0

]

+

1

b[0]-a[0]+1






b


[


0


]













a


[


0


]




+








1





。暴力即可。




AC

\text{AC}







AC






代码:

#include <cstdio>

constexpr int MN(1e3+7);

int n, a[MN], b[MN];
bool check(int d)	// a >= b
{
	for (int i=0; i<n; ++i)
	{
		if (a[i]+d > b[i])
			return true;
		else if (a[i]+d < b[i])
			return false;
	}
	return true;
}


int main()
{
	scanf("%d", &n);
	for (int i=0; i<n; ++i)
		scanf("%d", a+i);
	for (int i=0; i<n; ++i)
		scanf("%d", b+i);
	
	int ans;
	if (check(0))
		ans = 0;
	else if (check(b[0]-a[0]))
		ans = b[0]-a[0];
	else
		ans = b[0]-a[0]+1;

	printf("%d\n", ans);
	
	return 0;
}



[J]:

有待填坑




[K(补)]:背包,dp

首先按照背包求出可以拼凑出的所有可能情况,用(i,j)表示用i根电缆可以拼出长度j(此时不重叠),答案即为




m

a

x

j

+

10

g

i

+

1

max{\frac{j+10-g}{i+1}}






m


a


x















i


+


1
















j


+


1


0





g


























注意判断无解和长度过长的情况

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define l(x) x<<1
#define r(x) (x<<1)+1
#define N 100010
#define LL long long
using namespace std;

int n,g,i,j,k;
int a[65];
bool f[70010][65];
double Ans;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline double Max(double a,double b){return (a>b)?a:b;}

inline int read(){
	int p=0;	char	c=getchar();
	while (c<48||c>57)	c=getchar();
	while (c>=48&&c<=57)	p=(p<<1)+(p<<3)+c-48,c=getchar();
	return p;
}

int main(){
	scanf("%d%d",&n,&g);
	Ans=-1;
	for (i=1;i<=n;i++)	scanf("%d",&a[i]);
	f[0][0]=1;	sort(a+1,a+1+n);
	for (k=1;k<=n;k++)
		for (i=60600-a[k];i>=0;i--)
			for (j=0;j<=n;j++){
				if (!f[i][j])	continue;
				f[i+a[k]][j+1]=1;
			}
	for (i=g-10;i<=60600;i++){
		for (j=1;j<=n;j++){
			if (!f[i][j])	continue;
			if (i-j*5+5>g)	continue;
			Ans=Max(Ans,(double)1.0*(i+10-g)/(j+1));
		}
	}
	if (Ans>=0)	printf("%.10lf\n",Ans);
	else printf("impossible\n");
	return 0;
}



[L(补)]:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int s[105][105];
int ans[105][105];
int map[105][105];

void clean(int a, int b) {
	s[a-1][b-1] --;
	s[a-1][b]--;
	s[a-1][b+1] --;
	s[a][b-1]--;
	s[a][b] --;
	s[a][b+1] --;
	s[a+1][b-1]--;
	s[a+1][b] --;
	s[a+1][b+1] --;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n+2; i++) 
		for (int j = 1; j <= m+2; j++)
			scanf("%d", &s[i][j]);
	for (int i = 1; i <= n+2; i++)
		for (int j = 1; j <= m+2; j++) {
			if (s[i][j] == 1) {
				map[i+1][j+1] = 1;
				clean(i+1, j+1);
			}
		}
	for (int i = 1; i <= n+3; i++) for (int j = 1; j <= m+3; j++) {
		if (s[i][j] < 0) {
			printf("impossible\n");
			return 0;
		}
	}
	for (int i = 1; i <= m+3; i++) if (map[1][i]||map[n+2][i]) {
		printf("impossible\n");
		return 0;
	}
	for (int i = 1; i <= n+3; i++) if (map[i][1]||map[i][m+2]) {
		printf("impossible\n");
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			if (map[i+1][j+1]) printf("X");
			else printf(".");
		cout << endl;
	}
	return 0;
}



[M]:Kruskal+倍增(树上链查询)  or  并查集维护连通块+LCA  or  Kruskal+暴力树剖(树上链查询)

给定一个矩阵



h

[

 

]

[

 

]

[

1

,

1

0

6

]

h[\ ][\ ] \in[1, 10^6]






h


[




]


[




]













[


1


,




1



0










6









]





,行列数



[

1

,

500

]

\in[1, 500]















[


1


,




5


0


0


]





,矩阵内两个格点间的路径只能沿邻接方向(上下左右)。定义简单路径的



m

i

n

min






m


i


n





值是其所经过的点中的最小值。有



q

[

1

,

1

0

5

]

q\in[1, 10^5]






q













[


1


,




1



0










5









]





次查询,每次询问两个位置,求在这两点间的众多路径中,



m

a

x

max






m


a


x





值最小的那条路径的



m

a

x

max






m


a


x





值。

  • 思路1:


    Kruskal + 倍增


    。首先在每两个点之间连边,边权为两点点权的较大者,之后用



    Kruskal

    \text{Kruskal}







    Kruskal






    建一棵最小生成树,对于每次询问,在生成树上求以此两点为端点的链上的最大值。在生成树上做

    倍增

    即可。时间复杂度





    O

    (

    N

    2

    l

    o

    g

    (

    N

    2

    )

    +

    Q

    l

    o

    g

    (

    N

    2

    )

    )

    O(N^2log(N^2)+Qlog(N^2))






    O


    (



    N










    2









    l


    o


    g


    (



    N










    2









    )




    +








    Q


    l


    o


    g


    (



    N










    2









    )


    )






  • 思路2:


    并查集


    +


    LCA


    。把所有点(不是边,排边是



    Kruskal

    \text{Kruskal}







    Kruskal






    )按



    h

    h






    h





    值排序,从小到大依次加点,用并查集维护连通块(但也是利用了



    Kruskal

    \text{Kruskal}







    Kruskal






    的思想),同时建一棵

    保证父节点的



    h

    h






    h





    值不小于子结点的最小生成树

    (为什么这样建出来是最小生成树?因为是从小到大加点的;为什么有这样的性质?因为连边时总是让后遍历到的点做父节点)。每次加点轮到



    u

    u






    u





    时打上访问标记,然后依次看看其上下左右已经被访问过的点



    v

    v






    v





    所属的连通块



    f

    v

    fv






    f


    v





    是否就是



    u

    u






    u





    ,如果不是,则加



    u

    f

    v

    u \rightarrow fv






    u













    f


    v





    的这么一条边作为生成树上的边,再把



    f

    v

    fv






    f


    v





    连通块并到



    u

    u






    u





    上去(



    f

    a

    [

    f

    v

    ]

    =

    u

    fa[fv] = u






    f


    a


    [


    f


    v


    ]




    =








    u





    ),然后继续操作。全部操作完后就

    建成了

    有前述性质的生成树。有了这样的性质,对于每次询问,只要找到两点的



    LCA

    \text{LCA}







    LCA






    ,输出



    h

    [

    L

    C

    A

    ]

    h[LCA]






    h


    [


    L


    C


    A


    ]





    即可(链上点



    h

    h






    h





    最大者一定是



    L

    C

    A

    LCA






    L


    C


    A





    )。这种做法可以达到





    O

    (

    N

    2

    l

    o

    g

    (

    N

    2

    )

    +

    Q

    )

    O(N^2log(N^2)+Q)






    O


    (



    N










    2









    l


    o


    g


    (



    N










    2









    )




    +








    Q


    )






  • 思路3:


    Kruskal + 点权树剖


    。其实是思路1的暴力做法,复杂度多一个



    l

    o

    g

    log






    l


    o


    g











    O

    (

    N

    2

    l

    o

    g

    (

    N

    2

    )

    +

    Q

    l

    o

    g

    2

    (

    N

    2

    )

    )

    O(N^2log(N^2)+Qlog^2(N^2))






    O


    (



    N










    2









    l


    o


    g


    (



    N










    2









    )




    +








    Q


    l


    o



    g










    2









    (



    N










    2









    )


    )







    的。不过用


    zkw线段树


    还是可以在一半时限内通过(数据不是很强)。

Kruskal + 倍增代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#define N 500010
#define LL long long
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
using namespace std;

int n,m,i,cnt,x,y,X,Y,L,lsum=1,q,j;
int head[N],fa[N],f[N][20],cost[N][20],v[N],d[N];
int a[510][510],p[20];

struct Tree{
	int x,y,l;
}t[N*2];

struct Edge{
	int t,next,l;
}e[N*4];

vector <int> son[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
	int p=0,c=getchar();
	while (c<48||c>57)	c=getchar();
	while (c>=48&&c<=57)	p=(p<<1)+(p<<3)+c-48,c=getchar();
	return p;
}

inline int ID(int x,int y){
	return 	(x-1)*m+y;
}

bool cmp(Tree x,Tree y){
	return x.l<y.l;
}

inline int Find(int x){return (fa[x]==x)?x:fa[x]=Find(fa[x]);}

inline void Add(int s,int t,int l){
	e[lsum].t=t;	e[lsum].next=head[s];	e[lsum].l=l;	head[s]=lsum++;
	e[lsum].t=s;	e[lsum].next=head[t];	e[lsum].l=l;	head[t]=lsum++;
}

inline void Dfs(int x){
	int i=0,s=0;
	for (i=1;i<=18;i++){
		f[x][i]=f[f[x][i-1]][i-1];
		cost[x][i]=Max(cost[x][i-1],cost[f[x][i-1]][i-1]);
	}
	if (!son[x].size())	return;
	for (s=son[x].size(),i=0;i<s;i++)	Dfs(son[x][i]);
}

inline void Maketree(int x){
	int i=0;
	v[x]=1;
	for (i=head[x];i;i=e[i].next){
		if (v[e[i].t])	continue;
		cost[e[i].t][0]=e[i].l;	f[e[i].t][0]=x;	d[e[i].t]=d[x]+1;
		Maketree(e[i].t);	son[x].push_back(e[i].t);
	}
}

inline void Ready(){
	int i=0,j=0,P=0,q=0,s=0;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++){
			if (j<m)	t[++cnt]=(Tree){ID(i,j),ID(i,j+1),Max(a[i][j],a[i][j+1])};
			if (i<n)	t[++cnt]=(Tree){ID(i,j),ID(i+1,j),Max(a[i][j],a[i+1][j])};
		}
	sort(t+1,t+1+cnt,cmp);
	for (i=1;i<=n*m;i++)	fa[i]=i;
	for (i=1;i<=cnt;i++){
		P=Find(t[i].x);	q=Find(t[i].y);
		if (P==q)	continue;
		s++;	fa[P]=q;	Add(t[i].x,t[i].y,t[i].l);
		if (s>=n*m-1)	break;
	}
	for (i=1,p[0]=1;i<=18;i++)	p[i]=p[i-1]*2;
	d[1]=1;	Maketree(1);	Dfs(1);
}

inline int LCA(int x,int y){
	int l=0,i=0;	L=0;
	if (d[x]<d[y])	Swap(x,y);
	l=d[x]-d[y];
	for (i=0;i<=18;i++)
		if (l&p[i])	L=Max(L,cost[x][i]),x=f[x][i];
	if (x==y)	return x;
	for (i=18;i>=0;i--)
		if (f[x][i]!=f[y][i]){
			L=Max(L,cost[x][i]),L=Max(L,cost[y][i]),x=f[x][i],y=f[y][i];
		}
	L=Max(L,cost[x][0]);	L=Max(L,cost[y][0]);
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	Ready();
	while (q--){
		x=read();	y=read();	X=read();	Y=read();
		if (x==X&&y==Y)	{
			printf("%d\n",a[x][y]);
			continue;
		}
		x=ID(x,y);	y=ID(X,Y);
		LCA(x,y);	printf("%d\n",L);
	}
	return 0;
}

并查集 + LCA代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX(a, b) ((a)>(b)?(a):(b))
#define MIN(a, b) ((a)<(b)?(a):(b))

constexpr int MN(503), MV(MN*MN), MQ(1e5+5);

int R, C, Q;
inline int ID(const int r, const int c)
{
	return (r-1) * C + c;
}
int h[MV];
bool vis[MN][MN];
int ans[MQ];


struct Ed
{
	int v, ne;
} ed[MV * 2], qed[MQ * 2];
int head[MV], ent;
int qhead[MV], qent;
#define edd(uu, vv) ed[++ent].ne=head[uu], ed[ent].v=vv, head[uu]=ent
#define qedd(uu, vv) qed[++qent].ne=qhead[uu], qed[qent].v=vv, qhead[uu]=qent



struct UF
{
	int uf[MV];
	int find(const int x)
	{
		return uf[x] ? (uf[x]=find(uf[x])) : x;
	}
	bool merge(int x, int y)
	{
		return ((x=find(x)) == (y=find(y)) ? false : (uf[x]=y, true));
	}
};


int build_tree()
{
	int root;
	struct Node
	{
		int r, c, d;
		bool operator <(const Node &o) const
		{
			return d < o.d;
		}
	};
	static Node a[MV];

	int tot = 0;
	scanf("%d %d %d", &R, &C, &Q);
	for (int r=1; r<=R; ++r)
		for (int c=1; c<=C; ++c)
			scanf("%d", &h[++tot]), a[tot] = {r, c, h[tot]};
	std::sort(a+1, a+1+tot);

	static UF uf;
	constexpr int dr[]{-1, 1, 0, 0}, dc[]{0, 0, -1, 1};
	for (int i=1; i<=tot; ++i)
	{
		vis[a[i].r][a[i].c] = true;
		int u = ID(a[i].r, a[i].c);
		for (int k=0; k<4; ++k)
		{
			int rr = a[i].r+dr[k], cc = a[i].c+dc[k];
			if (vis[rr][cc])
			{
				int v = ID(rr, cc);
				int fv = uf.find(v);
				if (fv != u)
					edd(u, fv), uf.uf[fv] = root = u;
			}
		}
	}
	
	return root;
}


void read_q()
{
	int r1, c1, r2, c2;
	for (int i=1; i<=Q; ++i)
	{
		scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
		int u = ID(r1, c1), v = ID(r2, c2);
		qedd(u, v), qedd(v, u);
	}
}


void tarjan(const int u)
{
	static UF uf;
	static bool vis[MV];

	vis[u] = true;
	for (int i=qhead[u]; i; i=qed[i].ne)
	{
		int v = qed[i].v;
		if (vis[v])
		{
			int lca = uf.find(v);
			ans[(i+1)>>1] = h[lca];
		}
	}

	for (int i=head[u]; i; i=ed[i].ne)
	{
		int v = ed[i].v;
		tarjan(v), uf.uf[v] = u;
	}
}


int main()
{
	int root = build_tree();
	read_q();
	tarjan(root);
	for (int i=1; i<=Q; ++i)
		printf("%d\n", ans[i]);

	return 0;
}

Kruskal + 点权树剖代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <climits>

#define MAX(a, b) (((a)>(b) ? (a):(b)))
#define SW(a, b) do{auto __tp=a; a=b; b=__tp;}while(0)


constexpr int MN(503), MV(MN*MN), ME(MV*8);
using wint = int;


struct Ev
{
	int u, v;
	wint d;
	Ev(void) { }
	Ev(int u, int v, wint d) : u(u), v(v), d(d) { }
	bool operator <(const Ev &o) const
	{
		return d < o.d;
	}
};
std::vector<Ev> ev;
int R, C;
inline int ID(int r, int c)
{
	return (r-1) * C + c;
}



struct Ed
{
	int v;
	Ed *ne;
} ed[ME], *head[MV];
int tot;
#define edd(uu, vv) ed[++tot].ne=head[uu], ed[tot].v=vv, head[uu]=ed+tot


int uf[MV];
inline int find(const int x)
{
	return uf[x] ? (uf[x]=find(uf[x])) : x;
}
inline bool merge(int x, int y)
{
	return (x=find(x)) == (y=find(y)) ? false : (uf[x]=y, true);
}


template <typename vint, typename xint = int>
class ZKW
{
private:

	vint t[MV << 1];	// zkw只要2n空间
	xint n, _offset;	// 必须要有offset
#define _getl(l) l-_offset
#define _getr(r) r+1-_offset
#define VINT_MIN INT_MIN

#define li i<<1
#define ri i<<1|1
#define pu(i) t[i] = MAX(t[li], t[ri])

public:

	void build(const vint *arr, const xint l, const xint r)
	{
		_offset = l;
		n = r-l+1;

		memcpy(t+n, arr+l, sizeof(vint) * n);
		for (int i=n-1; i; --i)
			pu(i);
	}

	vint max(xint l, xint r)
	{
		vint m = VINT_MIN, tp;
		for (l=_getl(l)+n, r=_getr(r)+n; l<r; l>>=1, r>>=1)
		{
			if (l&1)
				tp = t[l++], m = MAX(m, tp);
			if (r&1)
				tp = t[--r], m = MAX(m, tp);
		}
		return m;
	}
};



namespace HLD
{
ZKW<wint> st; 

int de[MV], fa[MV], sz[MV], son[MV];
void dfs1(const int u, const int f)
{
	de[u] = de[fa[u]=f] + (sz[u]=1);
	int msz = 0;
	for (Ed *p=head[u]; p; p=p->ne)
	{
		if (p->v != f)
		{
			dfs1(p->v, u);
			if (sz[p->v] > msz)
				msz = sz[p->v], son[u] = p->v;
		}
	}
}


wint a0[MV], a[MV];
int top[MV], id[MV], dnt;
void dfs2(const int u)
{
	top[u] = son[fa[u]]==u ? top[fa[u]] : u;
	id[u] = ++dnt;
	a[dnt] = a0[u];

	if (son[u])
	{
		dfs2(son[u]);
		for (Ed *p=head[u]; p; p=p->ne)
			if (p->v != fa[u] && p->v != son[u])
				dfs2(p->v);
	}
}

wint max(int u, int v)
{
	wint m = VINT_MIN, tp;
	while (top[u] != top[v])
	{
		if (de[top[u]] > de[top[v]])
			SW(u, v);
		tp = st.max(id[top[v]], id[v]);
		m = MAX(m, tp);
		v = fa[top[v]];
	}
	if (de[u] > de[v])
		SW(u, v);
	tp = st.max(id[u], id[v]);
	return MAX(m, tp);
}

void build_graph()
{
	static int g[MN][MN];
	for (int r=1, u, v; r<=R; ++r)
	{
		for (int c=1; c<=C; ++c)
		{
			scanf("%d", g[r]+c);
			a0[ID(r, c)] = g[r][c];
			if (r > 1)
				ev.emplace_back(Ev(ID(r, c), ID(r-1, c), MAX(g[r][c], g[r-1][c])));
			if (c > 1)
				ev.emplace_back(Ev(ID(r, c), ID(r, c-1), MAX(g[r][c], g[r][c-1])));
		}
	}

	int ent = 0, V = R*C;
	std::sort(ev.begin(), ev.end());
	for (auto &e : ev)
	{
		if (merge(e.u, e.v))
		{
			edd(e.u, e.v), edd(e.v, e.u);
			if (++ent == V-1)
				break;
		}
	}
		

	dfs1(1, 0);
	dfs2(1);
	st.build(a, 1, dnt);
}

}


int main()
{
	int q;
	scanf("%d %d %d", &R, &C, &q);
	HLD::build_graph();

	while (q--)
	{
		int r1, c1, r2, c2;
		scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
		int u = ID(r1, c1), v = ID(r2, c2);
		printf("%d\n", HLD::max(u, v));
	}
}



补题方案

A,M 均为

LCA+树上路径

,值得补题。

G 为计几,难度可能不是很大,也最好补补。



总结

  • 要做多源最短路时,如果floyd复杂度不能承受,要考虑能不能在树上用LCA求解



版权声明:本文为weixin_42102584原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。