这篇分享并不是关于如何求解“蒙德里安的梦想”这道题目,而是列出了我在写这道题目时所犯过的错误。
符号优先级的错误
- 算数运算符,如+,-,*,\,的优先级是大于移位运算符的优先级的。
因此如下代码会导致MLE(Memory Limit Exceeded)
我们的本意是想定义一个大小为$N * ((1 << N) + 10)$的数组,因为没有考虑运算符优先级的问题,所以出现了错误。
const int N = 12,M = 1 << N;
long long dp[N][1 << N + 10];//第一维表示列,第二维表示每一列的状态
bool st[1 << N + 10];
- 相等运算符的优先级高于位于(&)、位或(|)、位异或(^)的优先级。在如下代码中,我们的本意是想判断
j & k
的值,然后再判断(j & k) == 0
,但是由于相等运算符的优先级更高,下面的代码先判断k == 0
,之后执行j & (k == 0)
,从而导致输出为0
if( (j & k == 0) && st[j | k] )
求解有效状态的错误
为了缩短运行时间,我预处理出了在11位条件下所有的有效状态。之后我发现这是不正确的。因为对于同一个数字来说,位数不同,它是否是有效状态的结果也不同。比如4,在位数为3的时候,它的二进制表示是100,是有效状态,但是当位数变为4,它的二进制表示是0100,它就是非法状态。
以后会持续更新