Codeforces Round #635 (Div. 2) 题解（A.B.C.D）hddddh的博客-

A . Ichihime and Triangle

链接：A. Ichihime and Triangle

题意：
给四个整数 a,b,c,d,从[a,b],[b,c],[c,d]选三个数构成三角形。

思路：
直接选一个 b,两个 c 就好了，这样一定能构成三角形。

代码：

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; typedef long long ll; const int maxn=5e3+7; int main (){ int k;     cin>>k; while(k--){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);         printf ("%d %d %dn",a,c,c); } } 

B. Kana and Dragon Quest game

链接： B. Kana and Dragon Quest game

题意:
怪物有初始血量 x, 可以进行 n次操作1，m次操作2.
操作1：怪物血量变成n/2+10,
操作2：怪物血量变成n-10）.
问最后能不能使血量小于等于0;
思路：

1. 对于操作1，怪物的当前血量越多，扣的就越多，而操作二扣除血量是一定的。
2. 所以我们可以贪心的先进行操作一，直到怪物血量无法再减少。
3. 然后再进行操作二就好了，这样一定是最优的。

代码：

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; typedef long long ll; const int maxn=5e3+7; int main (){ int k;     cin>>k; while(k--){ int x,n,m,flag=1; scanf("%d%d%d",&x,&n,&m); while(n>0){ if(x-(x)/2<10) break;             x=(x)/2+10;             n--; } if(x-m*10>0) printf ("NOn"); else printf ("YESn"); } } 

C. Linova and Kingdom

链接 C. Linova and Kingdom

题意：
给n个城市，这n个城市由n-1条道路组成了一棵树。以1为根节点，需要从其中选取 k 个城市作为工业城市，使得这k个城市的贡献值最大，贡献值计算规则为，这个城市到1号城市所经过的非工业城市的数量。
思路：

1. 如果我们考虑贡献值为经过城市的数量，那么答案肯定就是，节点深度最大的前k个城市。

2. 接下来考虑贡献值为经过的非工业城市的数量

3. 首先，是按照节点深度从大到小选 k个点，那么选取一个节点的时候，我们必然已经选取了它的所有的子节点，因为这个城市变成了工业城市，所以它所有子节点的贡献值都会减 1（因为它所有的子节点都要经过它到达1）.

4. 所以可以等效于每个节点的贡献值 =节点深度–子节点数，最后对贡献值排序就好了。

代码：

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; typedef long long ll; const int maxn=4e5+7; int n,m,head[maxn],depth[maxn],num=0,cnt[maxn]; int degree[maxn]; struct node{ int next,to; }; struct node edge[maxn]; void add(int u,int v){      edge[num].next=head[u];      edge[num].to=v;      head[u]=num++; } void dfs1(int u, int pre, int d){     depth[u]=d,cnt[u]=1; for(int i = head[u]; i != -1; i = edge[i].next){ int to = edge[i].to; if(to == pre) continue; dfs1(to, u, d + 1);         cnt[u]+=cnt[to]; } } int main (){ memset(head,-1,sizeof(head)); int u,v;    ll ans=0;    cin>>n>>m; for(int i=0;i<n-1;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs1(1,-1,0); for(int i=1;i<=n;i++) depth[i]-=cnt[i]-1; sort(depth+1,depth+1+n); for(int i=0;i<m;i++){       ans+=depth[n-i]; }    printf ("%lldn",ans); } 

D. Xenia and Colorful Gems

链接： D. Xenia and Colorful Gems

题意：
给三个数组，从中各选一个数 x,y,z使得(x−y)^2+ (y−z)^2+ (z−x)^2的值最小。

思路：
首先1e5,太暴力肯定是不行的，所以我们可以只枚举其中一个数组，然后在其他两个数组，分别找到最接近它的数。当然可以有两个，然后全枚举一遍就好了。把三个数组全进行一次这样的操作。

代码：

 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=4e5+7; ll a[maxn],b[maxn],c[maxn]; ll f(ll a,ll b, ll c){ return (a-b)*(a-b)+(a-c)*(a-c)+(b-c)*(b-c); } int main(){ int k;     cin>>k; while(k--){       ll ans=2e18+7;       ll px,py,pz; int x,y,z; scanf("%d%d%d",&x,&y,&z); for(int i=0;i<x;i++) scanf("%lld",&a[i]); for(int i=0;i<y;i++) scanf("%lld",&b[i]); for(int i=0;i<z;i++) scanf("%lld",&c[i]); sort(a,a+x); sort(b,b+y); sort(c,c+z); for(int i=0;i<x;i++){           py=lower_bound(b,b+y,a[i])-b;           pz=lower_bound(c,c+z,a[i])-c; if(py==y) py--; if(pz==z) pz--; if(py>0) ans=min(ans,f(a[i],b[py-1],c[pz]));//（b<a,c>=a） if(pz>0) ans=min(ans,f(a[i],b[py],c[pz-1]));//(b>=a,c<a)           ans=min(ans,f(a[i],b[py],c[pz]));//(b>=a,c>=a) } for(int i=0;i<y;i++){           px=lower_bound(a,a+x,b[i])-a;           pz=lower_bound(c,c+z,b[i])-c; if(px==x) px--; if(pz==z) pz--; if(px>0) ans=min(ans,f(a[px-1],b[i],c[pz])); if(pz>0) ans=min(ans,f(a[px],b[i],c[pz-1]));           ans=min(ans,f(a[px],b[i],c[pz])); } for(int i=0;i<z;i++){           px=lower_bound(a,a+x,c[i])-a;           py=lower_bound(b,b+y,c[i])-b; if(py==y) py--; if(px==x) px--; if(px>0) ans=min(ans,f(a[px-1],b[py],c[i])); if(py>0) ans=min(ans,f(a[px],b[py-1],c[i]));           ans=min(ans,f(a[px],b[py],c[i])); } printf("%lldn",ans); } } 

比赛的时候，D题没调出来，有点难受