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

问题 1. SAT问题 问题P为若干个子句的逻辑与,每个子句是若干变量的逻辑或(P是合取范式/CNF),问是否存在一组输入,使得P为真。 根据对偶性,这一问题可以表述为:命题S是若干子句的逻辑或,每个子句是若干变量的逻辑与(S是析取范式/DNF),问S是否为恒真命题。 2. 01整数规划 给定整数矩阵C和整数向量d,问是否存在01向量x使得. 注:似乎Karp原论文中此处把“大于等于”误为“等于” … 继续阅读“Karp的21个NPC问题和部分证明”

ACM/ICPC乌鲁木齐2017解题报告

两位队友的博客: http://hzwer.com/ http://kuribohg.github.io/ BEH三题是我写的,其余题目鸣谢二位大腿。 A:Banana 开始样例错了。 代码:

B:Out-out control cars 题意:两个三角形匀速直线运动,问是否会撞上。 题解:只需单独计算每个三角形的某个顶点是否会和另 … 继续阅读“ACM/ICPC乌鲁木齐2017解题报告”

[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 … 继续阅读“[CCPC2015][HDU5548]Mahjong解题报告”

CF 461D Appleman and Complicated Task解题报告

题目 http://codeforces.com/contest/461/problem/D 给你一个n*n网格,每一格要么是0要么是1要么为空,要求你用0或1填满所有空格,使得每个格子周围的0有偶数个。 题解 首先我们观察到这样一个事实:当第一行确定后,整个网格的填法就确定了。我们以N=8为例,把这种确定方法列出来:其中,“0246”这样的数的含义为,假设第一行为a[0..7],它表示该格的值是 … 继续阅读“CF 461D Appleman and Complicated Task解题报告”

CF 449E Jzzhu and Squares解题报告

题目大意 http://codeforces.com/contest/449/problem/E 给定一个N*M的网格。对一个顶点为格点的正方形R(不一定与格线平行),计算出其中有多少个单位格被R完全包含(记作F(R))。求所有正方形的F(R)之和。 题解 首先画一个“勾股图”: 粉色是我们的正方形(不和格线平行),设其外接正方形的边长为L,四周直角三角形的短边为a,则长边为L-a。设其中完整包含 … 继续阅读“CF 449E Jzzhu and Squares解题报告”