7.23模拟赛总结 [数据结构优化dp] + [神奇建图]

复盘

浅复盘下吧…

7:40 开题

看 T1 ，起初以为和以前某道题有点像，子序列划分，注意到状态数很少，搜出来所有状态然后 dp，然后发现这个 T1 和那个毛关系没有

浏览了一下，感觉 T2 题面又臭又长，意思也很恶心；T3 树上 ds 看上去很亲切；T4 一眼就不太可做

回来看 T1，发现很 sb，每次肯定贪心选最优的后缀，至于选 m 的限制，填满一段后再贪心往前选就行

8:04 码完了，小样例顺利过掉，一测大样例发现小数点后面不对，想了想应该不会是精度问题，可能做法假了

然后 不断证明结论+修改一些毫无影响的细节，仍然和大样例不上，最后决定把题面重读一遍，知道看到了 “相对误差”，6，突然想到我学过高中物理。。。到 8:50 才交上去

快开 T2，朴素的想法当然是 二维状态记 Max，但这个显然不太有优化空间（这种状态设计只有 $i-1$ 到 $i$ 只有 $O(1)$ 个决策需要单点修改时才能优化)

那么很快想到改成 $f_i$ 一维状态，钦定 $i$ 必选，往前找一个合法的，发现可以接上去的区间可以预处理出来，那么只需找 $[l,r]$ 内小于 $a_i$ 的最优决策… 三维偏序？树套树警告！

算了，先打暴力，竟然有 $O(1)pts$ 的高分，然鹅被一个 sb 细节卡住一直到 9:30 仍没调过，决定先看 T3

一眼发现是 sb 题，直接树上主席树就做完了，直接决定开码，10:30 过了小样例

然鹅大样例又挂了，反复调根本不明白怎么回事，一度以为自己主席树板子假了

最后突然想着把数组开大一倍，卧槽对了，不爆 RE 直接 WA 是吧，浪费了高达 $O(n)$ 的时间

11:00 了，先把 T1 暴力调了吧，发现弱智错误… 然后看看能不能写点性质，得到了高达 $5pts$ 的性质分

最后想 T2 感觉写不完，决定开 T4 暴力

最后获得了高达 $7pts$ 的暴力分，赢！

所以 100+53+100+7=260 , rk $O(2^n)$

题解

T2

其实离正解不远了，回顾一下转移：

$f_i=max(f_j+1)$，其中 $j<i,a_j<a_i$ 且 $i,j$ 可以通过小于 $a_i$ 的数 “连接” 起来

直接三维偏序做也没错，但是本题可以有更多性质

注意到：能转移的决策满足 $a_j<a_i$，能连接其它数的数也是 $a_j<a_i$ ，二者可以同时维护

那么我们转到值域上做，从小到大插入新决策

每次处理询问时相当于要找连续段，这个可以 $set$ 做（更好做法是并查集，但是我不会）；然后询问区间 Max，线段树维护

遇到偏序问题可以尝试 在最外层换一维关键字排序，会有意想不到的效果

#include<bits/stdc++.h>
using namespace std ;typedef long long LL ;
const int N = 3e5+100 ;int n , D , a[N] ;
int f[N] , rhk[N] ;
struct Segtree
{int l , r , Max ;
}t[4*N] ;
bool cmp( int x , int y )
{return a[x] < a[y] ;
}
void build( int p , int l , int r )
{t[p].l = l , t[p].r = r ;if( l == r ) {return ;}int mid = ( l + r ) >> 1 ;build( p<<1 , l , mid ) ; build( p<<1|1 , mid+1 , r ) ;  
}
int ask( int p , int l , int r )
{if( l <= t[p].l && t[p].r <= r ) {return t[p].Max ;}int mid = ( t[p].l + t[p].r ) >> 1 , Max = 0 ;if( l <= mid ) Max = max( Max , ask(p<<1,l,r) ) ;if( r > mid ) Max = max( Max , ask(p<<1|1,l,r) ) ;return Max ;
}
void modify( int p , int x , int d )
{if( t[p].l == t[p].r ) {t[p].Max = max( t[p].Max , d ) ;return ;}int mid = ( t[p].l + t[p].r ) >> 1 ;if( x <= mid ) modify( p<<1 , x , d ) ;else modify( p<<1|1 , x , d ) ;t[p].Max = max( t[p<<1].Max , t[p<<1|1].Max ) ;
}
struct node
{int l , r ;friend bool operator < ( node x , node y ) {return x.r < y.r ;}
};
set<node> s ; // 维护连续段 
int query( int x ) // 查 x 可用决策 
{int P = max(1,x-D) ;auto it = s.lower_bound((node){0,P}) ;if( it == s.end() ) {return 0 ;}return ask( 1 , min(it->l,P) , x-1 ) ;
}
void Insert( int x )// 插入决策 x 
{modify( 1 , x , f[x] ) ;if( s.empty() ) {s.insert((node){x,x}) ;return ;}auto it = s.lower_bound((node){0,x}) ;int L = x , R = x , fg = 0 ;if( it != s.end() ) {if( x < it->l ) {if( x+D >= it->l ) {// 接上了R = it->r ;fg = 1 ;} if( it != s.begin() ) {auto iit = it ;iit -- ;if( iit->r + D >= x ) {L = iit->l ;s.erase( iit ) ;}}if( fg ) s.erase( it ) ;s.insert((node){L,R}) ;}return ;}it -- ;if( it->r+D >= x ) {L = it->l ;s.erase( it ) ;}s.insert((node){L,x}) ;
}int main()
{scanf("%d%d" , &n , &D ) ;for(int i = 1 ; i <= n ; i ++ ) {scanf("%d" , &a[i] ) ; rhk[i] = i ;}// 转移有两维限制，按值域做，去掉一维sort( rhk+1 , rhk+n+1 , cmp ) ;build( 1 , 1 , n ) ;int ans = 0 ;for(int i = 1 ; i <= n ; i ++ ) {int j = i ;f[rhk[i]] = query( rhk[i] ) + 1 ;while( j+1 <= n && a[rhk[j]] == a[rhk[j+1]] ) {j ++ ;f[rhk[j]] = query( rhk[j] ) + 1 ;}for(int k = i ; k <= j ; k ++ ) {Insert( rhk[k] ) ;}i = j ;}for(int i = 1 ; i <= n ; i ++ ) {ans = max( ans , f[i] ) ;}printf("%d" , ans ) ;return 0 ;
}

其实很好写

 

T4

神奇题

尝试 $dp$ ，发现根本做不了…

根据我们的经验，遇到十分之抽象且题面又臭又长又不知所云的题目大多是图论，所以这题考虑建图

额

老师讲的一个建图出发点：注意到最终序列中每个值 要么由 $a$ 提供，要么由 $b$，这种 “由 A 或由 B” 的问题是有二分图的样子的，考虑分左右两部，对于每个 $i$，将左部 $a_i$ 与 右部 $b_i$ 连边

我理解的：题目中给的 划分 实际上约束是很多的，我们考虑最初选所有 $a$ 中的集合，然后用 $b$ 中的若干个集合替换，这样 替换者的并 和 被替换者的并 必须是一样的，想换掉某个子集 $a[]$ 的话，必须选择 所有 包含 $b$ 中对应位置 的区间，然后对应回来 $a$ 中区间也必须选… 如此往复（口胡）

我们尝试形式化的去描述这个东西，发现正可以用上面那种建边方式来描述 ，一个连通块就代表了 可以相互替换的一组 $a[],b[]$

对于 $K=0$，我们直接对于每个连通块取较小的那一组替换

对于 $K=1$，考虑枚举边，分讨一下：

若断的是非割边，然后连到另一个连通块，这样贡献的变化是 $min(a,b)+min(c,d)\to min(a+c,b+d)$

显然有不等式 $min(a,b)+min(c,d)\le min(a+c,b+d)$，所以贡献不会变小，断开一定不优

这个不等式也告诉我们，要尽可能拆连通块，尽可能不合并连通块

若断割边，我们最好的当然是连回本身，只拆，不合并

注意！这里有一个 conner，如果一个连通块只有两个节点 $u,v$ 怎么办？我们显然没办法把 $u$ 向自己连边

然而有这么一个事情：不妨设 $u$ 为左部点，那么一定可以把 $u$ 连到一个 左部点数不小于右部点的连通块上（找不到的话考虑右部点 $v$ ），当 $n\ge 1$ 时，这样的连通块一定能找到

当 $n=1$，直接特判 答案为 $1$ 即可

对于 $K=2$，与上面相反，需要 尽可能合并连通块，尽可能不拆连通块

对于一个连通块，如果有 非割边 ，那么用它一定比用割边更优，因为不会拆，且能够合并

下面考虑应该和哪个连通块合并，对于两个连通块 $(a_1,b_1)$ , $(a_2,b_2)$

若 $a_1<b_1,a_2<b_2$ （不等号方向相同）：

贡献变化 $min(a_1+a_2,b_1+b_2)-min(a_1,b_1)-min(a_2,b_2)=0$，没影响

若 $a_1<b_1,a_2>b_2$ （相反）

贡献变化 $min(a_1+a_2,b_1+b_2)-min(a_1,b_1)-min(a_2,b_2)$

$=min(a_1+a_2,b_1+b_2)-a_1-b_2$
$=min(a_2-b_2,b_1-a_1)$
$=min({\Delta }_1,{\Delta }_2)$

当 $a_1,b_1$ 确定时，要找一个不等号相反，且差最大的，直接扫一遍记 Max 就行

如果全是割边，我们直接遍历这棵缩点后的树，依次断开每条树边即可

不太好写

#include<bits/stdc++.h>
using namespace std ;typedef long long LL ;
const int N = 2e5+100 ; int T , K , M1 , M2 ;
int n , a[N] , b[N] ;
struct nn
{int lst , to ;
}E[2*N] ;
int head[2*N] , tot = 1 ;
inline void add( int x , int y )
{E[++tot] = (nn){ head[x] , y } ;head[x] = tot ;
}
int dfn[2*N] , low[2*N] , tim ;
bool bri[2*N] ;
vector<int> e[2*N] ;
void tarjan( int x , int inE )
{dfn[x] = low[x] = ++tim ;for(int i = head[x] ; i ; i = E[i].lst ) {int t = E[i].to ;if( !dfn[t] ) {tarjan( t , i ) ;low[x] = min( low[x] , low[t] ) ;if( low[t] > dfn[x] ) {bri[i] = bri[i^1] = 1 ;}}else if( i != (inE^1) ) {low[x] = min( low[x] , dfn[t] ) ;}}
}
int cnt , bol , bel[2*N] , A[2*N] , B[2*N] , SA[2*N] , SB[2*N] ;
void dfs( int x )
{bel[x] = cnt ;if( x <= M1 ) A[cnt] ++ ;else B[cnt] ++ ;for(int i = head[x] ; i ; i = E[i].lst ) {int t = E[i].to ;if( bri[i] ) {if( bel[t] ) {e[bel[t]].push_back( bel[x] ) ;e[bel[x]].push_back( bel[t] ) ;}}else if( !bel[t] ) dfs( t ) ;}
}
int PA[2*N] , PB[2*N] , ans1 , ans2 , ans3 , rt[2*N] ;
bool can[2*N] ; // 是否有非割边 
void get_size( int x , int fa )
{SA[x] = A[x] , SB[x] = B[x] ;if( A[x]+B[x] > 1 ) can[bol] = 1 ;for(int t : e[x] ) {if( t == fa ) continue ;get_size( t , x ) ;SA[x] += SA[t] ; SB[x] += SB[t] ;}
}
void ddfs( int x , int fa )
{for(int t : e[x] ) {if( t == fa ) continue ;ans2 = max( ans2 , min(PA[bol],PB[bol])-min(SA[t],SB[t])-min(PA[bol]-SA[t],PB[bol]-SB[t]) ) ; // 最多减少多少 ddfs( t , x ) ;}
}
int I , Mx1 , Mx2 ;
inline int V ( int a , int b , int c , int d ) // 合并后增加多少 / 拆开后损失多少 
{return min(a+c,b+d)-min(a,b)-min(c,d) ;
}
inline int V1( int a , int b )
{if( a > b ) return min(a-b,Mx2) ;return min(b-a,Mx1) ;
}
void Get( int x , int fa ) // 处理割边 
{for(int t : e[x] ) {if( t == fa ) continue ;ans3 = max( ans3 , -V(SA[t],SB[t],PA[I]-SA[t],PB[I]-SB[t])+V1(SA[t],SB[t]) ) ;ans3 = max( ans3 , -V(SA[t],SB[t],PA[I]-SA[t],PB[I]-SB[t])+V1(PA[I]-SA[t],PB[I]-SB[t]) ) ;Get( t , x ) ;}
}
void solve()
{cnt = 0 ; bol = 0 ;for(int i = 1 ; i <= M1+M2 ; i ++ ) {if( !dfn[i] ) {tarjan( i , 0 ) ;}}for(int i = 1 ; i <= M1+M2 ; i ++ ) {if( !bel[i] ) {cnt ++ ;dfs( i ) ;}}ans1 = ans2 = ans3 = 0 ;for(int i = 1 ; i <= cnt ; i ++ ) {if( !SA[i]&&!SB[i] ) {bol ++ ;rt[bol] = i ;get_size( i , 0 ) ;PA[bol] = SA[i] , PB[bol] = SB[i] ;ddfs( i , 0 ) ;ans1 += min(PA[bol],PB[bol]) ;}}ans2 = ans1-ans2 ;if( K == 0 ) {printf("%d\n" , ans1 ) ;return ;}if( K == 1 ) {printf("%d\n" , ans2 ) ;return ;}if( K == 2 ) {Mx1 = 0 , Mx2 = 0 ;if( M1 < n ) Mx1 = 1 ;if( M2 < n ) Mx2 = 1 ;for(int i = 1 ; i <= bol ; i ++ ) {Mx1 = max( Mx1 , PA[i]-PB[i] ) ;Mx2 = max( Mx2 , PB[i]-PA[i] ) ;}for(int i = 1 ; i <= bol ; i ++ ) {if( can[i] ) {if( PA[i] > PB[i] ) ans3 = max( ans3 , min(PA[i]-PB[i],Mx2) ) ;else ans3 = max( ans3 , min(PB[i]-PA[i],Mx1) ) ;}else {I = i ;Get( rt[i] , 0 ) ;}}printf("%d\n" , ans3+ans1 ) ;return ;}
}
int nam[N][2] ;	
void Clear()
{for(int i = 2 ; i <= tot ; i ++ ) bri[i] = 0 ;tot = 1 ;for(int i = 1 ; i <= M1+M2 ; i ++ ) head[i] = dfn[i] = bel[i] = 0 ;for(int i = 1 ; i <= n ; i ++ ) nam[i][0] = nam[i][1] = 0 ;tim = 0 ; for(int i = 1 ; i <= cnt ; i ++ ) e[i].clear() , A[i] = B[i] = SA[i] = SB[i] = 0 ;for(int i = 1 ; i <= bol ; i ++ ) can[i] = 0 ; 
}int main()
{scanf("%d%d" , &T , &K ) ;while( T -- ) {scanf("%d" , &n ) ;if( n == 1 ) {printf("1\n") ;for(int i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i] ) ;for(int i = 1 ; i <= n ; i ++ ) scanf("%d" , &b[i] ) ;continue ;}M1 = 0 , M2 = 0 ;for(int i = 1 ; i <= n ; i ++ ) {scanf("%d" , &a[i] ) ;if( !nam[a[i]][0] ) {nam[a[i]][0] = ++M1 ;}a[i] = nam[a[i]][0] ;}for(int i = 1 ; i <= n ; i ++ ) {scanf("%d" , &b[i] ) ;if( !nam[b[i]][1] ) {nam[b[i]][1] = ++M2 ;}b[i] = nam[b[i]][1] ;add( a[i] , b[i]+M1 ) , add( b[i]+M1 , a[i] ) ;}solve() ;Clear() ;}return 0 ;
}