Codeforces Round #635 (Div. 2) 题解
分类:
IT文章
•
2025-01-27 10:55:31
A. Ichihime and Triangle
题意：
已知$ a ≤ x ≤ b ，b ≤ y ≤ c , c ≤ z ≤ d $,让你确定 $x , y , z$ 使其构成三角形的三条边
思路：
直接令三条边长为$ b , c , d $即可
![]()
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
ll t,a,b,c,d;
cin>>t;
while(t--){
cin>>a>>b>>c>>d;
cout<<b<<" "<<c<<" "<<c<<endl;
}
return 0;
}
View Code
B. Kana and Dragon Quest game
题意：
给一个数$ h $,你可以进行两种操作：$1.h=[h /2 +10] ,2. h=[h-10]$,问能否通过$n$种操作$1$,与$m$种操作$2$使得$h$小于等于$0$
思路：
通过解不等式$h/2 + 10 ≤ h$，我们可以发现当$h ≤ 20 $时进行操作$1$，只会使得$h$变得更大
所以我们先将$h$通过操作$1$尽可能的降至大于$20$且最小的位置，再用操作$2$判断其是否会小于等于$0$
![]()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
int main(){
ll p=read();
while(p--){
ll a,b,c;
cin>>a>>b>>c;
while(b&&a>20){
b--;
a=a/2+10;
}
if(a>c*10) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
View Cod
C. Linova and Kingdom
题意：
给一颗树，现在你可以将$K$个节点染成白色，并将其余节点染成黑色，要求所有白色节点到节点$1$路径上经过和黑色节点和最大
思路：
贪心可以发现将所有深度尽可能大的节点染成白色是最优的，但是可能出现的问题就是不能单单对深度进行排序累加，因为其父亲节点有可能也是白色点
所以我们还要统计节点的子树大小，对$dep[i] - siz[i] $ 进行排序，取前$k$大即可
![]()
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
const int manx=2e5+5;
vector<ll>g[manx];
vector<pair<ll,ll> >a;
ll cnt[manx],d[manx],col[manx];
ll n,k;
void dfs(ll u,ll pre){
d[u]=d[pre]+1; cnt[u]=1;
for(auto v: g[u]){
if(v==pre) continue;
dfs(v,u);
cnt[u]+=cnt[v];
}
a.pb(mp(d[u]-cnt[u],u));
}
int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
ll u=read(),v=read();
g[u].pb(v); g[v].pb(u);
}
dfs(1,0);
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
ll ans=0;
for(int i=0;i<k;i++)
ans+=a[i].first;
printf("%lld
",ans);
return 0;
}
View Code
![]()
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
const int N=1e5+5;
ll t,n1,n2,n3;
ll a[N],b[N],c[N];
ll solve(ll a[],ll n1,ll b[],ll n2,ll c[] ,ll n3){
ll ans=2e18,x,y,z;
for(int i=1;i<=n1;i++){
x=a[i];
int pos=lower_bound(b+1,b+1+n2,x)-b;
if(pos>=1&&pos<=n2 &&b[pos]>=x)y=b[pos];
else continue;
int l=1,r=n3;
while(l<r){
int mid=(l+r+1)>>1;
if(c[mid]<=x) l=mid;
else r=mid-1;
}
if(c[l]<=x) z=c[l];
else continue;
ans=min(ans,(x-y)*(x-y)+(x-z)*(x-z)+(y-z)*(y-z));
}
return ans;
}
int main(){
ll t=read();
while(t--){
ll n1=read(),n2=read(),n3=read();
for(int i=1;i<=n1;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n2;i++)scanf("%lld",&b[i]);
for(int i=1;i<=n3;i++)scanf("%lld",&c[i]);
sort(a+1,a+1+n1);
sort(b+1,b+1+n2);
sort(c+1,c+1+n3);
ll ans=2e18;
ans=min(ans,solve(a,n1,b,n2,c,n3));
ans=min(ans,solve(a,n1,c,n3,b,n2));
ans=min(ans,solve(b,n2,a,n1,c,n3));
ans=min(ans,solve(b,n2,c,n3,a,n1));
ans=min(ans,solve(c,n3,b,n2,a,n1));
ans=min(ans,solve(c,n3,a,n1,b,n2));
cout<<ans<<endl;;
}
return 0;
}
