2024年2月USACO计算机竞赛银牌题目解析！USACO竞赛公开赛什么时候？

2024年第三场USACO月赛已经结束，没有当场晋级的同学可以等待一周左右的时间。现在，让我们来看看2024年2月（第三场）USACO计算机竞赛银牌题目的解析。

USACO报名-免费领资料【翰林提供报名服务】【历年真题】

代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define int long long
struct re{
int X1,X2,Y1,Y2;
};
re ve[N];
int mx,mn,gg;
vector<int> v1,v2;
bool check1(vector<pair<int,int> > S, int x){
vector<int> v;
if (gg==-1){
v=v2;
} else v=v1;
vector<int> q;
for (auto v:S){
q.push_back(floor((long double)1.0*(v.second-x)/v.first));
}
sort(q.begin(),q.end());
sort(v.begin(),v.end());
for (int i=0;i<v.size();i++)
if (v[i]>q[i]) return 0;
return 1;
}
bool check2(vector<pair<int,int> > S, int x){
vector<int> v;
if (gg==-1){
v=v2;
} else v=v1;
vector<int> q;
for (auto v:S){
q.push_back(ceil((long double)1.0*(v.second-x)/v.first));
}
sort(q.begin(),q.end());
sort(v.begin(),v.end());
for (int i=0;i<v.size();i++)
if (v[i]<q[i]) return 0;
return 1;
}

void solve(vector<pair<int,int> > S,int g){
gg=g;
int h=-4e18,t=4e18;
while (h<t){
int mid=(h+t+1)/2;
if (check1(S,mid)) h=mid;
else t=mid-1;
}
mn=min(mn,h);
h=-4e18,t=4e18;
while (h<t){
int mid=(h+t)/2;
if (mid<0) mid=(h+t-1)/2;
if (check2(S,mid)) t=mid;
else h=mid+1;
}
mx=max(mx,h);
}
signed main(){
ios::sync_with_stdio(false);
int T;
cin>>T;
while (T--){
int n,X1,Y1,Y2,X2;
cin>>n>>X1;
vector<pair<int,int> > S1,S2;
vector<int> jl;
for (int i=1;i<=n;i++){
cin>>Y1>>Y2>>X2;
jl.push_back(Y1); jl.push_back(Y2);
S1.push_back({X2,Y2});
S2.push_back({X2,Y1});
}
v1.clear(); v2.clear();
vector<int> ss;
for (int i=1;i<=4*n;i++){
int x;
cin>>x;
ss.push_back(abs(x));
if (x>0) v1.push_back(x);
else v2.push_back(x);
}
if (v1.size()<n||v2.size()<n){
cout<<-1<<endl;
continue;
}
int k=v1.size()-n;
sort(jl.begin(),jl.end());
reverse(jl.begin(),jl.end());
for (int i=0;i<k;i++)
S2.push_back({X1,jl[i]});
for (int i=k;i<jl.size();i++)
S1.push_back({X1,jl[i]});
mn=1e18;
mx=0;
sort(ss.begin(),ss.end());
// if (ss[0]==ss.back()){
// for (auto v:S1){
// mn=min(mn,-v.first*(-ss[0])+v.second);
// mx=max(mx,-v.first*(-ss[0])+v.second);
// }
// for (auto v:S2){
// mn=min(mn,-v.first*(ss[0])+v.second);
// mx=max(mx,-v.first*(ss[0])+v.second);
// }
// } else{
solve(S1,-1);
solve(S2,1);
// }
cout<<mx-mn<<endl;
}
return 0;
}

USACO计算机竞赛月赛时间表

如果在本场银组月赛中顺利晋级，参赛者将有机会参加下一场月赛的黄金组别。黄金组别的考试难度大致相当于大学计算机专业算法课程水平，因此参赛者需要具备一定的算法基础，理解一些抽象方法（例如：最短路径，动态规划），并且对数据结构有比较深入的了解。

如果在本场月赛中未能晋级，参赛者可以等待结果公布后参加下一场月赛。一般来说，高于750分或800分的分数通常可以获得晋级资格。