状压DP暨高维前缀和暨8月4日刷题日记暨65级讲课课件()-其他

发表于： 8月 4, 2022 8月 4, 2022
分类：其他
标签：其他

状压DP暨高维前缀和暨8月4日刷题日记暨65级讲课课件()

状压DP & SOSDP

既然你们不客气，我也不客气了。

写东西没点数，你们是来 1 个月速通 NOI 还是 NOIP？

典：爆踩替罪羊树的 why 竟然要讲搜索，爆踩大模拟的 dzy 也要搜索，爆踩左偏树的lxy不懂莫反

蓝紫起步，极不友好，听不懂可以睡觉，不愿意听可以睡觉。

说好，我就没打算让你们听懂，讲完别问我，我只负责上课。

争取 20 min 上完。

状压DP

定义：

：状压 \(dp\) 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

OI-WIKI

其利用计算机二进制的性质来描述状态的一种DP方式。

很多棋盘问题都运用到了状压，同时，状压也很经常和BFS及DP连用。

前置

状压常用操作
脑子一个

例题

P1896 [SCOI2005]互不侵犯

题目描述:在 \(n \times n(1 \le n \le 10)\) 的棋盘上放 \(k(0\le k<n\times n)\) 个国王，国王可攻击相邻的 \(8\) 个格子，求使它们无法互相攻击的方案总数。

第一反应是什么？搜索？对不起你 T 了。想想为什么。

我们令每一行放国王为1，不放为0，则每一行都能用一个 01 串表示，而这个 01 串可以当成二进制码，把他转化成十进制，就对应了一个数，也就是说 \(n\le 9\) ，总共有 \([0,2^{9}]\) 种 01 串，其中不乏一些不合法的，我们可以预处理出合法的 01 串。再考虑01串的贡献，明显的1的个数就是贡献，预处理的时候一并处理贡献。

设 \(f[i][j][k]\) 表示前 \(i\) 行，十进制表示下状态为 \(j\) ，前 \(i\) 行放 \(k\) 个国王的方案数。显然的转移：

啥意思？第 \(i\) 行的贡献由 \(i-1\) 行累加，\(j\) 和 \(x\) 分别代表两种不同的合法状态(行间合法，行内合法)，放 \(k\) 个国王则由没放 \(i\) 行时加上放 \(i\) 行的合法状态的贡献得来。

/*
Knowledge : Rubbish Algorithm
Work by : Dreamcatcher
Time : O(AC)
*/
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF=0x3f3f3f3f;
const int Mod=1e9+7;
const int N=1e6+6;

int read() {
    int x=0,f=0;char ch=getchar(); 
    for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch&15);
    return f?-x:x;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+48);
}

int sta[N],sit[N],f[10][1005][90];
//状态十进制存sit，二进制中1的个数存sta
//f[i][j][k] i行，j枚举状态的十进制，k统计国王个数 
int n,k,cnt;

void prepare(int x,int num,int cur){
    if(cur>=n) return sit[++cnt]=x,sta[cnt]=num,void();
    prepare(x,num,cur+1);prepare(x+(1<<cur),num+1,cur+2); 
} 
//预处理出可能存在的所有状态 
 
bool Judge(int i,int j){
    if((sit[i]&sit[j])|((sit[i]<<1)&sit[j])|
    (sit[i]&(sit[j]<<1))) return 0;return 1;
}

signed main() {
   n=read();k=read();prepare(0,0,0);
   for(int i=1;i<=cnt;i++) f[1][i][sta[i]]=1;
   for(int i=2;i<=n;i++){
   for(int j=1;j<=cnt;j++){
   for(int x=1;x<=cnt;x++){
   if(!Judge(j,x)) continue;
   for(int l=sta[j];l<=k;l++) 
   f[i][j][l]+=f[i-1][x][l-sta[j]];
   }}}int Ans=0;for(int i=1;i<=cnt;i++) 
   Ans+=f[n][i][k];print(Ans);
   return 0;
}

重新填坑。 ——6.11

P1879 [USACO06NOV]Corn Fields G

感觉是上一题的弱化版，省去了 \(k\) 个的限制条件，我们依然预处理出每种状态及合法性，然后转移即可。

复杂度大概是 \(\mathcal{O(n\cdot m \cdot 4^n)}\)，后面的 \(4^n\) 跑不满，因为开始筛的时候省去了很多无用状态，所以跑的还很快。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
const int N=1e6+7;
using namespace std;

inline int read() {
	int x=0,f=0;
	char ch=getchar();
	while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}

int b[N>>10][N>>10],Ans,n,m,stc[N],sc,f[13][4100],a[N];

void dfs(int pos,int num){
	if(pos>=m) return stc[++sc]=num,void();
	dfs(pos+1,num);dfs(pos+2,num+(1<<pos));
}

signed main() {
	n=read(),m=read();dfs(0,0);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) 
	b[i][j]=read(),a[i]=(a[i]<<1)+b[i][j];  
	for(int i=1;i<=sc;i++){
		f[1][stc[i]]=1;for(int j=1;j<=m;j++)
		if(!b[1][j]&&((stc[i]>>(j-1))&1))f[1][stc[i]]=0;
	}
	for(int i=2;i<=n;i++)
	for(int j=1;j<=sc;j++)
	for(int k=1;k<=sc;k++){
		if(stc[j]&stc[k]) continue;
		bool flg=0;for(int p=1;p<=m;p++)
		if(!b[i][p]&&(stc[j]>>(p-1)&1)){flg=1;break;}
		if(flg) continue;f[i][stc[j]]=(f[i][stc[j]]+f[i-1][stc[k]])%100000000;
	}
	for(int i=1;i<=sc;i++) Ans=(Ans+f[n][stc[i]])%100000000;
	printf("%lld\n",Ans);
	return 0;
}

SOS_DP

全称是 \(Sum \ over \ Subsets \ Dynamic \ Programming\) (子集和DP)，俗称的高维前缀和，为什么放这，因为和状压 DP 类似，并且我状压 DP 应该讲的很快，为了凑时间。

一维前缀和？不会你退吧。

二维前缀和？不会你退吧。

三维前缀和？不会你会一维二维不会推三维？退了吧。

容斥也行，每一维分别前缀和也行。（代码粘的）

//二维
for(int i=1;i<=n;++i)//先求数组a关于第一个维度的前缀和
{
    for(int j=1;j<=m;++j)
    {
        a[i][j]=a[i][j]+a[i][j-1];
    }
} 
for(int i=1;i<=n;++i)//在已经求完一个维度前缀和的基础上求数组a关于第二个维度的前缀和
{
    for(int j=1;j<=m;++j)
    {
        a[i][j]=a[i][j]+a[i-1][j];
    }
}

//三维
for(int i=1;i<=n;++i)
{
    for(int j=1;j<=m;++j)
    {
        for(int k=1;k<=p;++k)
        {
            a[i][j][k]+=a[i-1][j][k];
        }
    }
}
for(int i=1;i<=n;++i)
{
    for(int j=1;j<=m;++j)
    {
        for(int k=1;k<=p;++k)
        {
            a[i][j][k]+=a[i][j-1][k];
        }
    }
}
for(int i=1;i<=n;++i)
{
    for(int j=1;j<=m;++j)
    {
        for(int k=1;k<=p;++k)
        {
            a[i][j][k]+=a[i][j][k-1];
        }
    }
}

复杂度跟维数相关，可以这样求高维前缀和，可以说这是理论上的前缀和操作，现实意义不大。

而真正的高维前缀和是这样的：

求：\(f[st]=\sum_{i \subseteq st} w[i]\)

就是 \(i \subseteq st\) 即 \(i\ \& \ st = i\) ，一眼子集。

例子：\(1010_2\) 子集为：\(1010_2,1000_2,0010_2,0000_2\)。

不懂也该看懂了吧。

也就：\(f[st]=1010_2\) 时：\(f[1010_2]=w[1010_2]+w[1000_2]+w[0010_2]+w[0000_2]\)

子集类 DP 解决这个高效。

原理：

设\(f[st][i]\) 表示 \(st\) 状态时最后 \(i\) 位变化的所有子集的贡献。

然后 DP 一下。

\(i\) 位为 \(0\)，\(f[st][i]=f[st][i-1]\)
\(i\) 位为 \(1\)，\(f[st][i]=f[st][i-1]+f[st \ \oplus 2^i ][i – 1]\)

滚动数组滚掉第一维。

同理还有超集和 DP，只需加个 \(!\) 就可以了！

什么是超集？

超集：如果一个集合 \(S_2\) 中的每一个元素都在集合 \(S_1\) 中，且集合 \(S_1\) 中可能包含 \(S_2\) 中没有的元素，则集合 \(S_1\) 就是 \(S_2\) 的一个超集，反过来，\(S_2\) 是 \(S_1\) 的子集。 \(S_1\) 是 \(S_2\) 的超集。

for(int i=0;i<(1<<n);i++) f[i]=w[i];
for(int i=0;i<n;i++){
	for(int st=0;st<(1<<n);st++)
        if(st&(1<<i)) f[i]+=f[st^(1<<i)];
}

CF165E Compatible Numbers

查询每个 \(a_i\) 是否有 \(a_i\ \& \ a_j =0\) 的 \(a_j\) 存在，高维前缀和，发现 \(\&\) 起来是 \(0\)，就说明二进制下每一位对起来不是叉开了就是都是 \(0\)。那就说明要是 \(a_j\) 取反之后一定是 \(a_i\) 的子集，既然 SPJ，随便存一个子集就行了。

怎么取反？全 \(\oplus \ 1\) 啊，\(1e6\) 大概 \(1<<22\) 左右，瞎写写就过了。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define debug cout<<"Szt ak ioi\n";
//#define int long long

const int Mod=1e9+7;
const int N=1e6+7,M=2e3+1;
const int Max=(1<<22)-1;

using namespace std;

inline int read() {
	int x=0,f=0;
	char ch=getchar();
	while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return f?-x:x;
}

int n,w[1<<22],f[1<<22];
signed main() {
	n=read();
	for(int i=1;i<=n;i++) w[i]=read(),f[w[i]]=w[i];
	for(int i=0;i<22;i++)
	for(int j=0;j<(1<<22);j++)
	if((j&(1<<i))&&f[j^(1<<i)]) f[j]=f[j^(1<<i)];
	for(int i=1;i<=n;i++)
	printf("%d ",f[w[i]^((1<<22)-1)]?f[w[i]^((1<<22)-1)]:-1);
	return 0;
}

CF383E Vowels

原题翻译是有点毛病的，大意应该是：\(n\) 个长度为 \(3\) 的字符串 (范围为 \(a\) 到 \(x\) 共 \(24\) 个字符)，当一个字符串包含关键字符串的时候，这个字符串是正确的，对每个正确字符串个数平方求异或和。

SOS DP 萌萌题，首先非常显而易见的是，可以将字符串先压缩成长度为 \(24\) 的 \(2\) 进制串，对于每种状态 \(st\)，实际就是求 \(\sum_{st \&i \ne 0}a_i\) ，\(a[i]\) 是状态 \(i\) 的字符串有多少个，即与 \(st\) 有交集的字符串个数多少。通过 SOS DP 轻松求出。知道 \(f[i]\) 那么 \(f[\sim i]\) 就是不与 \(i\) 有交集的字符串的个数，所以 \(n-f[\sim i]\) 就是贡献。

#include<bits/stdc++.h>，
#define INF 0x3f3f3f3f
#define debug cout<<"Szt ak ioi\n";
#define int long long

const int Mod=1e9+7;
const int N=1e6+7,M=2e3+1;

using namespace std;

inline int read() {
	int x=0,f=0;
	char ch=getchar();
	while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return f?-x:x;
}

int n,f[1<<24],Ans;

signed main() {
	n=read();
	for(int i=1;i<=n;i++){
		char ch;int Num=0;
		for(int j=1;j<=3;j++) scanf(" %c",&ch),Num|=(ch<'y')?(1<<(ch-'a')):0;
		++f[Num];
	}
	for(int i=0;i<24;i++)
	for(int j=0;j<(1<<24);j++)
	if(j&(1<<i)) f[j]+=f[j^(1<<i)]; 
	for(int i=0;i<(1<<24);i++)Ans^=((n-f[i])*(n-f[i]));
	return 0&printf("%lld\n",Ans);
}

AT4168 [ARC100C] Or Plus Max

给你一个长度为 \(2^n\) 的序列 \(a\)，每个\(1\le K\le 2^n-1\)，找出最大的 \(a_i+a_j（i \ \or \ j ≤ K ,0 \le i < j < 2^n ）\)并输出。

SOS DP 直接考虑对于每个 \(K\) 求出下标为 \(K\) 子集的最大 \(a_i+a_j\)。那么显然一个是最大值，一个是次大值，这个是 SOS DP 轻松搞的。

但这样子是假的，因为 \(\leq K\) 不等于是 \(K\) 的子集。但很显然是 \(\leq K\) 的所有数的子集的并。于是按原先算法算出来答案后取个前缀 \(\max\) 即可。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define debug cout<<"Szt ak ioi\n";
//#define int long long

const int Mod=1e9+7;
const int N=1e6+7,M=2e3+1;

using namespace std;

inline int read() {
	int x=0,f=0;
	char ch=getchar();
	while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return f?-x:x;
}

int n,k,f[1<<19],g[1<<19];

signed main() {
	n=read();
	for(int i=0;i<(1<<n);i++)f[i]=read();
	for(int i=0;i<19;i++){
		for(int j=0;j<(1<<19);j++){
			if(j&(1<<i)){
				int d1,d2;
				int Pr=(j^(1<<i));
				if(f[j]>f[Pr]) d1=f[j],d2=max(g[j],f[Pr]);
				else d1=f[Pr],d2=max(f[j],g[Pr]);
				f[j]=d1,g[j]=d2;
			}
		}
	}int Ans=0;
	for(int i=1;i<(1<<n);i++) printf("%d\n",Ans=max(Ans,f[i]+g[i]));
	return 0;
}

这些应该够了，不够的话？就不够吧，我不讲了反正，徐逸尘的莫反应该都听的很明白吧，你莫反都嘎嘎懂了，这不是也乱杀？

————————