高度由习惯堆积

分类 技巧:容斥原理 下的文章

BZOJ2669 局部极小值

题目有一个n行m列的整数矩阵,其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子(相邻是指有公共边或公共顶点)都小,我们说这个格子是局部极小值。给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。思路看到数据范围马上想到状压dp。先分析状态数,会发现局部极小值在一张图中最多只有8个,所以状态为已经实现了哪些局部极小值。$dp[i][S]$为已经填完数$[1,i]$,满...
February 17, 2019

HDU5468 Puzzled Elena(dfs序+容斥原理)好题

题目给定一棵以1为根的树,求每个节点对应的子树中有多少个节点权值与它互质。思路首先要预处理出所有的数的质因子。很容易想到,一棵子树里与根节点互质的点的个数是多于与根节点不互质的点的个数的,所以,我们可以计算与根节点不互质的点,最后用子树的大小减一下。然而如何计算呢?题目中有关于使用容斥原理的提示,但是对于一棵子树来说,单独开辟空间存储一个质因子出现了几次显然会爆内存,于是要使用dfs作差。在...