<span>模拟103 题解</span>
A. Game
$yxs$大神教你转化题意：
将B哥的牌视作左括号，小A的牌视作右括号。
那么问题转化为最多匹配多少个括号，并求出最大字典序的一组解。
如果不需要最大字典序，问题是简单的贪心，每次取出最小的右括号尝试匹配。
考虑一个暴力做法：
对于B哥的每一张牌，做$nlogn$的贪心得到最优解下之后能匹配多少对括号。
之后从大到小枚举填哪张牌，暴力$nlogn$ $check$能否达到最优匹配。
对于当前括号匹配/不匹配，这两个问题都是具有单调性的。
所以可以对两部分进行二分，然而还是一个只有20分的大暴力。
瓶颈在于$check$的复杂度是$nlogn$的。
实际上这个$check$还有一个分治做法。
每次考虑整个区间的答案，即左区间答案，右区间答案和跨过中点的答案。
在当前区间配对一定比留着以后配对更优，所以这个分治也用到了贪心的思想。
发现这个分治每次只修改一条链，可以用线段树优化分治的过程，做到$nlog^2n$
1 #include<set> 2 #include<cstdio> 3 #include<iostream> 4 #include<algorithm> 5 #define lch p<<1 6 #define rch p<<1|1 7 using namespace std; 8 const int N=1e5+7; 9 int n,cnt; 10 int a[N],b[N],lsh[N<<1]; 11 int ans[N<<3],sz[N<<3][2],rk[N<<3]; 12 void modify(int p,int pos,int id,int val,int L,int R){ 13 if(L==R) return sz[p][id]+=val,rk[p]+=id*val,void(); 14 int mid=L+R>>1; 15 if(pos<=mid) modify(lch,pos,id,val,L,mid); 16 else modify(rch,pos,id,val,mid+1,R); 17 int tmp=min(sz[lch][0],sz[rch][1]); 18 ans[p]=ans[lch]+ans[rch]+tmp; 19 sz[p][0]=sz[lch][0]+sz[rch][0]-tmp; 20 sz[p][1]=sz[lch][1]+sz[rch][1]-tmp; 21 rk[p]=rk[lch]+rk[rch]; 22 } 23 int query(int p,int k,int L,int R){ 24 if(L==R) return L; 25 int mid=L+R>>1; 26 if(rk[lch]>=k) return query(lch,k,L,mid); 27 else return query(rch,k-rk[lch],mid+1,R); 28 } 29 int getrank(int p,int pos,int L,int R){ 30 if(L==R) return rk[p]; 31 int mid=L+R>>1; 32 if(pos<=mid) return getrank(lch,pos,L,mid); 33 else return getrank(rch,pos,mid+1,R)+rk[lch]; 34 } 35 inline int read(register int x=0,register char ch=getchar(),register char f=0){ 36 for(;!isdigit(ch);ch=getchar()) f|=ch=='-'; 37 for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48); 38 return f?-x:x; 39 } 40 int main(){ 41 freopen("game.in","r",stdin); 42 freopen("game.out","w",stdout); 43 n=read(); 44 for(int i=1;i<=n;++i) lsh[++cnt]=b[i]=read(); 45 for(int i=1;i<=n;++i) lsh[++cnt]=a[i]=read(); 46 sort(lsh+1,lsh+cnt+1); cnt=unique(lsh+1,lsh+cnt+1)-lsh-1; 47 for(int i=1;i<=n;++i){ 48 a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh; 49 b[i]=lower_bound(lsh+1,lsh+cnt+1,b[i])-lsh; 50 modify(1,a[i],1,1,1,cnt); modify(1,b[i],0,1,1,cnt); 51 } 52 for(int i=1;i<=n;++i){ 53 int k=ans[1],l=getrank(1,b[i],1,cnt)+1,r=rk[1],mid,pp; 54 modify(1,b[i],0,-1,1,cnt); 55 if(l<=r){ 56 while(l<r){ 57 mid=l+r+1>>1; pp=query(1,mid,1,cnt); 58 modify(1,pp,1,-1,1,cnt); 59 if(ans[1]+1==k) l=mid; 60 else r=mid-1; 61 modify(1,pp,1,1,1,cnt); 62 } 63 pp=query(1,l,1,cnt); 64 modify(1,pp,1,-1,1,cnt); 65 if(ans[1]+1==k){ 66 printf("%d ",lsh[pp]); 67 continue; 68 } 69 modify(1,pp,1,1,1,cnt); 70 } 71 l=1,r=getrank(1,b[i],1,cnt); 72 while(l<r){ 73 mid=l+r+1>>1; pp=query(1,mid,1,cnt); 74 modify(1,pp,1,-1,1,cnt); 75 if(ans[1]==k) l=mid; 76 else r=mid-1; 77 modify(1,pp,1,1,1,cnt); 78 } 79 pp=query(1,l,1,cnt); 80 modify(1,pp,1,-1,1,cnt); 81 printf("%d ",lsh[pp]); 82 } 83 return 0; 84 }
B. Time
考场上的思路是考虑最大值，枚举最大值最终达到了哪个位置，之后两侧分别算逆序对就完了。
结果最后半个小时一对拍发现自己伪了，存在一些情况，最优决策并不交换最大值，但交换了另外的一些元素。
正解考虑的是最小值：
对于最小值，一定交换到最左侧或最右侧。
因为最小值交换到一侧之后，不会与其它任何一个点产生逆序对，
所以最小值可以贪心选择左侧或右侧中更优的一侧交换过去。
用树状数组动态维护一下选哪个方向更优就好了。
C. Cover
因为区间只有包含/不相交两种形态，可以建树表示区间之间的关系。
之后有一个显然的$dp$。
使$dp_{x,i}=\sum \limits_{son}dp_{son,i}$，即对子树对应位相加。
为了加入当前节点的贡献，倒序枚举$i$,$dp_{x,i}=max(dp_{x,i},dp_{x,i-1}+w_x)$。
然后可以用神奇的差分表优化一下这个$dp$，设$f_{x,i}=dp_{x,i}-dp_{x,i-1}$。
对于子树求和，在差分表上的操作是对应位相加。
问题在于如果加入一个点的贡献。
观察可以得出，差分表是单调的，也就是说$f_{x,i}>=f{x,i+1}$恒成立。
考虑在什么情况下，$dp_{x,i}<dp_{x,i-1}+w_x$成立，即取$max$操作是有意义的。
移项可得$w_x>dp_{x,i}-dp{x,i-1}$，即$w_x>f_{x,i}$，
所以对应操作是直接插入差分表中对应的位置，即维护单调结构。
通过直观的理解，上述的做法也都是成立的。
有了上述的做法，实际上也可以简单归纳，证明差分表的单调性。
因为每个子树中元素个数不超过子树大小，差分表的实现大概用到了树上启发式合并。
1 #include<set> 2 #include<queue> 3 #include<vector> 4 #include<cstdio> 5 #include<iostream> 6 using namespace std; 7 const int N=3e5+7; 8 struct node{ 9 int l,r,id; 10 node(){} 11 node(int l,int r,int id):l(l),r(r),id(id){} 12 friend bool operator <(const node &x,const node &y){ 13 return x.l==y.l?(x.r==y.r?x.id<y.id:x.r>y.r):x.l<y.l; 14 } 15 }s[N]; 16 multiset<node> st; 17 priority_queue<long long> f[N]; 18 int n,m,tot; 19 int w[N],head[N],nxt[N<<1],to[N<<1]; 20 long long val[N]; 21 inline void add(int a,int b){ 22 nxt[++tot]=head[a]; 23 head[a]=tot; 24 to[tot]=b; 25 } 26 void build(int p,int l,int r){ 27 while(!st.empty()){ 28 auto it=st.lower_bound(node(l,r,0)); 29 if(it==st.end()) break; 30 node k=*it; 31 if(k.l>=l&&k.r<=r){ 32 st.erase(it); 33 add(p,k.id); 34 build(k.id,k.l,k.r); 35 } 36 else break; 37 } 38 } 39 void dfs(int x){ 40 int son=m+1; 41 for(int i=head[x];i;i=nxt[i]){ 42 dfs(to[i]); 43 if(f[to[i]].size()>f[son].size()) son=to[i]; 44 } 45 swap(f[son],f[x]); 46 for(int i=head[x];i;i=nxt[i]){ 47 if(to[i]==son) continue; 48 int k=f[to[i]].size(),cnt=0; 49 for(int j=1;j<=k;++j) val[j]=f[x].top(),f[x].pop(); 50 for(int j=1;j<=k;++j) val[j]+=f[to[i]].top(),f[to[i]].pop(); 51 for(int j=1;j<=k;++j) f[x].push(val[j]); 52 } 53 f[x].push(w[x]); 54 } 55 inline int read(register int x=0,register char ch=getchar(),register char f=0){ 56 for(;!isdigit(ch);ch=getchar()) f|=ch=='-'; 57 for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48); 58 return f?-x:x; 59 } 60 int main(){ 61 freopen("cover.in","r",stdin); 62 freopen("cover.out","w",stdout); 63 n=read()-1; m=read(); 64 for(int i=1;i<=m;++i) s[i].id=i,s[i].l=read(),s[i].r=read()-1,w[i]=read(),st.insert(s[i]); 65 build(0,1,n); 66 dfs(0); 67 int k=f[0].size(); 68 for(int i=1;i<=k;++i) val[i]=f[0].top(),f[0].pop(); 69 for(int i=1;i<=m;++i) val[i]+=val[i-1],printf("%lld ",val[i]); 70 return 0; 71 }
查看8道真题和解析
