ABC赛后总结
2026-05-31 17:42:05
发布于：上海
5阅读
0回复
0点赞
拉完了。
Two Rings
昨晚打比赛被B题创飞了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;
cin>>t;
while(t--){
ll x1,y1,r1,x2,y2,r2;
cin>>x1>>y1>>r1>>x2>>y2>>r2;
ll d=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
ll l=abs(r1-r2)*abs(r1-r2);
ll r=(r1+r2)*(r1+r2);
if(l<=d&&d<=r)cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
这个数学结论。你要是不知道的话这题可能会过不了。
这个题让我想到了2024CSP-S第一题：决斗。一个比较好想的贪心。
第一眼的感觉是：将A数组和B数组做一个排序，然后遍历A数组，去在B数组中找小于它重量两倍的最大值。
然后会超时。
我赛时的优化是：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N];
bool vis[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int ans=0;
int now=n;
for(int i=n;i>=1;i--){
if(now==0)break;
int sum=upper_bound(b+1,b+1+m,2*a[i])-b-1;
if(sum==0)break;
if(sum<=now)now=sum-1,ans++;
else if(sum>now)now--,ans++;
}
cout<<ans;
return 0;
}
果然人不能共情过去的自己。我现在第一眼看不出我当时在写啥。
这里空空如也
有帮助，赞一个