Karp的21个NPC问题和部分证明

问题 1. SAT问题 问题P为若干个子句的逻辑与,每个子句是若干变量的逻辑或(P是合取范式/CNF),问是否存在一组输入,使得P为真。 根据对偶性,这一问题可以表述为:命题S是若干子句的逻辑或,每个子句是若干变量的逻辑与(S是析取范式/DNF),问S是否为恒真命题。 2. 01整数规划 给定整数矩阵C和整数向量d,问是否存在01向量x使得. 注:似乎Karp原论文中此处把“大于等于”误为“等于”: https://cs.stackexchange.com/questions/19716/0-1-integer-programming-and-karps-reduction SAT问题(合取范... 查看更多

[CCPC2015][HDU5548]Mahjong解题报告

题目 http://acm.hdu.edu.cn/showproblem.php?pid=5548 中文翻译版:http://cogs.pro/cogs/problem/problem.php?pid=2555 给定点数为1~K的麻将牌各4张(这4张完全相同),问有多少种方案,从中选出一个M张牌组成的集合,能够和牌。“和牌”指:其中有两张完全相同的将牌,其他牌可以被三三分组,每组要么是“n-1 n n+1”型,要么是“n n n”型。注意:集合相同而和法不同仅算一次。 题解 我们考虑这样一个命题:如果给定一个集合,能否和牌。这是一个很简单的DP:大致是:f={0,1},其中i是到了... 查看更多

CF 461D Appleman and Complicated Task解题报告

题目 http://codeforces.com/contest/461/problem/D 给你一个n*n网格,每一格要么是0要么是1要么为空,要求你用0或1填满所有空格,使得每个格子周围的0有偶数个。 题解 首先我们观察到这样一个事实:当第一行确定后,整个网格的填法就确定了。我们以N=8为例,把这种确定方法列出来:其中,“0246”这样的数的含义为,假设第一行为a,它表示该格的值是a xor a xor a xor a. 可以发现,这个形式是很规整的。都是“246”或者“1357”这种,连续的奇/偶数。 因此,我们的问题就变成了:问有多少种a的取值,满足K组形如a... 查看更多

CF 449E Jzzhu and Squares解题报告

题目大意 http://codeforces.com/contest/449/problem/E 给定一个N*M的网格。对一个顶点为格点的正方形R(不一定与格线平行),计算出其中有多少个单位格被R完全包含(记作F(R))。求所有正方形的F(R)之和。 题解 首先画一个“勾股图”: 粉色是我们的正方形(不和格线平行),设其外接正方形的边长为L,四周直角三角形的短边为a,则长边为L-a。设其中完整包含了F(L,a)个单位格。 可以发现,其中完全包含的单位正方形分成两部分:第一部分是中间小正方形里的个,第二部分是周边直角三角形里包含的。 我们这么计算第二部分:一红一白两... 查看更多