USACO 22JAN Platinum 题解

文章目录[隐藏]

赛时爆炸了，很多平常熟悉的套路都没想起来，但题目还是要补的不是吗？

T1

题意：给一个长度为的数组，若相邻两数之差的绝对值不超过则可以交换，问能得到的所有中字典序最小的一个。

数据范围：

发现的数无法交换，于是找到所有这样的限制做拓扑排序。如何做？正常最小拓扑序是把所有入度为0的点放入优先队列中，然后每次取堆顶的点并从图中删除。时间复杂度为。

思考一下如何优化，首先可以对原数组离散化，用一个线段树来维护当前可能的最小位置，每次取出作为答案并更新与其有连边的点的入度即可。具体地，若当前点的权值为，则中的所有权值对应的点的入度。需要一个带懒标记线段树做区间更新。

时间复杂度：

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#definedebug(...) fprintf(stderr, __VA_ARGS__)#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;inlinellread(){ ll x=0,f=1;charch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}returnx*f; }constintN=2e5+5;intn,K,a[N],val[N],deg[N];unordered_map<int,int> vis;#definels (p<<1)#definers (ls|1)#definemid ((L+R)>>1)pii t[N<<2];inttag[N<<2];inlinepiiMin(constpii a,constpii b){if(a.se == b.se)returnmake_pair(min(a.fi,b.fi),a.se);returna.se < b.se ? a : b; }voidbuild(intp,intL,intR){if(L == R){ t[p] = make_pair(L,deg[L]);return; } build(ls,L,mid),build(rs,mid+1,R); t[p] = Min(t[ls],t[rs]); }voidpush(intp,intv){tag[p] += v,t[p].se += v;}voiddown(intp){if(!tag[p])return; push(ls,tag[p]),push(rs,tag[p]); tag[p] =0; }voidupd(intp,intL,intR,intl,intr,intv){if(l > R || r < L)return;if(l <= L && R <= r){ push(p,v);return; } down(p); upd(ls,L,mid,l,r,v),upd(rs,mid+1,R,l,r,v); t[p] = Min(t[ls],t[rs]); }intT[N];voidadd(intx){for(;x <= n;x += x & -x)T[x]++;}intQ(intx){intres =0;for(;x;x -= x & -x)res += T[x];returnres; }intmain(){ n = read(),K = read(); rep(i,1,n)a[i] = read(),val[i] = a[i]; sort(val+1,val+n+1); rep(i,1,n){ vis[a[i]]++; a[i] = lower_bound(val+1,val+n+1,a[i]) - val + vis[a[i]] -1; }//calculating in-degreerep(i,1,n){intx = lower_bound(val+1,val+n+1,val[a[i]]-K) - val -1;inty = lower_bound(val+1,val+n+1,val[a[i]]+K+1) - val -1; deg[a[i]] = (i-1) + Q(x) - Q(y); add(a[i]); } build(1,1,n); rep(i,1,n){intu = t[1].fi;cout<< val[u] <<'n';intx = lower_bound(val+1,val+n+1,val[u]-K) - val -1;//cout << 1 << ' ' << x << 'n';inty = lower_bound(val+1,val+n+1,val[u]+K+1) - val -1;//cout << y+1 << ' ' << n << 'n';//cout << u << ' ' << u << 'n';upd(1,1,n,1,x,-1); upd(1,1,n,y+1,n,-1); upd(1,1,n,u,u,n); }return0; }

T2

题意：给一个长度为的数组，相邻两项若差不大于1则可以交换，问能得到的不同个数，答案模。

数据范围：

计数问题基本就是 dp 了。发现从上一题中的不大于变成了不大于，必然有猫腻。由于差大于的数很多，所以大部分数之间是不能够对换位置的，考虑从这一点入手解决问题。

然后此时如果观察到了奇数之间不可能调换位置（除非两数相同，但是这样的调换没有意义），偶数也同理。于是设计 dp 状态为表示当前确定了前个位置，有个奇数，个偶数。对每个数，预处理它最远能与它不同奇偶性的哪个数交换即可。转移是简单的。

时间复杂度：。

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#definedebug(...) fprintf(stderr, __VA_ARGS__)#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;inlinellread(){ ll x=0,f=1;charch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}returnx*f; }constintN=5e3+5,P =1e9+7;intn,a[N],pos[N];voidadd(int&x,constinty){x += y;if(x > P)x -= P;}voidsub(int&x,constinty){x -= y;if(x <0)x += P;}voidsolve(){ n = read();vector<int> even,odd; rep(i,1,n){ a[i] = read();if(a[i] &1){ pos[i] = sz(odd); odd.pb(i); }else{ pos[i] = sz(even); even.pb(i); } }vector<int> pre(n+1); rep(i,1,n){if(a[i] &1)pre[i] = sz(even);elsepre[i] = sz(odd); rep(j,i+1,n)if(((a[i] - a[j]) &1) &&abs(a[i] - a[j]) >1){ pre[i] = min(pre[i],pos[j]); } }vector dp(sz(even) +1,vi(sz(odd) +1)); dp[0][0] =1; rep(i,0,sz(even))rep(j,0,sz(odd)){if(!dp[i][j])continue;if(i < sz(even) && j <= pre[even[i]]) add(dp[i+1][j],dp[i][j]);if(j < sz(odd) && i <= pre[odd[j]]) add(dp[i][j+1],dp[i][j]); }cout<< dp[sz(even)][sz(odd)] <<'n'; }intmain(){intT = read();while(T--)solve();return0; }

T3

题意：给定组向量，求每一组中选出一个向量，加起来后最大的长度。

数据范围：向量数不超过，。

我们维护当前所有可能答案构成的点集，有

性质1：如果一个点不在该点集的凸包上，那么这个点离原点的距离不是最大的。

对每一组向量我们都可以求出它的凸包。对于第组向量，我们将它的凸包与前组得到的答案凸包合并，用 Minkowski 和即可。

时间复杂度：。

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#definedebug(...) fprintf(stderr, __VA_ARGS__)#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;inlinellread(){ ll x=0,f=1;charch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}returnx*f; }constintN=2e5+5;structnode{ll x,y; nodeoperator- (constnode a){return(node){x-a.x,y-a.y};} nodeoperator+ (constnode a){return(node){x+a.x,y+a.y};} lloperator* (node a)const{returnx*a.y - y*a.x;}//cross prolllen()const{returnx*x + y*y;} }O;boolcmpy(constnode &a,constnode &b){returna.y == b.y ? a.x < b.x : a.y < b.y;}boolcmp(constnode &a,constnode &b){returna*b ==0? a.len() < b.len() : a*b >0;}intn,m,q,stk[N],top,tot;voidConvex(vector &A){ sort(A.begin(),A.end(),cmpy); O = A[0]; stk[top=1] =0; rep(i,0,sz(A)-1)A[i] = A[i] - O; sort(A.begin()+1,A.end(),cmp);//极角排序rep(i,1,sz(A)-1){while(top >1&& (A[i] - A[stk[top-1]]) * (A[stk[top]] - A[stk[top-1]]) >=0)top--; stk[++top] = i; } rep(i,1,top)A[i-1] = A[stk[i]] + O; A.resize(top);//rep(i,0,sz(A)-1)cout << A[i].x << ' ' << A[i].y << 'n';A.pb(A[0]); }vector A,B,vec[N],dA,dB,ans,tmp;voidMinkowski(vector &A,vector &B){ dA.resize(sz(A)),dB.resize(sz(B)); rep(i,0,sz(A)-1)dA[i] = A[(i+1)%sz(A)] - A[i]; rep(i,0,sz(B)-1)dB[i] = B[(i+1)%sz(B)] - B[i]; ans.pb(A[0] + B[0]);inta =0,b =0;while(a < sz(A) && b < sz(B)){if(dA[a] * dB[b] >=0)ans.pb(ans.back() + dA[a++]);elseans.pb(ans.back() + dB[b++]); }while(a < sz(A))ans.pb(ans.back() + dA[a++]);while(b < sz(B))ans.pb(ans.back() + dB[b++]); }intmain(){ n = read(); rep(i,1,n){intx = read(); rep(j,1,x)vec[i].pb((node){read(),read()}); Convex(vec[i]); } ans = vec[1]; rep(i,2,n){ tmp = ans;ans.clear(); Minkowski(vec[i],tmp); Convex(ans); } ll len =0;for(autot : ans)len = max(len,t.len());cout<< len <<'n';return0; }