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分的分數通常可以獲得晉級資格。