给定一个格状迷宫，保证任意点均可达，且任意两格点间有且仅有一条简单路径。 给定一组移动序列，求按照这个序列走的累计路程。
按照题意对图预处理，得到一棵树，对于每对询问求 \(\text{LCA}\) 的同时求距离，累加即为答案。 一开始 \(\text{RE}\) 了两发，要注意离散化操作带来的越界问题...
求 \(\text{LCA}\)，可以 倍增 or DFS序RMQ or Tarjan，前两者带 \(log\)，后者是离线的不带 \(log\)，本题倍增即可 \(\text{AC}\)。
\(\text{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; }给定一个蓝圈和红圈，红圈严格在蓝圈内部，再给定蓝圈内两个点，两点连线直线段必穿过红圈。求在不进入红圈的情况下连接两点的曲线段长度最小值。
先求两点与红圈切线段长度，以此求得两切点间的弧上距离，答案为该距离加两切点到两点的距离。
注：\(\text{int}\) 会带来奇怪的精度问题。
\(\text{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; }求 \(\text{DAG}\) 上的最长路。
\(\text{DAG}\) 上的 \(\text{dp}\)，状态转移方程：\(dp[u] = \max\{w_{u\rightarrow v}+dp[v]\}\) 记忆化搜索，或按拓扑序递推都行。
记忆化搜索\(\text{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; }拓扑序递推\(\text{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; }设第一项为x，以此求得之后的每一项，根据非负这一条件求x的范围(或者无解)
\(\text{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; }\(\text{T}\)组数据，每组输入一个比例（两个数 \(a b\)），是整数 \(\text{or}\) 最多不超过五位的小数（\(a, b\in (0, 100)\)），问是否存在质数 \(p, q\)，使得 \(a:b\ ==\ p:q\)。若存在则输出 \(p+q\) 最小时的 \(p\ q\)，若不存在输出 \(\text{impossible}\)。
先都转化为整数，然后求 \(\text{gcd}\) 化简再检查是否都为质数即可。 注意 \(a==b\) 时答案是 \(2\ 2\) ，而不是 \(\text{impossible}\)！
\(\text{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; }根据题意，有且仅有斐波那契相邻两项符合要求
#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; }【计几，待补ing】
给一个数 \(m \in [1, 10^{16}]\)，问是否存在 \(n\ge 3, s\ge 1\) 使得 \(m = \sum\limits_{i=1}^{s}i^{(n-1)}\) 若存在，输入任意一组解即可。若不存在输出 \(\text{impossible}\)。
考虑到 \((\sum x^k) \sim (x^{k+1})\)，根据题意幂指数又至少是2，因此暴力枚举也可以接受（最多枚举 \(10^{6}\) 次），因此直接莽。超过范围时直接 \(\text{break}\) 掉就行。
\(\text{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; }一道阅读理解题...给出长度 \(n\in[1, 1000]\)，然后给出两个长度均为 \(n\) 的数组 \(a[\ ], b[\ ]\)，每个数都 \(\in[1, 1000]\)。 将 \(a\) 数组的所有数加上一个非负数 \(d\)，使得 \(a\) 的字典序不小于 \(b\)，问 \(d\) 最小能取多少。
先看看加 \(0\) 行不行，如果不行，那么要么加 \(b[0]-a[0]\)，要么加 \(b[0]-a[0]+1\)。暴力即可。
\(\text{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; }有待填坑
首先按照背包求出可以拼凑出的所有可能情况，用(i,j)表示用i根电缆可以拼出长度j(此时不重叠)，答案即为\(max{\frac{j+10-g}{i+1}}\) 注意判断无解和长度过长的情况
#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; }给定一个矩阵 \(h[\ ][\ ] \in[1, 10^6]\)，行列数 \(\in[1, 500]\)，矩阵内两个格点间的路径只能沿邻接方向（上下左右）。定义简单路径的 \(min\) 值是其所经过的点中的最小值。有 \(q\in[1, 10^5]\) 次查询，每次询问两个位置，求在这两点间的众多路径中，\(max\) 值最小的那条路径的 \(max\) 值。
思路1：Kruskal + 倍增。首先在每两个点之间连边，边权为两点点权的较大者，之后用 \(\text{Kruskal}\) 建一棵最小生成树，对于每次询问，在生成树上求以此两点为端点的链上的最大值。在生成树上做倍增即可。时间复杂度 \(O(N^2log(N^2)+Qlog(N^2))\)思路2：并查集 + LCA。把所有点（不是边，排边是 \(\text{Kruskal}\)）按 \(h\) 值排序，从小到大依次加点，用并查集维护连通块（但也是利用了 \(\text{Kruskal}\) 的思想），同时建一棵保证父节点的 \(h\) 值不小于子结点的最小生成树（为什么这样建出来是最小生成树？因为是从小到大加点的；为什么有这样的性质？因为连边时总是让后遍历到的点做父节点）。每次加点轮到 \(u\) 时打上访问标记，然后依次看看其上下左右已经被访问过的点 \(v\) 所属的连通块 \(fv\) 是否就是 \(u\)，如果不是，则加 \(u \rightarrow fv\) 的这么一条边作为生成树上的边，再把 \(fv\) 连通块并到 \(u\) 上去（\(fa[fv] = u\)），然后继续操作。全部操作完后就建成了有前述性质的生成树。有了这样的性质，对于每次询问，只要找到两点的 \(\text{LCA}\)，输出 \(h[LCA]\) 即可（链上点 \(h\) 最大者一定是 \(LCA\)）。这种做法可以达到 \(O(N^2log(N^2)+Q)\)思路3：Kruskal + 点权树剖。其实是思路1的暴力做法，复杂度多一个 \(log\)，\(O(N^2log(N^2)+Qlog^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 为计几，难度可能不是很大，也最好补补。
转载于:https://www.cnblogs.com/403-forbidden/p/11149116.html
相关资源：培训动员会上的领导讲话.doc