USACO 2021 DEC Platinum 試題解析

前兩天，USACO 又火了一把！起因是 USACO 12 月月賽排行榜被中國(guó)選手霸占，中國(guó)選手猛增！USACO 真的值得中國(guó)選手參加嗎？美國(guó)的信學(xué)術(shù)活動(dòng)為何會(huì)讓中國(guó)選手紛紛參賽？今天就USACO 2021 DEC Platinum 試題進(jìn)行解析：

USACO 21DEC PlatinumT1 Ticket

題目難度：USACO P/省選

先想暴力做法。注意到一個(gè)人不會(huì)重復(fù)買(mǎi)票，所以我們可以把每種票看作虛擬節(jié)點(diǎn)，買(mǎi)票看作從??到??號(hào)票邊權(quán)為??的邊，同時(shí)??號(hào)票向區(qū)間??中的所有點(diǎn)連邊權(quán)為??的邊。題目希望求出每個(gè)點(diǎn)到達(dá)??和??所需的最小代價(jià)，不妨建反圖以??和??為原點(diǎn)分別跑一遍最短路。

然而這樣會(huì)喜提 WA 。因?yàn)槿匀粵](méi)有解決重復(fù)買(mǎi)票的問(wèn)題，兩條最短路的交集中的所有邊被算了兩遍。怎么解決？先記當(dāng)前答案為??，若節(jié)點(diǎn)??的兩條最短路均經(jīng)過(guò)它的鄰居??，不難發(fā)現(xiàn)??。這和單源最短路的松弛本質(zhì)相同，我們對(duì)答案數(shù)組重新跑一遍最短路即可。

時(shí)間復(fù)雜度：下面提供兩種優(yōu)化的思路，第一種是考場(chǎng)第一眼看出的線段樹(shù)優(yōu)化建圖，具體知識(shí)可以參考這個(gè)博客?DS優(yōu)化建圖?。對(duì)區(qū)間中的每個(gè)點(diǎn)暴力連邊是不好的！我們用線段樹(shù)建圖的方式連邊，時(shí)間復(fù)雜度為??。USACO評(píng)測(cè)機(jī)或洛谷開(kāi) O2 均可通過(guò)本題。#include?<bits/stdc++.h>
#define?rep(i,a,b)?for(int?i=(a);i<=(b);++i)
#define?ll?long?long
using?namespace?std;
inline?ll?read(){
ll?x=0,f=1;char?ch=getchar();
while?(!isdigit(ch)){if?(ch=='-')?f=-1;ch=getchar();}
while?(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return?x*f;
}
const?int?N=1e6+5,M=7e6+5;
const?ll?inf=1e16;
int?head[N],cnt;
struct?Edge{
int?to,nxt,w;
}e[M];
inline?void?add(int?u,int?v,int?w){e[++cnt]={v,head[u],w};head[u]=cnt;}
int?n,q,s;
struct?Node{int?l,r;}t[N];
#define?ls?(p<<1)
#define?rs?(ls|1)
inline?void?build(int?p,int?l,int?r){
t[p].l=l,t[p].r=r;
if(l==r){//葉子節(jié)點(diǎn)與原圖加邊
add(l+8*n,p,0);add(p+4*n,l+8*n,0);
add(p,l+8*n,0);add(l+8*n,p+4*n,0);
return;
}
//向兒子連邊
add(p,ls,0);add((ls)+4*n,p+4*n,0);
add(p,rs,0);add((rs)+4*n,p+4*n,0);
int?mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
inline?void?upd(int?p,int?L,int?R,int?u,int?w){
int?l=t[p].l,r=t[p].r,mid=(l+r)>>1;
if(l==L&&r==R){//當(dāng)前節(jié)點(diǎn)覆蓋區(qū)間
add(p+4*n,u+8*n,w);
return;
}
if(R<=mid)upd(ls,L,R,u,w);
else?if(L>mid)upd(rs,L,R,u,w);
else{
upd(ls,L,mid,u,w);upd(rs,mid+1,R,u,w);
}
}
ll?dis[N],d[N];
struct?node{
ll?dis;int?pos;
bool?operator?<(?const?node?&x?)const{
return?x.dis?<?dis;
}
};
bool?vis[N];
priority_queue?<node>?pq;
inline?void?dijkstra(bool?op=0){
if(!op){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;pq.push({0,s});
}else{
rep(i,1,9*n+q)pq.push({dis[i],i});
}
memset(vis,0,sizeof(vis));
while(!pq.empty()){
node?tmp=pq.top();pq.pop();
int?x=tmp.pos;
if(vis[x])continue;
vis[x]=1;
for(int?i=head[x];i;i=e[i].nxt){
int?y=e[i].to;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
pq.push({dis[y],y});
}
}
}
}
int?main(){
n=read(),q=read();
build(1,1,n);
rep(i,1,q){
int?a=read(),w=read(),b=read(),c=read();
upd(1,b,c,i+n,0);
add(9*n+i,a+8*n,w);
}
s=8*n+1;
dijkstra();
memcpy(d,dis,sizeof(d));
//rep(i,1,n)cout<<dis[i+8*n]<<'?';
s=9*n;
dijkstra();
rep(i,1,9*n+q)dis[i]+=d[i];
dijkstra(1);
rep(i,1,n){
if(dis[i+8*n]>inf)puts("-1");
else?printf("%lldn",dis[i+8*n]);
}
return?0;
}
如何優(yōu)化？考慮 dijkstra 時(shí)實(shí)際上在做什么。原圖中的節(jié)點(diǎn)會(huì)影響將它包含的票的虛擬節(jié)點(diǎn)，然后這個(gè)虛擬節(jié)點(diǎn)僅影響其所對(duì)應(yīng)的一個(gè)原圖節(jié)點(diǎn)??。其次，我們知道堆優(yōu)化 dijkstra 后每個(gè)票僅會(huì)被更新一次。于是并不需要建出圖，在線段樹(shù)上轉(zhuǎn)移并且對(duì)更新完的區(qū)間打上標(biāo)記就可以做到??（代碼咕咕咕）。

第二種做法來(lái)自 Benq 的題解。同樣利用上面的性質(zhì)，對(duì)所有票按左端點(diǎn)升序排列，注意到每個(gè)門(mén)票最多入隊(duì)一次，建一棵勢(shì)能線段樹(shù)維護(hù)一段區(qū)間的所有票右端點(diǎn)的最大值即可。在每個(gè)票入隊(duì)后打上標(biāo)記，均攤分析可以得出復(fù)雜度為??。目前在洛谷上是最優(yōu)解。
時(shí)間復(fù)雜度：
#include?<bits/stdc++.h>
#define?rep(i,a,b)?for(int?i=(a);i<=(b);++i)
#define?per(i,a,b)?for(int?i=(a);i>=(b);--i)
#define?pii?pair<int,int>
#define?vi?vector<int>
#define?fi?first
#define?se?second
#define?pb?push_back
#define?ALL(x)?x.begin(),x.end()
#define?sz(x)?int(x.size())
#define?ll?long?long
using?namespace?std;
inline?ll?read(){
ll?x=0,f=1;char?ch=getchar();
while?(!isdigit(ch)){if?(ch=='-')?f=-1;ch=getchar();}
while?(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return?x*f;
}
const?int?N=2e5+5;
const?ll?inf?=?1e18;
struct?ticket{int?c,p,a,b;};
bool?cmp(ticket?x,ticket?y){return?x.a<y.a;}
struct?SegTree{
int?n,sz;
vector?<int>?mx;
vector?<ticket>?tickets;
#define?ls?(p<<1)
#define?rs?(ls|1)
void?pushup(int?p){mx[p]=max(mx[ls],mx[rs]);}
SegTree(vector?<ticket>?tickets)?:?tickets(tickets){//初始化
n?=?1;
sz?=?sz(tickets);
while(n?<?sz)n<<=1;
mx.assign(2*n,0);
rep(i,0,n-1){
if(i?<?sz){
mx[i+n]?=?tickets[i].b;
}else?mx[i+n]?=?-1;
}
per(i,n-1,1)pushup(i);
}
//找到所有可能轉(zhuǎn)移的門(mén)票并移除
void?remove(vector?<int>?&v,int?x,int?p=1,int?L=0,int?R=-1){
if(R==-1)R+=n;
if(L>=sz||tickets[L].a>x||mx[p]<x)return;
if(L==R){
mx[p]?=?-1;
v.pb(L);
return;
}
int?mid?=?(L+R)>>1;
remove(v,x,ls,L,mid),remove(v,x,rs,mid+1,R);
pushup(p);
}
};
void?Min(ll?&a,const?ll?b){if(a>b)a=b;}
int?main(){
int?n=read(),k=read();
vector?<ticket>?tickets(k);
for(auto?&t:?tickets){
t.c=read()-1,t.p=read(),t.a=read()-1,t.b=read()-1;
}
sort(ALL(tickets),cmp);
auto?Dij?=?[&](vector<ll>?&dis){//Dijkstra
priority_queue?<pair<ll,int>>?pq;
rep(i,0,k-1){
Min(dis[tickets[i].c],dis[i+n]+tickets[i].p);
}
rep(i,0,n-1){
if(dis[i]<inf)pq.push({-dis[i],i});
}
SegTree?seg(tickets);
while(!pq.empty()){
pii?x?=?pq.top();
pq.pop();
if(-x.fi>dis[x.se])continue;
vector?<int>?vec;
seg.remove(vec,x.se);//找到轉(zhuǎn)移的門(mén)票
for(int?t?:?vec){
if(dis[t+n]?>?dis[x.se]){
dis[t+n]?=?dis[x.se];
if(dis[tickets[t].c]?>?dis[x.se]?+?tickets[t].p){
dis[tickets[t].c]?=?dis[x.se]?+?tickets[t].p;
pq.push({-dis[tickets[t].c],tickets[t].c});
}
}
}
}
};
//三次最短路
vector?<ll>?L(n+k,inf),R(n+k,inf),dis(n+k);
L[0]=0,R[n-1]=0;
Dij(L),Dij(R);
rep(i,0,n+k-1)dis[i]?=?L[i]?+?R[i];
Dij(dis);
rep(i,0,n-1){
if(dis[i]<inf)printf("%lldn",dis[i]);
else?puts("-1");
}
return?0;
}
T2 Paired Up題目難度：USACO P+/NOI-

子任務(wù) 1：
設(shè)為當(dāng)前考慮到第頭H牛，第頭G牛時(shí)匹配的牛的最大權(quán)值和。那么我們可以選擇不匹配??，不匹配??，或者是將和匹配。
時(shí)間復(fù)雜度：
#define?rep(i,a,b)?for(int?i=(a);i<=(b);++i)
#define?pii?pair<int,int>
#define?vi?vector<int>
int?main(){
T=read(),n=read(),K=read();
vector?<pii>?cow[2];
cow[0].pb({0,0}),cow[1].pb({0,0});
rep(i,1,n){
cin>>c;
int?x=read(),y=read();
cow[c=='H'].pb({x,y});
sum+=y;
}
A=sz(cow[0]),B=sz(cow[1]);
if(T==1){
vector?<vi>?dp(A+1,vi(B+1));
rep(i,1,A)rep(j,1,B){
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(abs(cow[0][i].x-cow[1][j].x)<=K)
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+cow[0][i].y+cow[1][j].y);
}
printf("%dn",sum-dp[A][B]);
}
}
子任務(wù) 2：
對(duì)于最大化未匹配的權(quán)值和，我們考慮使用類(lèi)似的 dp 狀態(tài)。但是注意到在上述轉(zhuǎn)移時(shí)，有時(shí)候我們考慮的并不是最大匹配，只是因?yàn)樽顑?yōu)解只產(chǎn)生于最大匹配（若不是最大匹配，多匹配兩頭牛顯然更優(yōu)），我們才能得到??時(shí)的答案。
于是我們需要把最大匹配這一限制加入我們的 dp 狀態(tài)，具體地，我們加入一維??表示最后一頭未匹配的牛，假設(shè)我們不想匹配當(dāng)前的 H 牛，那么牛??必須滿足如下條件之一：牛的品種是牛與當(dāng)前牛的距離大于 狀態(tài)量是??，每次轉(zhuǎn)移還是的，足夠通過(guò)該子任務(wù)。

時(shí)間復(fù)雜度：
vector?<vector<vi>>?dp(A+1,vector<vi>(B+1,vi(n+1,-1)));
dp[0][0][n]=0;
rep(i,0,A)rep(j,0,B)rep(k,0,n){
if(dp[i][j][k]==-1)continue;
if(i<A&&j<B&&abs(cow[0][i].x-cow[1][j].x)<=K)
Max(dp[i+1][j+1][k],dp[i][j][k]);
if(i<A&&(!(A<=k&&k<n&&cow[0][i].x<=cow[1][k-A].x+K)))
Max(dp[i+1][j][i],dp[i][j][k]+cow[0][i].y);
if(j<B&&(!(k<A&&cow[1][j].x<=cow[0][k].x+K)))
Max(dp[i][j+1][A+j],dp[i][j][k]+cow[1][j].y);
}
int?ans?=?0;
rep(i,0,n)Max(ans,dp[A][B][i]);
printf("%dn",ans);
子任務(wù) 3：
考慮最終的優(yōu)化，?兩維比較難舍去，但我們可以修改最后一維的定義。定義??為處理到前??頭 H 牛，??頭 G 牛，并且欽定下一種不放入匹配的牛的品種為??。有轉(zhuǎn)移：
當(dāng)然我們也可以轉(zhuǎn)換欽定的品種：如果之前我們被強(qiáng)制不選 H 牛，那么最后一個(gè)未匹配的 H 牛最多是第?個(gè)。能不放入匹配的 G 牛需要離該牛距離至少為??，且在該牛之前的所有牛都要放入匹配。預(yù)處理出對(duì)于所有??，滿足條件的 G 牛編號(hào)的最小值，并且判斷這段區(qū)間的牛是否能全部匹配即可。

時(shí)間復(fù)雜度：
per(i,A,1)per(j,B,1){
if(chk(i,j))lst[i][j]=lst[i+1][j+1]+1;
else?lst[i][j]=0;
}
int?j=1;
rep(i,1,A){
while(j<=B&&(chk(i,j)||G[j].x<H[i].x))j++;
nxtH[i]?=?j;
}
j=1;
rep(i,1,B){
while(j<=A&&(chk(j,i)||H[j].x<G[i].x))j++;
nxtG[i]?=?j;
}
memset(f,-0x3f,sizeof(f));
memset(g,-0x3f,sizeof(g));
nxtG[0]?=?nxtH[0]?=?1;
f[0][0]?=?g[0][0]?=?0;
rep(i,0,A)rep(j,0,B){
int?cnt?=?max(nxtH[i]-j-1,0);
if(i+cnt<=A?&&?lst[i+1][j+1]>=cnt)
Max(g[i+cnt][j+cnt],f[i][j]);
cnt?=?max(nxtG[j]-i-1,0);
if(j+cnt<=B?&&?lst[i+1][j+1]>=cnt)
Max(f[i+cnt][j+cnt],g[i][j]);
if(i<A?&&?j<B?&&?chk(i+1,j+1)){
Max(f[i+1][j+1],f[i][j]);
Max(g[i+1][j+1],g[i][j]);
}
if(i<A)?Max(f[i+1][j],f[i][j]+H[i+1].y);
if(j<B)?Max(g[i][j+1],g[i][j]+G[j+1].y);
}
printf("%dn",max(f[A][B],g[A][B]));


USACO 作為一個(gè)國(guó)際性比賽，還是很值得大家去練練手的。如果你也想報(bào)名 USACO，想在 USACO 學(xué)術(shù)活動(dòng)中獲得一個(gè)不錯(cuò)的成績(jī)，可以掃碼咨詢【免費(fèi)獲取】學(xué)術(shù)活動(dòng)備考資料大禮包，不定期名師講座等你來(lái)~