HDU 5838 Mountain

Posted on By 二价氢

http://acm.hdu.edu.cn/showproblem.php?pid=5838

题目大意

给你一个的矩阵,你要往里面填入1~25的数,同时有且仅有某些给定的格子为8联通块极小值,询问有多少种填数方案。

思路及做法

注意到最多只有不超过9个格子为区间极小值,给予这种情况,同时注意到如果已经按顺序填入了某些数,那么我接下来能够在那些格子填数,只和已知的区间极小值格子是否填入了数字有关,而与它们具体填了哪些数无关。

剩下的东西别人的题解讲得挺清楚的我想睡觉就不写下去了,反正用表示填了前个数,已知的最小值的点的状态可以表示为,然后发现要满足有且仅有的条件,这时候容斥一下就好了。

AC-Code (C++)

Time 374MS, Memory 2836K

https://github.com/erjiaqing/my_solutions/blob/master/hdu/5838.cpp