USACO 2021 DEC Platinum 试题解析

前两天,USACO 又火了一把!起因是 USACO 12 月月赛排行榜被中国选手霸占,中国选手猛增!USACO 真的值得中国选手参加吗?美国的信竞赛为何会让中国选手纷纷参赛?今天就USACO 2021 DEC Platinum 试题进行解析:

USACO 21DEC PlatinumT1 Ticket

题目难度:USACO P/省选

先想暴力做法。注意到一个人不会重复买票,所以我们可以把每种票看作虚拟节点,买票看作从  到  号票边权为  的边,同时  号票向区间  中的所有点连边权为  的边。题目希望求出每个点到达  和  所需的最小代价,不妨建反图以  和  为原点分别跑一遍最短路。

然而这样会喜提 WA 。因为仍然没有解决重复买票的问题,两条最短路的交集中的所有边被算了两遍。怎么解决?先记当前答案为  ,若节点  的两条最短路均经过它的邻居  ,不难发现  。这和单源最短路的松弛本质相同,我们对答案数组重新跑一遍最短路即可。

时间复杂度:下面提供两种优化的思路,第一种是考场第一眼看出的线段树优化建图,具体知识可以参考这个博客 DS优化建图 。对区间中的每个点暴力连边是不好的!我们用线段树建图的方式连边,时间复杂度为  。USACO评测机或洛谷开 O2 均可通过本题。#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){//叶子节点与原图加边
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){//当前节点覆盖区间
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;
}
如何优化?考虑 dijkstra 时实际上在做什么。原图中的节点会影响将它包含的票的虚拟节点,然后这个虚拟节点仅影响其所对应的一个原图节点  。其次,我们知道堆优化 dijkstra 后每个票仅会被更新一次。于是并不需要建出图,在线段树上转移并且对更新完的区间打上标记就可以做到  (代码咕咕咕)。

第二种做法来自 Benq 的题解。同样利用上面的性质,对所有票按左端点升序排列,注意到每个门票最多入队一次,建一棵势能线段树维护一段区间的所有票右端点的最大值即可。在每个票入队后打上标记,均摊分析可以得出复杂度为  。目前在洛谷上是最优解。
时间复杂度:
#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);
}
//找到所有可能转移的门票并移除
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);//找到转移的门票
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-

子任务 1:
设为当前考虑到第头H牛,第头G牛时匹配的牛的最大权值和。那么我们可以选择不匹配  ,不匹配  ,或者是将和匹配。
时间复杂度:
#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]);
}
}
子任务 2:
对于最大化未匹配的权值和,我们考虑使用类似的 dp 状态。但是注意到在上述转移时,有时候我们考虑的并不是最大匹配,只是因为最优解只产生于最大匹配(若不是最大匹配,多匹配两头牛显然更优),我们才能得到  时的答案。
于是我们需要把最大匹配这一限制加入我们的 dp 状态,具体地,我们加入一维  表示最后一头未匹配的牛,假设我们不想匹配当前的 H 牛,那么牛  必须满足如下条件之一:牛的品种是牛与当前牛的距离大于 状态量是  ,每次转移还是的,足够通过该子任务。

时间复杂度:
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);
子任务 3:
考虑最终的优化, 两维比较难舍去,但我们可以修改最后一维的定义。定义  为处理到前  头 H 牛,  头 G 牛,并且钦定下一种不放入匹配的牛的品种为  。有转移:
当然我们也可以转换钦定的品种:如果之前我们被强制不选 H 牛,那么最后一个未匹配的 H 牛最多是第 个。能不放入匹配的 G 牛需要离该牛距离至少为  ,且在该牛之前的所有牛都要放入匹配。预处理出对于所有  ,满足条件的 G 牛编号的最小值,并且判断这段区间的牛是否能全部匹配即可。

时间复杂度:
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 作为一个国际性比赛,还是很值得大家去练练手的。如果你也想报名 USACO,想在 USACO 竞赛中获得一个不错的成绩,可以扫码咨询【免费获取】竞赛备考资料大礼包,不定期名师讲座等你来~

翰林国际教育资讯二维码