|
純粹是為了節(jié)省篇目所以把這倆合在一起了
高維前綴和(sosDP)
不是很懂我為什么要在FWT之后學(xué)這個(gè)東西
子集和DP Sum over Subsets dynamic programming 一般用來解決這種東西：
\[\forall 0\leq i\leq 2^n-1,\sum_{j\subset i}a[j]
\] 直接枚舉子集是 \(\mathcal{O}(3^n)\) 的，用這個(gè)東西做到 \(\mathcal{O}(n\cdot 2^n)\) .
思路&實(shí)現(xiàn)
先考慮維度較低的前綴和。眾所周知,，二維前綴和就是四個(gè)矩形容斥一下。但是還有一種寫法是對每一個(gè)維度分別求前綴和：
for ( int i=1; i<=n; i++ )
for ( int j=1; j<=n; j++ )
a[i][j]+=a[i-1][j];
for ( int i=1; i<=n; i++ )
for ( int j=1; j<=n; j++ )
a[i][j]+=a[i][j-1];
如果維度上升到三維甚至更多,，容斥會(huì)變得極其不可做,，但是這種逐維求和的方式還是可行的。
高維前綴和利用的其實(shí)就是這種按位的思想,，加上一個(gè)DP,。
以上面的子集問題為例，設(shè) \(dp[i][S]\) 表示狀態(tài)為 \(S\) ,，二進(jìn)制最后 \(i\) 位和 \(S\) 不同的子集的信息之和,。
對于這種子集關(guān)系，放一張 剽來的圖 ：
容易發(fā)現(xiàn),，我們每次只需要統(tǒng)計(jì)枚舉的當(dāng)前位為 \(0/1\) 的,、上一層的子集答案，并且在當(dāng)前位為 \(0\) 的時(shí)候只需要統(tǒng)計(jì)為 \(0\) 的情況,。寫成代碼就是（這里把第一維滾掉了w）
for ( int i=0; i<(1<<n); i++ ) f[i]=a[i];
for ( int i=0; i<n; i++ )
for ( int S=0; S<(1<<n); S++ )
if ( S&(1<<i) ) f[S]+=f[S^(1<<i)];
超集：如果 \(S_2\subseteq S_1\) ,，那么 \(S_1\) 是 \(S_2\) 的超集。
sosDP 同樣可以用來解決超集求和問題,，方法是幾乎相同的,，可以理解為把子集問題中所有的 \(01\) 反轉(zhuǎn)。
for ( int i=0; i<(1<<n); i++ ) f[i]=a[i];
for ( int i=0; i<n; i++ )
for ( int S=0; S<(1<<n); S++ )
if ( !(S&(1<<i)) ) f[S]+=f[S^(1<<i)];
注：更一般的情況下,，高維前綴和中這個(gè) += 是將兩個(gè)答案合并,，即 f[S]=Merge(f[S],f[S^(1<<i)]) .
習(xí)題
給定一個(gè)長度為 \(2^n\) 的序列 \(a\) ，對于 \(1\leq k\leq 2^n-1\) ,，求 \(\max\{a[i]+a[j]\},\forall i|j\leq k\) ,，\(k\) 取遍 \(1\sim 2^n-1\) 。
\(\forall i|j\leq k\) 這個(gè)條件可以轉(zhuǎn)化為：求出 \(i|j=k\) 的答案,，然后前綴 \(\max\) ,。而對于 \(i|j=k\) ，又可以轉(zhuǎn)化為 \(i|j\subseteq k\) ,，因?yàn)槿绻虺鰜硎莻€(gè)真子集只會(huì)讓答案更小,。到了這一步，其實(shí)就是求 \(k\) 所有子集中 \(a[i]\) 的最大值和次大值,，然后合并答案即可,。
//Author: RingweEH
void bmax( int &a,int b ) { a=(a>b) ? a : b; }
const int N=19,INF=0x3f3f3f3f;
struct Node
{
int mx1,mx2;
Node ( int _mx1=-INF,int _mx2=-INF ) : mx1(_mx1),mx2(_mx2) {}
}f[1<<N];
int a[1<<N],n;
Node Merge( Node t1,Node t2 )
{
Node res=t1;
if ( t2.mx1>res.mx1 ) res.mx2=res.mx1,res.mx1=t2.mx1,bmax(res.mx2,t2.mx2);
else bmax( res.mx2,t2.mx1 );
return res;
}
int main()
{
n=read(); int m=1<<n;
for ( int i=0; i<m; i++ ) a[i]=read();
for ( int i=0; i<m; i++ ) f[i]=Node(a[i]);
for ( int i=0; i<n; i++ )
for ( int S=0; S<m; S++ )
if ( S&(1<<i) ) f[S]=Merge(f[S],f[S^(1<<i)]);
int ans=0;
for ( int i=1; i<m; i++ )
bmax( ans,f[i].mx1+f[i].mx2 ),printf("%d\n",ans );
return 0;
}
給定一個(gè)長度為 \(n\) 的序列 \(a\) ，求對于所有滿足 \(i<j<k\) 的三元組 \((i,j,k)\) ,，\(\max\{a_i|(a_j\&a_k)\}\) .
某一個(gè)數(shù) \(x\) 出現(xiàn)兩次及以上就能被 \(\&\) 出來了,，所以可以枚舉 \(a[i]\) 然后統(tǒng)計(jì)對應(yīng)的 \(a[j]\&a[k]\) ，再把 \(a[i]\) 統(tǒng)計(jì)進(jìn)去，順帶滿足大小關(guān)系,。
//Author: RingweEH
void Add( int x,int p )
{
if ( cnt[x]>=2 ) return;
if ( p==-1 ) { cnt[x]++; return; }
Add( x,p-1 );
if ( x&(1<<p) ) Add( x^(1<<p),p-1 );
}
int Get( int x )
{
int res=0;
for ( int i=20; i>=0; i-- )
if ( !(x&(1<<i)) && cnt[res|(1<<i)]>=2 ) res|=(1<<i);
return res|x;
}
int main()
{
n=read();
for ( int i=1; i<=n; i++ ) a[i]=read();
int ans=0;
for ( int i=n; i; i-- )
{
if ( i<=n-2 ) bmax( ans,Get(a[i]) );
Add( a[i],20 );
}
printf("%d\n",ans );
return 0;
}
問數(shù)組中的每個(gè)數(shù) \(a[i]\) 是否可以在數(shù)組里面找到 \(a[j]\&a[i]=0\) ,，輸出 \(a[j]\) 或 -1 .
也就是找 \(a[i]\) 取反之后的子集。
//Author: RingweEH
int main()
{
memset( dp,-1,sizeof(dp) );
n=read();
for ( int i=1; i<=n; i++ ) a[i]=read(),dp[a[i]]=a[i];
int lim=(1<<22);
for ( int i=0; i<=22; i++ )
for ( int S=0; S<lim; S++ )
if ( dp[S]==-1 && (S>>i&1) ) dp[S]=dp[S^(1<<i)];
for ( int i=1; i<=n; i++ ) printf("%d ",dp[(lim-1)^a[i]] );
return 0;
}
動(dòng)態(tài)DP(DDP)
前置芝士：
- 矩陣乘法加速遞推
- 一定的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（線段樹,、樹剖,、LCT……）
廣義矩陣乘法
DDP 的基本思想是把DP轉(zhuǎn)移式拆成矩陣乘法，然后再用數(shù)據(jù)結(jié)構(gòu)維護(hù),。很多DP式里面都有 \(\max\) ,，無法用一般的加法乘法表達(dá)，所以我們需要對矩陣乘法進(jìn)行魔改,。
矩陣乘法的結(jié)合律的成立只依賴于乘法對加法有分配率,，\(a\cdot(b+c)=ab+ac\) ，而加法對 \(\min\max\) 也有分配率,，\(a+\max(b,c)=\max(a+b,a+c)\) ,，所以可以重定義矩陣乘法：\(C[i][j]=\max_k\{A[i][k]+B[k][j]\}\) ，發(fā)現(xiàn)這個(gè)新的矩乘很像 Floyd ,，而 Floyd 的原理又是DP……所以,？
\(n\) 個(gè)數(shù)，\(q\) 次操作,。
0 x y \(a[x]\) 修改為 \(y\)1 l r 詢問 \([l,r]\) 最大子段和,。
首先列出最大子段和的DP式：設(shè) \(f[i]\) 表示以 \(a[i]\) 結(jié)尾的最大子段和，\(g[i]\) 表示 \([1,i]\) 的最大子段和,。
\[f[i]=\max(f[i-1]+a[i],a[i]),g[i]=\max(g[i-1],f[i])
\] 把這玩意兒改寫成矩陣乘法：
\[\begin{bmatrix}
a_i & -\infin & a_i\a_i & 0 & a_i\-\infin & -\infin & 0
\end{bmatrix}
\begin{bmatrix}
f_{i-1}\g_{i-1}\0
\end{bmatrix}
=\begin{bmatrix}
f_i\\g_i\\0
\end{bmatrix}
\] 線段樹維護(hù)區(qū)間矩陣乘積即可,。
//Author: RingweEH
#define ls pos<<1
#define rs pos<<1|1
const int N=5e4+10,INF=INT_MAX>>2;
struct Matrix
{
int mat[3][3];
Matrix(){for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)mat[i][j]=-INF;}
}tr[N<<2];
int a[N],n,q;
Matrix operator * ( const Matrix &A,const Matrix &B )
{
Matrix res;
for ( int k=0; k<=2; k++ )
for ( int i=0; i<=2; i++ )
for ( int j=0; j<=2; j++ )
bmax( res.mat[i][j],A.mat[i][k]+B.mat[k][j] );
return res;
}
void Pushup( int pos ) { tr[pos]=tr[ls]*tr[rs]; }
void Build( int pos,int l,int r )
{
if ( l==r )
{
tr[pos].mat[0][0]=tr[pos].mat[0][2]=tr[pos].mat[1][0]=tr[pos].mat[1][2]=a[l];
tr[pos].mat[1][1]=tr[pos].mat[2][2]=0; return;
}
int mid=(l+r)>>1;
Build(ls,l,mid); Build(rs,mid+1,r); Pushup(pos);
}
void Modify( int pos,int l,int r,int x,int val )
{
if ( l==r ) { tr[pos].mat[0][0]=tr[pos].mat[0][2]=tr[pos].mat[1][0]=tr[pos].mat[1][2]=val; return; }
int mid=(l+r)>>1;
(x<=mid) ? Modify(ls,l,mid,x,val) : Modify(rs,mid+1,r,x,val);
Pushup(pos);
}
Matrix Query( int pos,int L,int R,int l,int r )
{
if ( l<=L && R<=r ) return tr[pos];
int mid=(L+R)>>1;
if ( l<=mid && r>mid ) return Query(ls,L,mid,l,r)*Query(rs,mid+1,R,l,r);
return ( l<=mid ) ? Query(ls,L,mid,l,r) : Query(rs,mid+1,R,l,r);
}
int main()
{
n=read();
for ( int i=1; i<=n; i++ ) a[i]=read();
q=read();
Build(1,1,n);
while ( q-- )
{
int opt=read(),x=read(),y=read();
if ( opt )
{
if ( x>y ) swap( x,y );
Matrix res=Query( 1,1,n,x,y );
printf("%d\n",max(res.mat[1][0],res.mat[1][2]) );
}
else a[x]=y,Modify(1,1,n,x,y);
}
return 0;
}
給定一棵 \(n\) 點(diǎn)樹，\(m\) 次單點(diǎn)修改點(diǎn)權(quán)操作,，每次操作之后求最大權(quán)獨(dú)立集權(quán)值大小。
先不帶修改找式子,。顯然是
\[f[u][0]=\sum_{v\in son[u]}\max(f[v][0],f[v][1])\\\f[u][1]=\sum_{v\in son[u]}f[v][0]+a[i]
\] 然后,，考慮要套什么數(shù)據(jù)結(jié)構(gòu)。由于這里復(fù)雜度要求是 \(\mathcal{O(n\log n)}\) ,，所以不難想到用重鏈剖分,。然而我貌似有點(diǎn)忘了
樹剖復(fù)習(xí)。
其實(shí)就是按照子樹大小劃分輕重兒子/邊,，然后輕重鏈取極長,，重節(jié)點(diǎn)優(yōu)先遍歷出來的DFS序中重鏈、子樹都是連續(xù)的,。而且有重要性質(zhì)：任何一個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑中,，包含不超過 \(\log n\) 條重鏈。
找重兒子和DFS序可以兩遍完成。后面就是在DFS序上維護(hù)東西了,，沒什么好說的,。
為了能樹剖，要把DP式子稍微修改一下：令 \(g[u][0]\) 表示 \(u\) 所有輕兒子,，隨意取的最大權(quán)獨(dú)立集,；\(g[u][1]\) 表示 \(u\) 所有輕兒子不取自己的最大值，加上 \(u\) 本身的權(quán)值,。轉(zhuǎn)移方程就可以把求和去掉,，變成（這里 \(v\) 是重兒子）
\[f[u][0]=\max(g[u][0]+f[v][0],g[u][0]+f[v][1])\\\f[u][1]=g[u][1]+f[v][0]
\] 然后就要把它寫成矩陣：
\[\begin{bmatrix}
g[u][0] & g[u][0]\g[u][1] & -\infin
\end{bmatrix}
\begin{bmatrix}
f[v][0]\f[v][1]
\end{bmatrix}
=
\begin{bmatrix}
f[u][0]\f[u][1]
\end{bmatrix}
\] 為了節(jié)省空間把一些常見結(jié)構(gòu)體省略了……
//Author: RingweEH
void bmax( int &a,int b ) { a=(a>b) ? a : b; }
#define ls pos<<1
#define rs pos<<1|1
const int N=1e5+1,M=2e5+1,NM=4e5+1,INF=0x3f3f3f3f;
int tot,head[N],n,m,tim,f[N][2];
int a[N],fa[N],siz[N],dep[N],dfn[N],id[N];
int wson[N],top[N],ed[N];
struct Matrix
{
int mat[2][2];
Matrix(){memset(mat,-0x3f,sizeof(mat));}
}val[N];
Matrix operator * ( Matrix A,Matrix B )
struct Edge { int to,nxt; }e[M];
void Adde( int u,int v )
struct SegmentTree { int le[NM],ri[NM]; Matrix tr[NM]; }Tr;
void DFS1( int u )
{
siz[u]=1;
for ( int i=head[u]; i; i=e[i].nxt )
{
int v=e[i].to;
if ( v==fa[u] ) continue;
fa[v]=u; dep[v]=dep[u]+1; DFS1(v);
siz[u]+=siz[v];
if ( siz[v]>siz[wson[u]] ) wson[u]=v;
}
}
void DFS2( int u,int lin )
{
id[u]=++tim; dfn[tim]=u; top[u]=lin; bmax(ed[lin],tim);
f[u][0]=0; f[u][1]=a[u];
val[u].mat[0][0]=val[u].mat[0][1]=0; val[u].mat[1][0]=a[u];
if ( wson[u]^0 )
{
DFS2(wson[u],lin);
f[u][0]+=max(f[wson[u]][0],f[wson[u]][1] ); f[u][1]+=f[wson[u]][0];
}
for ( int i=head[u]; i; i=e[i].nxt )
{
int v=e[i].to;
if ( v==fa[u] || v==wson[u] ) continue;
DFS2(v,v);
f[u][0]+=max(f[v][0],f[v][1]); f[u][1]+=f[v][0];
val[u].mat[0][1]=val[u].mat[0][0]+=max(f[v][0],f[v][1]);
val[u].mat[1][0]+=f[v][0];
}
}
void Update( int x,int y )
{
val[x].mat[1][0]+=y-a[x]; a[x]=y;
Matrix pre,las;
while ( x^0 )
{
pre=Tr.Query(1,id[top[x]],ed[top[x]]);
Tr.Modify(1,id[x]);
las=Tr.Query(1,id[top[x]],ed[top[x]]);
x=fa[top[x]];
val[x].mat[0][0]+=max(las.mat[0][0],las.mat[1][0])-max(pre.mat[0][0],pre.mat[1][0]);
val[x].mat[0][1]=val[x].mat[0][0]; val[x].mat[1][0]+=las.mat[0][0]-pre.mat[0][0];
}
}
int main()
{
n=read(); m=read();
for ( int i=1; i<=n; i++ ) a[i]=read();
for ( int i=1,u,v; i<n; i++ ) u=read(),v=read(),Adde(u,v),Adde(v,u);
DFS1(1); DFS2(1,1);
Tr.Build(1,1,n); Matrix ans;
for ( int i=1,x,y; i<=m; i++ )
{
x=read(); y=read();
Update(x,y); ans=Tr.Query(1,id[1],ed[1]);
printf("%d\n",max(ans.mat[0][0],ans.mat[1][0]) );
}
return 0;
}
看這里
參考材料
sosDP DDP
|
