AtCoder Beginner Contest 065(CD)

C - Reconciled?

思路： n , m n,m n,m等价，可假设 n ≤ m n\le m n≤m

分情况讨论：

1. n = = m 1.n==m 1.n==m

a n s = 2 ( A n n ) 2 ans=2(A_n^n)^2 ans=2(Ann​)2

2. n = m − 1 n=m-1 n=m−1

a n s = A n n × A m m ans=A_{n}^{n}\times A_{m}^m ans=Ann​×Amm​

3. n < m n<m n<m

a n s = 0 ans=0 ans=0

D - Built?

思路：最小生成树。

显然直接暴力加所有边。

考虑对按 x x x排序后。

若三个点 A , B , C A,B,C A,B,C

A , B A,B A,B连边 x b − x a x_b-x_a xb​−xa​， B , C B,C B,C连边 x c − x b x_c-x_b xc​−xb​

则 A , C A,C A,C不用再连边 x c − x a x_c-x_a xc​−xa​

同理：不用连 y c − y a y_c-y_a yc​−ya​

综上只用连相邻的 x b − x a , y b − y a x_b-x_a,y_b-y_a xb​−xa​,yb​−ya​

然后对这 2 ( n − 1 ) 2(n-1) 2(n−1)条边进行排序， k r u s k a l kruskal kruskal即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int r[N];
struct edge{
	int u,v,w;
	bool operator<(const edge& e)const{
		return w<e.w;
	}
}e[N<<1];
struct point{
	int x,y,id;
}a[N];
bool cmp1(point a,point b){
	return a.x<b.x;
}
bool cmp2(point a,point b){
	return a.y<b.y;
}
int find(int x){
	return r[x]==x?x:r[x]=find(r[x]);
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		a[i].id=r[i]=i;
	}
	sort(a+1,a+n+1,cmp1);
	int s=0;
	for(int i=2;i<=n;i++){
		e[s++]={a[i-1].id,a[i].id,a[i].x-a[i-1].x};
	}
	sort(a+1,a+n+1,cmp2);
	for(int i=2;i<=n;i++){
		e[s++]={a[i-1].id,a[i].id,a[i].y-a[i-1].y};
	}
	sort(e,e+s);
	int tot=0;
	ll ans=0;
	for(int i=0;i<s;i++){
		int u=e[i].u,v=e[i].v;
		u=find(u),v=find(v);
		if(u!=v){
			r[u]=v;
			tot++;
			ans+=e[i].w;
		}
		if(tot==n-1) break;
	} 
	cout<<ans<<endl; 
	return 0;
}