Educational Codeforces Round 118 (Div. 2)
- A. Long Comparison
题目大意：\(Monocarp\)在一个黑板上写下了两个数。每一个数都用两个整数\(x,p\)表示，表示其值为\(x\)后有\(p\)个\(0\)。\(Monocarp\)想让你比较这两个数的大小。
思路：显然直接模拟会炸···
将两个数写成科学计数法：\(a=x_1+10^{p_1}\),\(b=x_2+10^{p_2}\)
直接比不好比较，采用取对数比较即可：\(log_{10}a=log_{10}x_1+p_1\),\(log_{10}b=log_{10}x_2+p_2\)，作差即可
Code:
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int t;
double x1,p1,x2,p2;
int main(){
cin>>t;
while(t--){
cin>>x1>>p1>>x2>>p2;
double ans;
ans=log10(x1/x2)+p1-p2;
if(ans==0) cout<<"="<<endl;
else if(ans>0) cout<<">"<<endl;
else cout<<"<"<<endl;
}
return 0;
}
- B. Absent Remainder
题目大意：给你一个长度为\(n\)的序列，请找\(\left\lfloor\dfrac{n}{2}\right\rfloor\)个不同的二元组\((x,y)\)(两个二元组不同满足\(x\)不同或\(y\)不同),满足以下性质：
- \(x\ !=y\)
- \(x\)和\(y\)均在序列中
- \(x\ mod\ y\)不在序列中
请输出这些二元组。若有多种答案，输出一种即可。
思路：由于\(x\ mod\ y<y\),因此我们选出序列中的最小值，那么 \(x\ mod\ y\)肯定不会出现在序列中，\(y\)依次从\(max\)往前取，最多取\(n-1 >= \left\lfloor\dfrac{n}{2}\right\rfloor\)，符合条件
Code:
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int t;
int n,a[N];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n/2;i++)cout<<a[n-i+1]<<" "<<a[1]<<endl;
}
return 0;
}
- C. Poisoned Dagger
题目大意：\(Monocarp\)要斩杀一头巨龙，巨龙的血量为\(h\)。\(Monocarp\)可以发动\(n\)次攻击，每次攻击发动于时间\(a_i\)，持续时间\(k\)秒，每持续\(1\)秒就会让巨龙的血量\(-1\)。如果两个攻击的间隔小于\(k\)，后一个攻击发动时会停止前一个攻击的效果。\(Monocarp\)想知道斩杀这头巨龙的\(k\)的最小值是多少。
思路：根据题意可以得到对于每个\(a_i\)持续的区间为\([a_i,min(a_{i+1}-1,a_i+k-1)]\)(注意对于\(a_n\),显然区间为\([a_n ,a_n+k]\))
\(n\)个区间求和得：$f(k)=\sum_{i=1}^{n-1}\bigl( min(a[i]+k-1,a[i+1]-1)-a[i]+1 \bigr)+k $
显然该柿子关于\(k\)具有单调性,因此套二分答案即可求出最小的\(k\)
Code:
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll n,h,a[N],t,ans;
ll check(ll mid){
ll tt=0;
for(int i=1;i<n;i++) tt+=min(a[i]+mid-1,a[i+1]-1)-a[i]+1;
tt+=mid;
return tt;
}
int main(){
cin>>t;
while(t--){
cin>>n>>h;
for(int i=1;i<=n;i++) cin>>a[i];
ll l=0,r=h+1;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)>=h){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<endl;
}
return 0;
}