USACO 21DEC Platinum 題解

USACO 21DEC Platinum
T1 Ticket
題目難度：USACO P/省選
先想暴力做法。注意到一個(ge) 人不會(hui) 重複買(mai) 票，所以我們(men) 可以把每種票看作虛擬節點，買(mai) 票看作從(cong)   到  號票邊權為(wei)   的邊，同時  號票向區間  中的所有點連邊權為(wei)   的邊。題目希望求出每個(ge) 點到達  和  所需的最小代價(jia) ，不妨建反圖以  和  為(wei) 原點分別跑一遍最短路。
然而這樣會(hui) 喜提 WA 。因為(wei) 仍然沒有解決(jue) 重複買(mai) 票的問題，兩(liang) 條最短路的交集中的所有邊被算了兩(liang) 遍。怎麽(me) 解決(jue) ？先記當前答案為(wei)   ，若節點  的兩(liang) 條最短路均經過它的鄰居  ，不難發現  。這和單源最短路的鬆弛本質相同，我們(men) 對答案數組重新跑一遍最短路即可。
時間複雜度：
下麵提供兩(liang) 種優(you) 化的思路，第一種是考場第一眼看出的線段樹優(you) 化建圖，具體(ti) 知識可以參考這個(ge) 博客 DS優(you) 化建圖。
對區間中的每個(ge) 點暴力連邊是不好的！我們(men) 用線段樹建圖的方式連邊，時間複雜度為(wei)   。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){//葉子節點與(yu) 原圖加邊 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; } //向兒(er) 子連邊 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; }如何優(you) 化？考慮 dijkstra 時實際上在做什麽(me) 。原圖中的節點會(hui) 影響將它包含的票的虛擬節點，然後這個(ge) 虛擬節點僅(jin) 影響其所對應的一個(ge) 原圖節點  。其次，我們(men) 知道堆優(you) 化 dijkstra 後每個(ge) 票僅(jin) 會(hui) 被更新一次。於(yu) 是並不需要建出圖，在線段樹上轉移並且對更新完的區間打上標記就可以做到  （代碼咕咕咕）。
第二種做法來自 Benq 的題解。同樣利用上麵的性質，對所有票按左端點升序排列，注意到每個(ge) 門票最多入隊一次，建一棵勢能線段樹維護一段區間的所有票右端點的最大值即可。在每個(ge) 票入隊後打上標記，均攤分析可以得出複雜度為(wei)   。目前在洛穀上是最優(you) 解。
時間複雜度：
#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：
設  為(wei) 當前考慮到第  頭 H 牛，第  頭 G 牛時匹配的牛的最大權值和。那麽(me) 我們(men) 可以選擇不匹配  ，不匹配  ，或者是將  和  匹配。
時間複雜度：
#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：
對於(yu) 最大化未匹配的權值和，我們(men) 考慮使用類似的 dp 狀態。但是注意到在上述轉移時，有時候我們(men) 考慮的並不是最大匹配，隻是因為(wei) 最優(you) 解隻產(chan) 生於(yu) 最大匹配（若不是最大匹配，多匹配兩(liang) 頭牛顯然更優(you) ），我們(men) 才能得到  時的答案。
於(yu) 是我們(men) 需要把最大匹配這一限製加入我們(men) 的 dp 狀態，具體(ti) 地，我們(men) 加入一維  表示最後一頭未匹配的牛，假設我們(men) 不想匹配當前的 H 牛，那麽(me) 牛  必須滿足如下條件之一：
牛  的品種是牛  與(yu) 當前牛的距離大於(yu) 狀態量是  ，每次轉移還是  的，足夠通過該子任務。
時間複雜度：
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：
考慮最終的優(you) 化，兩(liang) 維比較難舍去，但我們(men) 可以修改最後一維的定義(yi) 。定義(yi)   為(wei) 處理到前  頭 H 牛，  頭 G 牛，並且欽定下一種不放入匹配的牛的品種為(wei)   。有轉移：
當然我們(men) 也可以轉換欽定的品種：如果之前我們(men) 被強製不選 H 牛，那麽(me) 最後一個(ge) 未匹配的 H 牛最多是第個(ge) 。能不放入匹配的 G 牛需要離該牛距離至少為(wei)   ，且在該牛之前的所有牛都要放入匹配。預處理出對於(yu) 所有  ，滿足條件的 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]));T3 HILO題目難度：USACO P/省選-
不難發現猜 HI 的數不會(hui) 使猜 LO 的數被跳過。設  ，那麽(me) 原題相當於(yu) 將  和  排列，隻記錄  的每次下標最大值的出現位置，求期望  的數量。
這可以 dp ，設  為(wei) 當前最大出現  以及最後一個(ge) 出現的是  ，通過簡單的轉移可以做到  。前綴和優(you) 化可以做到  ，這裏不再贅述。
比較吸引我的是在賽後討論中看到的  做法，這裏簡單的證明一下。
結論：令  . 有
證明：
或  時結論顯然成立，不妨對  歸納。即證  後期望的變化為(wei) ：
計算對  的排列中插入  對答案的貢獻，  隻能排在第一個(ge) 出現的  之前，否則會(hui) 被跳過。個(ge)   將  個(ge)   分成  段，故第一個(ge)   前  的期望個(ge) 數為(wei)   個(ge) 。設前麵有  個(ge)   。
接下來，隻要  被插入在  個(ge)   中最大的  前麵，都會(hui) 對期望貢獻一個(ge) "ba" 。最大的  的期望位置為(wei) ：
即為(wei) 原排列首項是  的概率，為(wei)   。能得出：
const int N=2e5+5,P=1e9+7; int n,x; ll H[N],inv[N]; int main(){ n=read(),x=read(); inv[1]=1; ll fac = 1; rep(i,2,n){ inv[i]=(P-P/i)*inv[P%i]%P; fac = fac*i%P; } rep(i,1,n)H[i]=(H[i-1]+inv[i])%P; int y = n-x; cout<<(fac*inv[2]%P*(inv[n]*y%P+H[x]+H[y]-H[n])%P+P)%P; return 0; }