首页 > 代码库 > 总结2

总结2

                        一周总结

状态压缩:

状态压缩无论是有关于图的遍历的还是图形和物体的放置的,都可归结于一类问题,那就是排列问题即先算谁的问题。

如:hdu 4295 题意说将4个子串放入一个主串中,使得覆盖的字符数最大和最小。此题先预处理每个子串可在主串中放的位置pos[i][j]

kmp字符串匹配算法解决,接着就是状态转移。有两种状态:

1.在主串位置i中不计子串。f[i+1][j-1][k]=min(f[i+1][j-1][k],f[i][j][k])

2.在主串位置i能计子串时,而该子串未放时计算字串p=max(j,len[x])

f[i+1][p][k|(1<<x)]=min(f[i+1][p][(1<<x)]+f[i][j][k]+p-j);

状态转移方程f[i][j][k] 表示当在i位置时向右延伸了j个串时状态为k时的最小覆盖字符数

Hdu 4284 图类型的题,即是先走那个的题

lightOJ 1270 即是用6个不同形状的图形组成一个矩形求方案数,

也是先选和后选的问题

Hdu 3274   自动机+状态dp

自动机用于预处理,串之间匹配度的距离,然后状态转移就行了

Hdu 3001  因为每个点至多可以遍历两次,所以三进制状态压缩,要模拟三进制,用一个二维数组存,然后状态转移就行了。

Codeforce 453B 要记录路径。

 

 

容斥:

首先得明白这个公式:

 

 

先都求,然后再减去不满足条件的,奇加偶减

Hdu 4407 先给定一个序列1……n,然后有两种操作

1.改变某一位置上的数,

2.查询一定区间内的与一个数互质的数的和

思想是,先求出总的和,在减去不互质的数,对于修改的特殊处理,用gcd函数特判。不互质的数由p的质因子来决定,质因子数为偶数时加,为奇数时减(注:此处要减去不满足条件的,负负得正,故反了过来),最后特判变动的数就行了。

Hdu 4059  同样的容斥原理,因为要mod 同时还要除一个数30

要用扩展gcd,由除变乘实现/30,直接除不对

lightOJ 1095  错位排列

Hdu  4497 

对于容斥原理很多是和状态压缩结合到一块的,利用状态压缩找素数的个数和位置。实现减重。

 

图匹配:

对于图匹配,首先要有:最小路径覆盖,最小点覆盖,最大独立集

最大团的概念。

二分图来说,构图最重要。

Poj  1358 k个图每个图有字母和0组成 0代表空地,问每个图去掉同一个字母后要构成h*w的空地,如果某字母在上图被删的话,这个图中就不能再出现,求用多少个这样的区域。

把每个图预处理,删除一个字母能否构成h*w的区域,即为a[i][j]

然后匹配,求最大匹配就行了。

BZOJ 1059  求二分图的最大匹配,有点难想。

BZOJ 1143 求最大独立集=点数-最大匹配

BZOJ 2105 求最小路径覆盖=点数-最大匹配

BZOJ 3140 求最小顶点覆盖;

KM求最佳匹配