Codeforces Round #635 (Div. 2)

A. Ichihime and Triangle

题目链接

题目大意

找到满足三角形边长关系的
$x,y,z$

x,y,z使得
$x,y,z$

x,y,z满足
$a le xle ble y le c le z le d$

a≤x≤b≤y≤c≤z≤d

解题思路

我们知道一最短边为底的三角形肯定存在所以我们取特殊值
时间复杂度为
$O(1)$

O(1)

$x=a,y=z=c$

x=a,y=z=c

源码

#include <bits/stdc++.h> using namespace std; int main() { int T,a,b,c,d,x,y,z;     cin>>T; while (T--) {         cin>>a>>b>>c>>d;         x=a,y=z=c;         cout<<x<<" "<<y<<" "<<z<<endl; } return 0; } 

B. Kana and Dragon Quest game

题目链接

题目大意

大龙的血量为
$h$

h，你有两个技能
$A、B$

A、B分别能够使用
$n,m$

n,m次
技能
$A$

A：
$h=leftlfloor frac{h}{2} rightrfloor + 10$

h=⌊2h​⌋+10

技能
$B$

B：
$h=h-10$

h=h−10

问你是否能够打败大龙

解题思路

我们思考什么时候使用
$A$

A技能能够使怪物的血量减少

也就是解不等式
$h < leftlfloor frac{h}{2} rightrfloor + 10$

h<⌊2h​⌋+10我们解的
$h< 20$

h<20。

所以我们的策略是当
$h>20$

h>20时不断地使用
$A$

A技能，直至
$A$

A技能用完或者
$hle20$

h≤20时停止使用
$A$

A技能，然后判断一下接下来全部使用
$B$

B技能是否能够打败大龙就可以了。

源码

#include <bits/stdc++.h> using namespace std; int main() { int T,x,m,n;     cin>>T; while (T--) {         cin>>x>>n>>m; while (x>20&&n) {             x=x/2+10;             n--; } if(x>m*10)cout<<"NO"<<endl;else cout<<"YES"<<endl; } return 0; } 

C. Linova and Kingdom

题目链接

题目大意

一共有
$n$

n个点
$n-1$

n−1条边构成一棵以节点
$1$

1为根的树，每个结点代表一个城市，我们要选取
$k$

k个城市发展工业，其余的城市发展旅游业，求每个工业城市到节点
$1$

1的道路上所经过的旅游城市数量之和。

解题思路

更具样例给的图我们很容易发现1节点肯定需要发展旅游业，这样所得到的结果才最优，所以我们在考虑哪几个城市发展旅游业比较简单。

我们先从只考虑一个旅游城市时，显而易见那么那个旅游城市肯定就是根节点
$1$

1，答案就是
$n-1$

n−1
然后我们考虑寻找第二个旅游城市，比如说我们考虑例题中的
$3$

3节点，如果我们取了
$3$

3结点，那么
$3$

3节点的所有子节点的幸福值就
$+1$

+1，但是
$3$

3节点它从一个旅游城市变成了工业城市，所以总的幸福值就会减去
$3$

3节点还没被选为旅游城市之前的幸福值，我们可以发现如果节点
$3$

3要被选为旅游城市，那么节点
$3$

3的所有父节点肯定都已经被选为旅游城市（下面有证明），所以节点
$3$

3的幸福值就是它到根节点的距离。

接下来我们证明如果节点
$i$

i要被选为旅游城市，那么节点
$i$

i的所有父节点肯定都已经被选为旅游城市。我们可以使用反证法来证明，如果节点
$i$

i的父节点中存在工业城市
$j$

j，因为节点
$j$

j肯定包含节点
$i$

i所有的子节点，那么节点
$j$

j的根节点的数量肯定比节点
$i$

i多，且需要减去的幸福值肯定不比节点
$i$

i多，所以选择
$j$

j肯定比选择
$i$

i的解更优。

所以我们得出方程为

$ans=sum^{n-k} weigth[i]-dis[i]$

ans=∑n−k​weigth[i]−dis[i]
所以我们只需要将所有的节点根据
$weigth[i]-dis[i]$

weigth[i]−dis[i]排序，然后找到最大的
$n-k$

n−k项相加即可。

因为我们需要同时得到根节点的距离和子节点的数量两个量，所以我们采用DFS。

源码

#include <bits/stdc++.h> typedef long long ll; using namespace std; const int MAXN = (int)2e5 + 5; vector<int> G[MAXN]; ll tmp[MAXN]; bool used[MAXN]; int n, k; int dfs(int x,int d) { int res=0;     used[x]=true; for (int i = 0; i < G[x].size(); i++)if(!used[G[x][i]])res+=dfs(G[x][i],d+1);     tmp[x]=res-d; return res+1; } ll solve() { dfs(1,0); sort(tmp+1,tmp+n+1,greater<int>());     ll ans=0; for (int i = 1; i <= n-k; i++)ans+=tmp[i]; return ans; } int main() {     ios::sync_with_stdio(false);     cin.tie(0); int a, b;     cin >> n >> k; for (int i = 0; i < n - 1; i++) {         cin >> a >> b;         G[a].push_back(b);         G[b].push_back(a); }     cout << solve() << endl; return 0; } 

D. Xenia and Colorful Gems

题目链接

题目大意

从
$r,g,b$

r,g,b分别找到三个数
$x,y,z$

x,y,z，使得
$(x-y)^2+(y-z)^2+(z-x)^2$

(x−y)2+(y−z)2+(z−x)2最小。

解题思路

这题我是玄学AC。
我就分析一下我玄（无）学（脑）的思路。
我想啊，这跟距离有点像，所以答案的三个数字肯定是从小到大的，两边的数肯定是对应集合中到中间的那个数的距离最小的，但是中间的那个数是哪个集合的呢，枚举啊，反正才三个。
时间复杂度
$O(nlog(n))$

O(nlog(n))

源码

#include <bits/stdc++.h> typedef long long ll; using namespace std; const int MAXN=(int)1e5+5; ll x[MAXN],y[MAXN],z[MAXN],ans; int nx,ny,nz; ll dis(ll a, ll b, ll c) { return (a-b)*(a-b)+(a-c)*(a-c)+(b-c)*(b-c); } void solve(ll *r,int nr,ll *g,int ng,ll *b,int nb) { int gl,bl;     gl=bl=0; for (int i = 0; i < nr; i++) { while(gl+1<ng&&abs(g[gl]-r[i])>=abs(g[gl+1]-r[i]))gl++; while(bl+1<nb&&abs(b[bl]-r[i])>=abs(b[bl+1]-r[i]))bl++;         ans=min(ans,dis(r[i],g[gl],b[bl])); } } int main() {     ios::sync_with_stdio(false);     cin.tie(0); int T;     cin>>T; while (T--) {         cin>>nx>>ny>>nz; for (int i = 0; i < nx; i++)cin>>x[i]; for (int i = 0; i < ny; i++)cin>>y[i]; for (int i = 0; i < nz; i++)cin>>z[i];         ans=dis(x[0],y[0],z[0]); sort(x,x+nx); sort(y,y+ny); sort(z,z+nz); solve(x,nx,y,ny,z,nz); solve(y,ny,x,nx,z,nz); solve(z,nz,y,ny,x,nx);         cout<<ans<<endl; } return 0; } 

EF补完后再写┭┮﹏┭┮