Fizzmy

状态压缩

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / 状态压缩（共8篇）

BZOJ1226-学校食堂Dining

传送门题意：中文题，非权限题。 Solution：显然不能贪心，那么考虑dp，注意到 b[i]≤7 b [ i ] ≤ 7 ，所以说可以考虑状压怎么做，再结合n<=1000，想到了一个状态：f[i][j][k]表示前i-1个人都吃过饭了，j表示后面7人和i的吃饭状态，上一个吃过饭的...

2021-08-18

0 361

ASC1 E-Nice Patterns Strike Back

传送门（codeforces GYM）题意：给你一个n*m的矩形，对其进行上色，要求每个2*2的小正方形中的颜色不能相同，求方案数模p。（n<=10100,m<=5,p<=10000） Solution: 看到计数题，首先考虑组合数或者dp，组合数发现行不通，考虑dp，...

2021-08-18

0 400

ARC58 E 和風いろはちゃん / Iroha and Haiku-状压DP

传送门题意：给出N,X,Y,Z,定义一个合法的序列为长度为N,每个元素的取值为[1,10]的整数序列,序列满足其有四个下标x,y,z,w 使得a[x]+a[x+1]..a[y-1]=X,a[y]+a[y+1]+..a[z-1]=Y,a[z]+a[z+1]+.a[w]=Z 求合法序列个数...

2021-08-18

0 587

Codeforces 201D.Brand New Problem-状压dp

传送门题意：给出一个有n个字符串的匹配串，和m个有k个字符串的文本串，将匹配串进行全排列和文本串进行匹配，找到能全匹配成功的最小的逆序对数 n<=15,m<=10,k<=500000 Solution：通过哈希+map把字符串变成数字那么问题就转化成了把一个1到...

2021-08-18

0 354

BZOJ4197: [Noi2015]寿司晚宴-状压DP

传送门题意： n-1个数，分别为2~n，现从中取出若干数放入两个集合中，使A集合中所有数都和B集合中的所有数互质，求满足条件的方案数。 n≤500 n ≤ 500 Solution: 根据题意，在一个集合中选择一个数相当于选择了这个数的质因子集合，所以说两个集合的质因子集合的交集必...

2021-08-18

0 337

BZOJ 3925:[Zjoi2015]地震后的幻想乡-状压DP

传送门题意：给定一个n点m边的无向图，没有重边和自环，每条边的权值为 [0,1] [ 0 , 1 ] 之间的随机变量，求最小生成树中最大边的期望权值。 n≤10,m≤n(n−1)2 n ≤ 10 , m ≤ n ( n − 1 ) 2 Solution: 题意其实可以转化为选...

2021-08-18

0 506

BZOJ2669: [cqoi2012]局部极小值-状压DP+容斥

传送门题意: 有一个n行m列的整数矩阵，其中1到 n∗m n ∗ m 之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。给出所有局部极小值的位置，判断有多少个可能的矩阵。 (1≤n≤4,1≤m≤7) ( 1 ≤ n ...

2021-08-18

0 342

BZOJ2734: [HNOI2012]集合选数-状压DP

传送门题意：给出n，求出 { 1,...,n} { 1 , . . . , n } 的所有满足以下条件的子集数量：若 x 在该子集中，则 2x 和 3x 不能在该子集中。 n≤100000 n ≤ 100000 Solution: 没见过类似做法的人见到这道题...

2021-08-18

0 265