春训团队赛第四场
春训团队赛第四场
| 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
）按
hh
h
值排序，从小到大依次加点，用并查集维护连通块（但也是利用了
Kruskal\text{Kruskal}
Kruskal
的思想），同时建一棵
保证父节点的
hh
h
值不小于子结点的最小生成树
（为什么这样建出来是最小生成树？因为是从小到大加点的；为什么有这样的性质？因为连边时总是让后遍历到的点做父节点）。每次加点轮到
uu
u
时打上访问标记，然后依次看看其上下左右已经被访问过的点
vv
v
所属的连通块
fv
fv
f
v
是否就是
uu
u
，如果不是，则加
u→
f
v
u \rightarrow fv
u
→
f
v
的这么一条边作为生成树上的边，再把
fv
fv
f
v
连通块并到
uu
u
上去（
fa
[
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
]
即可（链上点
hh
h
最大者一定是
LC
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的暴力做法，复杂度多一个
lo
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求解