题解 P4067 【[SDOI2016]储能表】

2019-01-07 07:58:46


首先拆式子,变成 $\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}f(i,j)-k\times\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}[f(i,j)]$

设 $f[i][0/1][0/1][0/1]$ 表示第 $i$ 位, $n$ 是否到了上界, $m$ 是否到了上界, $k$ 是否到了上界。

然后用一个pair来当返回值,两部分同时转移。

具体就是枚举 $n$ 和 $m$ ,然后异或算出 $k$ 。看代码应该就能懂了qwq


血的教训: $long\ long$ 左移一定要写成 $1ll<<x$ ,如果写成 $1<<x$ 会 $\color{red}{\text{WA}}$ !


代码见blog