發(fā)布時(shí)間:2024-02-23 09:34:19 編輯:Lisa來(lái)源:未知
一起來(lái)看看本次月賽銀牌試題解析代碼+視頻吧!
- X-NEW-
USACO 2024年2月銀牌第一題
#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 2024年2月銀牌第二題
題解視頻分析:
代碼:
#include <bits/stdc++.h>
#define endl " "
using namespace std;
string s1,s2;
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int T;
cin>>T;
while (T--){
int n,m;
cin>>n>>m;
cin>>s1>>s2;
vector<pair<int,int> > ans;
vector<int> v1,v2;
int t3=0;
for (int i=0;i<n;i++)
if (i==0||s1[i]!=s1[i-1]) v1.push_back(s1[i]-'0');
for (int i=0;i<n;i++)
if (i==0||s2[i]!=s2[i-1]) v2.push_back(s2[i]-'0');
bool tt=0;
if (v2[0]==v1.back()){
tt=1;
swap(v1,v2);
}
if (v1.size()==1){
tt^=1;
swap(v1,v2);
}
// if (v1.size()<v2.size()) {
// tt=1;
// swap(v1,v2);
// }
int k=v2.back();
if (!(v1[0]==v2.back()||(v2.size()==1))){
k=3-k;
ans.push_back({2,3});
v2.pop_back();
}
reverse(v1.begin(),v1.end());
for (auto v:v1){
if (v==k){
ans.push_back({1,2});
} else{
ans.push_back({1,3});
t3++;
}
}
if (v2.size()==1){
if (ans.back().second==3) {
ans.pop_back(); t3--;
}
if (t3>0) ans.push_back({3,1});
} else{
if (ans.back().second==2){
ans.pop_back();
}
reverse(v2.begin(),v2.end());
for (auto v:v2)
if (v==k) {
ans.push_back({2,1});
} else{
ans.push_back({2,3});
}
if (ans.back().second==3){
ans.pop_back();
}
ans.push_back({3,2});
}
cout<<ans.size()<<endl;
if (m==1) continue;
for (auto &v:ans){
if (tt){
if (v.first<=2) v.first=3-v.first;
if (v.second<=2) v.second=3-v.second;
}
cout<<v.first<<" "<<v.second<<endl;
}
}
return 0;
}
/*
4
3 2
121
212
*/
USACO 2024年2月銀牌第三題
題解視頻分析:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6;
int f[N],g[N],h[N];
int n,m,k,a[N][6];
signed main(){
ios::sync_with_stdio(false);
int T;
cin>>T;
while (T--){
cin>>n>>m>>k;
for (int i=1;i<=m;i++)
for (int j=1;j<=k;j++)
cin>>a[i][j];
for (int i=1;i<=m;i++){
int ans=0;
int mn=1e9;
for (int j=1;j<=k;j++) mn=min(mn,a[i][j]);
for (int j=1;j<=k;j++)
ans+=a[i][j]%2;
if (ans==k||ans==0){
f[i]=mn;
} else {
int mx[2]={0,0};
for (int j=1;j<=k;j++)
mx[a[i][j]%2]=max(mx[a[i][j]%2],a[i][j]);
f[i]=-min(mx[0],mx[1]);
}
h[i]=f[i];
f[i]+=f[i-1];
}
g[m+1]=f[m];
for (int i=m;i>=1;i--){
g[i]=min(g[i+1],f[i]);
}
if (g[1]+n<=0){
cout<<-1<<endl;
continue;
}
vector<int> v;
for (int i=1;i<=m;i++){
int mx=0;
for (int j=1;j<=k;j++)
if (a[i][j]%2==1) mx=max(mx,a[i][j]);
mx=-mx;
if (mx==0) mx=h[i];
if (mx+n+min(0ll,g[i+1]-f[i])<=0) {
v.push_back(1);
n+=h[i];
} else{
v.push_back(0);
n+=mx;
}
}
for (int i=0;i<v.size();i++){
if (v[i]==0) cout<<"Even";
else cout<<"Odd";
if (i+1!=v.size()) cout<<" ";
}
cout<<endl;
}
return 0;
}
想要競(jìng)賽沖獎(jiǎng),除了實(shí)力非常強(qiáng)悍的同學(xué)來(lái)說(shuō),其他都是需要有充足準(zhǔn)備的,起碼要求是要上750分才是穩(wěn)穩(wěn)的。因?yàn)閁SACO競(jìng)賽的難度逐級(jí)越來(lái)越大,專業(yè)備考可以幫助選手節(jié)省時(shí)間的同時(shí),更有機(jī)會(huì)沖擊更高獎(jiǎng)項(xiàng)!
在此次2023年比賽中,犀牛學(xué)子斬獲了重磅獎(jiǎng)項(xiàng)和高分戰(zhàn)績(jī)。恭喜以下32位犀牛優(yōu)秀學(xué)子!
32位學(xué)員
滿分晉級(jí)
(犀牛學(xué)子晉級(jí)喜報(bào)公示)
犀牛USACO競(jìng)賽培訓(xùn)班課,由犀牛金牌導(dǎo)師親授,根據(jù)USACO考察方向及評(píng)分標(biāo)準(zhǔn),提供詳細(xì)科學(xué)參賽指導(dǎo)及學(xué)習(xí)指導(dǎo)幫助。
對(duì)于USACO的課程體系,經(jīng)過(guò)不斷的研究,以及對(duì)于?百名學(xué)?的學(xué)習(xí)能?分析,犀牛計(jì)算機(jī)教研團(tuán)隊(duì)最終總結(jié)出了?套lecture + lab的課程體系?案。即知識(shí)點(diǎn)授課+ 習(xí)題課教學(xué)體系,這是?前很多美國(guó)主流?學(xué)都在?的教育體系,我們經(jīng)過(guò)改良優(yōu) 化這種體系來(lái)?效備戰(zhàn)USACO考試。
精品小班、一對(duì)一等多種班型可供選擇,線下+線上同步授課,上海、北京、南京、蘇州、無(wú)錫、深圳、重慶等地都設(shè)有校區(qū),詳細(xì)課程內(nèi)容可咨詢網(wǎng)站客服了解~
微信咨詢