Codeforces Round #635 (Div. 2) A~D
https://codeforces.com/contest/1337/
A. Ichihime and Triangle
題意
給定四個數字 \(a,b,c,d(1\le a\le b\le c\le d\le 1e9)\)，請給出任意一組滿足下述條件的 \(x,y,z\) ，
- \(a\le x\le b \le y\le c \le z \le d\)
- \(x,y,z\) 可以構成三角形
解題
當 \(y=z=c\) 時，\(x\) 取 \([a,b]\) 中任意值都可以組成一個等腰三角形，
for i in range(int(input())):
a,b,c,d = list(map(int,input().split()))
print(b,c,c)
B. Kana and Dragon Quest game
題意
你在打一個血量為 \(x\) 的boss，你現在有兩種技能可以釋放，
- 技能一 Void Absorption：
- 當boss血量為 \(h\) 時，釋放此技能可以使boss血量變成 \(\lfloor \frac{h}{2} \rfloor + 10\)
- 技能二 Lightning Strike
- 打擊boss造成10點傷害，即 \(h-10\)
給出一個血量 \(x\) ，以及可以釋放技能一的次數 \(n\) 和技能二的次數 \(m\)，詢問能否殺死boss，
解題
以貪心的方法考慮，當boss血量越高使用技能一打出的效果越好，所以我們的方案是優先盡可能的把技能一打出，再打出剩下的 \(m\) 個技能二，需要注意的是，當boss血量小于等于20時，技能一就無法造成傷害了，甚至成了回血技，
for i in range(int(input())):
x,n,m = list(map(int,input().split()))
while n>0 and x>20:
x = x//2+10
n-=1
while m>0 and x>0:
x-=10
m-=1
print("YES" if x<=0 else "NO")
C. Linova and Kingdom
題意
有 \(n\) 個城市，編號從 \(1\) 到 \(n\) ，其中 \(1\) 為首都，在這些城市中有 \(n-1\) 條雙向道路，可以連通兩個城市，保證每兩個城市之間都存在的唯一的路徑可以相互到達，即這是一個全連通的圖，
給定一個 \(k\) ，你需要從 \(n\) 個城市中選出 \(k\) 個城市發展工業，其余的城市發展旅游業，每年每個工業城市都會派出一個代表，前往首都，在去的路上代表每經過一個旅游城市就會貢獻 \(1\) 點滿意度，詢問你可以得到的最大的滿意度和是多少，
解題
這是一道大毒瘤題，通過人數不及上一題1/2（悲
首先邊為 \(n-1\) 的全連通圖，說明這是一顆樹，我們設編號 \(1\) 的節點為根，
對于一個城市來說，設需要經過他到達首都的其他城市到的數量為 \(ct\)，即這個節點下面的子孫節點個數，設他到達首都需要經過的城市個數，即這個節點的深度 \(depth\)，首都的深度為 \(0\) ，
當把一個城市選做為工業城市，那么這個城市對滿意度的貢獻度 \(v = depth - ct\) ，
選取貢獻度最大的 \(k\) 個城市作為工業城市即可，
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
struct node{
int i = 0; //編號
int v = 0; //貢獻度
int depth = 0; //深度
vector<int>e; //邊
}nodes[2*e5];
int dfs(int i,int last){
int ct = 0;
nodes[i].depth = nodes[last].depth+1;
for(auto it:nodes[i].e) if(it!=last) ct+=dfs(it,i);
nodes[i].v = nodes[i].depth - ct;
return ct+1;
}
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
//freopen("1.out","w",stdout);
int n,k;
while(cin>>n>>k){
frr(i,1,n+1){
nodes[i].i = i;
nodes[i].v = 0;
nodes[i].e.clear();
}
fr(i,n-1){
int a,b;cin>>a>>b;
nodes[a].e.push_back(b);
nodes[b].e.push_back(a);
}
nodes[0].depth = -1;
dfs(1,0);
ll ans = 0;
nth_element(
nodes+1,nodes+k+1,nodes+n+1,
[](node a,node b){
return a.v>b.v;
}
);
frr(i,1,k+1) ans += nodes[i].v;
cout<<ans<<endl;
}
return 0;
}
D. Xenia and Colorful Gems
題意
有三個長度分別為 \(n_r,n_g,n_r\) 的正整數陣列 \(r,g,b\)，其中 \(1\le r_i,g_i,b_i\le1e9\) ，
詢問 \((r_i-g_j)^2+(r_i-b_k)^2+(g_j-b_k)^2\) 的最小值，
解題
同樣是一道毒瘤題，通過人數接近B題的1/4，
三個 \(n\) 的范圍上限 \(1e5\) ，很明顯這是一道復雜度 \(O(nlogn)\) 的二分題，
如果想得到最小的 \((r_i-g_j)^2+(r_i-b_k)^2+(g_j-b_k)^2\) ，只需要讓 \(r_i,g_j,b_k\) 的取值足夠接近就可以了，
這里分類討論6種情況：
- \(r_i\le g_j \le b_k\)
- \(r_i\le b_k \le g_j\)
- \(g_j \le r_i \le b_k\)
- \(g_j \le b_k \le r_i\)
- \(b_k \le r_i \le g_j\)
- \(b_k \le g_j \le r_i\)
對6鐘情況分別考慮，在每種情況中遍歷第二個陣列，再對另外兩個陣列二分查找，在滿足式子的值中，找出最接近遍歷數字的值，
值得一提的是 lower_bound 會得到在值大于等于查詢值的位置中，最小的一個，upper_bound 會得到值大于查詢值的位置中，最小的一個，他的前一個位置一定是值小于等于查詢值的位置中最大的，剛好滿足我們的需求，
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
#define Array vector<ll>
int nr, ng, nb;
ll ans;
ll p2(ll x){return x*x;}
void solve(Array a,Array b,Array c){
for(auto y:b){
auto px = upper_bound(a.begin(),a.end(),y);
auto pz = lower_bound(c.begin(),c.end(),y);
if(px==a.begin()||pz==c.end()) continue;
ll x = *(--px),z = *pz; //x<=y<=z 已經找到滿足式子的最與y接近的x,z
ll res = p2(x-y) + p2(y-z) + p2(x-z);
if(ans>res||ans==-1) ans = res;
}
}
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
//freopen("1.out","w",stdout);
int t;
while(cin>>t){
while(t--){
cin>>nr>>ng>>nb;
Array r(nr),g(ng),b(nb);
#define sortit(arr) sort(arr.begin(),arr.end())
fr(i,nr) cin>>r[i]; sortit(r);
fr(i,ng) cin>>g[i]; sortit(g);
fr(i,nb) cin>>b[i]; sortit(b);
ans = -1;
solve(r,g,b); solve(r,b,g);
solve(g,b,r); solve(g,r,b);
solve(b,r,g); solve(b,g,r);
cout<<ans<<endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198916.html
標籤：其他
下一篇：資料結構（嚴蔚敏版）思維導圖