Codeforces Round#635(Div.2)(A~D)題解

Codeforces #635 A~D

A.Ichihime and Triangle

B.Kana and Dragon Quest game

C.Linova and Kingdom

D.Xenia and Colorful Gems

A.Ichihime and Triangle
題意:4つの正の整数a,b,c,d a,b,c,d a,b,c,dをあげて、3つの区間[a,b],[b,c],[c,d][a,b],[b,c],[c,d][a,b],[b,c],[b,c],[c,d]を表して、各区間で1つの数を取り出して、この3つの数が三角形の3つの辺に構成できるようにします.問題解:直接b,c,cを取ればよい、これにより任意の両側が第3辺より大きいことを保証する.

#include 
using namespace std;
int t,a,b,c,d;
void solve(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		printf("%d %d %d
",b,c,c); 
	}
}
int main(void){
	solve();
	return 0;
}

B.Kana and Dragon Quest game
标题:正の整数x,n,mx,n,mx,n,m.はx x xの生命値が初期に存在することを示し、n n nは1 1 1 1,mは2.操作1:x=(x/2)+10 1:x=(x/2)+10 1:x=(x/2)+10操作2:x=x−10 2:x=x−10 2:x=x−10.最後にx<=0 x<=0 x<=0 x<=0とすることができるかを問う.問題解:欲張るだけでいい、まず1操作を行い、さらに2操作を行い、注意すると、1操作でx値が大きくなる場合があるので、判断してみましょう.

#include 
using namespace std;
int t,x,n,m;
void solve(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&x,&n,&m);
		while(n--){
			if((x/2)+10>x) break;
			x=(x/2)+10;
		}
		if(m*10<x) printf("NO
");
		else printf("YES
");
	}
}
int main(void){
	solve();
	return 0;
}

C.Linova and Kingdom
标题:あなたに1本の木をあげて、1番の節点は首都で、あなたにk個の都市を工業都市に選ばせて、すべての工業都市の貢献値はこの都市から首都までの簡単な経路の上で非工業都市の数量で、k個の都市を選んだ後に貢献値の最大値はいくらですでは、この都市のすべてのサブ都市が工業都市でなければならない.そうしないと、最適ではない.サブ都市が工業都市でない場合、そのサブ都市を選択する貢献は、現在の都市の貢献よりも多くなるdeep[現在の都市]-deep[サブ都市](deepは深い).2つの配列,c o s t,t t t cost,tt cost,ttを与える.c o s t[i]cost[i]cost[i]cost[i]は、現在のノードが工業都市として選択する後の総寄与値(すべてのサブノードを含む)を表す.明らかにc o s t[i]=s i z[i](d e p[i]-1)cost[i]=siz[i]*(deep[i]-1)cost[i]=siz[i]=siz[i](deep[i]-1)cost.t t[i]tt[i]tt[i]は、現在のノードが工業都市であることを選択した後の純利益、すなわちt[i]=c o s t[i]-tt[i]=cost[i]-tt[i]=cost[i]-tt[i]=cost[i]-tt[i]=cost[i]-ΣsumΣc o s t[s o n[i]]cost[son[i].次にtt配列を並べ替える、前のm個を取ればよい.

#include 
using namespace std;
typedef long long ll;
const int MAX = 2e5+5;
int n,m,deep[MAX],u[MAX*2],v[MAX*2],cnt,first[MAX],nextt[MAX*2];
int siz[MAX];
ll cost[MAX],tt[MAX],ans;
vector<int> list1;
void add(int a,int b){
	u[cnt]=a,v[cnt]=b;
	nextt[cnt]=first[u[cnt]];
	first[u[cnt]]=cnt;++cnt;
}
void dfs(int dot,int pre){
	siz[dot]=1;
	deep[dot]=deep[pre]+1;
	for(int num = first[dot];num!=-1;num=nextt[num]){
		if(v[num]==pre) continue;
		dfs(v[num],dot);
		siz[dot]+=siz[v[num]];
	}
	cost[dot]=1ll*siz[dot]*(deep[dot]-1);
	tt[dot]=cost[dot];
	for(int num=first[dot];num!=-1;num=nextt[num]){
		if(v[num]==pre) continue;
		tt[dot]-=cost[v[num]];
	}
}
bool cmp(int a,int b){
	return a>b;
}
void solve(){
	scanf("%d%d",&n,&m);
	memset(first,-1,sizeof(first));
	for(int i=1;i<n;++i){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);add(b,a);
	}
	dfs(1,0);
	for(int i=1;i<=n;++i){
		list1.push_back(tt[i]);
	}
	sort(list1.begin(),list1.end(),cmp);
	for(int i=1;i<=m;++i) ans+=list1[i-1];
	printf("%lld
",ans);
}
int main(void){
	solve();
	return 0;
}

D.Xenia and Colorful Gems
題意:長さはそれぞれn r,n g,n bの3つの配列をあげます.nr,ng,nb. nr,ng,nb. 3つの配列からそれぞれ1つの数を選択させ、x,y,z x,y,z,x,y,y,y,y,zは、(x−y),(x−y),(x−y)+(y−y),(y−z),(y−z)+(x−z),(x−z)(*(x−y)+(y−z)*(y−z)+(x−z)*(x−z)+(x−z)*(x−z)*(x−z)*(x−y),(x−y)+(y−z),(y−z),(y−z),(y−y−z),(y−y−z),(y−y−z),(y−y−z),(y−y−z),(y−y−z),(y−z)+(x-z)∗(x-z)が最小である.題解:a a a配列の各数を列挙し、b b b,c c配列の中で最もaに近い数、b 1,b 2,c 1,c 2 b 1,b 2,c 1,c 2 b 1,b 2,c 1,c 2 b 1,b 2,c 1,c 2 b 2,c 2を探し出す.b 1 < = a , b 2 > = a , c 1 < = a , c 2 > = a . b 1<=a、b 2>=a、c 1<=a、c 2>=a、b 1<=a、b 2>=a、c 1<=a、c 2>=aと分類して最小値をとるように検討すればよい、b、c配列も上記のように操作する.

#include 
using namespace std;
typedef long long ll;
const int MAX = 2e5+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int t,nr,ng,nb,a[MAX],b[MAX],c[MAX];
ll ans=INF;
ll cal(ll x,ll y,ll z){
	return (x-y)*(x-y)+(y-z)*(y-z)+(x-z)*(x-z);
}
void solve(){
	scanf("%d",&t);
	while(t--){
		ans=INF;
		scanf("%d%d%d",&nr,&ng,&nb);
		for(int i=0;i<nr;++i) scanf("%d",&a[i]);
		for(int i=0;i<ng;++i) scanf("%d",&b[i]);
		for(int i=0;i<nb;++i) scanf("%d",&c[i]);
		sort(a,a+nr);sort(b,b+ng);sort(c,c+nb);
		for(int i=0;i<nr;++i){
			int y = lower_bound(b,b+ng,a[i])-b;
			int z = lower_bound(c,c+nb,a[i])-c;
			if(y==ng) --y;if(z==nb) --z;
			ans=min(ans,cal(a[i],b[y],c[z]));
			if(y>0) ans=min(ans,cal(a[i],b[y-1],c[z]));
			if(z>0) ans=min(ans,cal(a[i],b[y],c[z-1]));
			if(y>0&&z>0) ans=min(ans,cal(a[i],b[y-1],c[z-1]));
		}
		for(int i=0;i<ng;++i){
			int x = lower_bound(a,a+nr,b[i])-a;
			int z = lower_bound(c,c+nb,b[i])-c;
			if(x==nr) --x;if(z==nb) --z;
			ans=min(ans,cal(a[x],b[i],c[z]));
			if(x>0) ans=min(ans,cal(a[x-1],b[i],c[z]));
			if(z>0) ans=min(ans,cal(a[x],b[i],c[z-1]));
			if(x>0&&z>0) ans=min(ans,cal(a[x-1],b[i],c[z-1]));
		}
		for(int i=0;i<nb;++i){
			int x = lower_bound(a,a+nr,c[i])-a;
			int y = lower_bound(b,b+ng,c[i])-b;
			if(x==nr) --x;if(y==ng) --y;
			ans=min(ans,cal(a[x],b[y],c[i]));
			if(x>0) ans=min(ans,cal(a[x-1],b[y],c[i]));
			if(y>0) ans=min(ans,cal(a[x],b[y-1],c[i]));
			if(x>0&y>0) ans=min(ans,cal(a[x-1],b[y-1],c[i]));
		}
		printf("%lld
",ans);
	}
}
int main(void){
	solve();
	return 0;
}