Atcoder AGC018 简要题解

74 阅读 0 评论 49 点赞

我是靠谱客的博主紧张御姐，最近开发中收集的这篇文章主要介绍Atcoder AGC018 简要题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

Coins

先转化为一个点只有两种属性 $x_i,y_i$ ，选出 $X$ 个 $x_i$ ， $X + Y$ 个 $x_i+y_i$ 的最大值。

如果固定选的集合那么肯定要选 $y_i$ 前 $k$ 大的，我们枚举一下第 $k$ 大的 $y_i$ 是多大然后在两边贪心即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}
 
const int N=1e5+50;
const LL INF=1e18;
int n,X,Y,Z; 
LL ans=-INF,sum,pre[N],suf[N];
struct atom {LL x,y;}a[N];
priority_queue <LL> q;
int main() {
	X=rd(), Y=rd(), Z=rd(), n=X+Y+Z;
	for(int i=1;i<=n;i++) {
		a[i].x=rd(), a[i].y=rd();
		int c=rd(); sum+=c;
		a[i].x-=c; a[i].y-=c;
		a[i].x-=a[i].y;
	}
	sort(a+1,a+n+1,[](atom c,atom d) {return c.x>d.x;});
	for(int i=1;i<=n;i++) {
		pre[i]=pre[i-1]+a[i].x+a[i].y;
		q.push(-(a[i].x+a[i].y));
		if(q.size()>X) pre[i]+=q.top(), q.pop();
	}
	while(!q.empty()) q.pop();
	for(int i=n;i>=1;i--) {
		suf[i]=suf[i+1]+a[i].y;
		q.push(-a[i].y);
		if(q.size()>Y) suf[i]+=q.top(), q.pop();
	}
	for(int i=X;i+Y<=n;++i) ans=max(ans,pre[i]+suf[i+1]);
	cout<<(ans+sum)<<'n';
}

Tree and Hamilton Path

算出若每个边独立最多被计算多少次。

然后最优情况是这些和减去重心相邻的某条边。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int,int> pii;
 
const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}
 
const int N=1e5+50;
int n,sze[N],mx_son[N],mx; LL ans;
vector <pii> edge[N];
inline void dfs(int x,int f) {
	sze[x]=1; 
	for(auto v:edge[x])
		if(v.first^f) {
			dfs(v.first,x); sze[x]+=sze[v.first];
			ans+=(LL)v.second*min(sze[v.first],n-sze[v.first])*2;
			mx_son[x]=max(mx_son[x],sze[v.first]);
		}
	mx_son[x]=max(mx_son[x],n-sze[x]);
	mx=min(mx,mx_son[x]);
}
int main() {
	n=rd(); mx=n;
	for(int i=1;i<n;i++) {
		int x=rd(), y=rd(), v=rd();
		edge[x].push_back(pii(y,v));
		edge[y].push_back(pii(x,v));
	} 
	dfs(1,0); 
	int mn=2e9;
	if((!(n&1)) && mx==n/2) {
		for(int i=1;i<=n;i++) if(mx_son[i]==n/2)
			for(auto v:edge[i]) if(mx_son[v.first]==n/2) mn=min(mn,v.second);
	} else {
		for(int i=1;i<=n;i++) if(mx_son[i]==mx)
			for(auto v:edge[i]) mn=min(mn,v.second);
	}
	ans-=mn;
	cout<<ans<<'n';
}

Sightseeing Plan

挺妙的，一条路径的贡献是与中间区域相交的块的个数。

枚举入口，出口，然后是个二维组合数求和，可以 $O (1)$ 计算。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int,int> pii;
 
const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}
 
const int N=1e7+50, mod=1e9+7;
inline int add(int x,int y) {return (x+y>=mod) ? (x+y-mod) : (x+y);}
inline int dec(int x,int y) {return (x-y<0) ? (x-y+mod) : (x-y);}
inline int mul(int x,int y) {return (long long)x*y%mod;}
inline int power(int a,int b,int rs=1) {for(;b;b>>=1,a=mul(a,a)) if(b&1) rs=mul(rs,a); return rs;}
int X[7],Y[7],ans;
struct binom {
	int fac[N],ifac[N];
	binom() {
		fac[0]=1;
		for(int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);
		ifac[N-1]=power(fac[N-1],mod-2);
		for(int i=N-2;~i;i--) ifac[i]=mul(ifac[i+1],i+1);
	}
	inline int C(int a,int b) {return mul(fac[a],mul(ifac[b],ifac[a-b]));}
} C;
 
inline int path0(int x,int y) {
	int in=C.C(y-Y[1]+x-X[1]+2,y-Y[1]+1)-C.C(y-Y[1]+x-X[2]+1,y-Y[1]+1);
	in=((LL)in-C.C(y-Y[2]+x-X[1]+1,y-Y[2])+C.C(y-Y[2]+x-X[2],y-Y[2]))%mod;
	return (in%mod+mod)%mod;
}
inline int path1(int x,int y) {
	int out=C.C(Y[6]-y+X[6]-x+2,Y[6]-y+1)-C.C(Y[6]-y+X[5]-x+1,Y[6]-y+1);
	out=((LL)out-C.C(Y[5]-y+X[6]-x+1,Y[5]-y)+C.C(Y[5]-y+X[5]-x,Y[5]-y))%mod;
	return (out%mod+mod)%mod;
}
int main() {
	for(int i=1;i<=6;i++) cin>>X[i];
	for(int i=1;i<=6;i++) cin>>Y[i];
	for(int i=X[3];i<=X[4];i++) {
		int v=mul(path0(i,Y[3]-1),path1(i,Y[3]));
		ans=dec(ans,mul(i-X[3]+1,v));
	}
	for(int i=Y[3];i<=Y[4];i++) {
		int v=mul(path0(X[3]-1,i),path1(X[3],i));
		ans=dec(ans,mul(i-Y[3]+1,v));
	}
	for(int i=X[3];i<=X[4];i++) {
		int v=mul(path0(i,Y[4]),path1(i,Y[4]+1));
		ans=add(ans,mul(i-X[3]+1+Y[4]-Y[3]+1,v));
	}
	for(int i=Y[3];i<=Y[4];i++) {
		int v=mul(path0(X[4],i),path1(X[4]+1,i));
		ans=add(ans,mul(i-Y[3]+1+X[4]-X[3]+1,v));
	}
	cout<<ans<<'n';
}

Two Trees

首先处理出在两棵树中的奇偶性，然后判断无解。

否则一定有解且 $a_i in {-1,0,1}$ ，0的点已经确定，然后我们对于每个树内部的 ${-1,1}$ 都配对一下对保证每个子树只有一个点空余。

这样两个树的匹配边一起形成二分图，随便做一个二分图染色都是合法方案（因为可以保证一对点的颜色在每个子树都不一样）。

#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;

const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}

const int N=1e5+50;

int n,ans[N];
vector <int> g[N];
struct Tree {
	int rt,col[N];
	vector <int> edge[N];
	inline int dfs(int x,int f) {
		vector <int> vec;
		int sum=1;
		for(auto v:edge[x]) {
			int t=dfs(v,x);
			sum^=1;
			if(t) vec.push_back(t);
		}
		if(sum) vec.push_back(x);
		while(vec.size()>2) {
			int u=vec.back(); vec.pop_back();
			int v=vec.back(); vec.pop_back();
			g[u].push_back(v); g[v].push_back(u);
		} return col[x]=sum,vec.size()?vec[0]:0;
	}
	inline void init() {
		for(int i=1;i<=n;i++) {
			int f=rd();
			if(~f) edge[f].push_back(i);
			else rt=i; 
		} dfs(rt,0);
	}
} T[2];
inline void dfs(int x,int c) {
	ans[x]=c;
	for(auto v:g[x])
		if(!~ans[v]) dfs(v,c^1);
}
int main() {
	n=rd(); 
	T[0].init(); 
	T[1].init();
	for(int i=1;i<=n;i++) 
		if(T[0].col[i]^T[1].col[i]) return puts("IMPOSSIBLE"),0;
	for(int i=1;i<=n;i++) ans[i]=-1;
	for(int i=1;i<=n;i++) if(!~ans[i]) dfs(i,0);
	puts("POSSIBLE");
	for(int i=1;i<=n;i++)
		printf("%d ",T[0].col[i] ? (ans[i]?1:-1) :0);
}