官方教你 Hack 系列

题目链接：CF1332D 【Walk on Matrix】

题意：

对于题目：

“给定一个 $n \times m$ 的矩阵，一开始你在 $(1,1)$，手上的数值为 $a_{i,j}$，现在你可以往下或者往右，一直走到 $(n,m)$ 。你每走到一个新的点 $(x,y)$，手上的数就会变成：手上的数 $AND$ $a_{x,y}$，需要你最大化走到 $(n,m)$ 时手上的数字。”

现在 $\texttt{Bob}$ 写了一个 $\texttt{dp}$ 来解决这个问题：

照着以上的规则写成代码是这样的：

//Code By Bob
#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int MAXN = 510;
const int INF = 2e9;
const int mod = 1e9 + 7;

int n,m;
int a[MAXN][MAXN],dp[MAXN][MAXN];

signed main () {
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n; ++i)
        for(register int j = 1;j <= m; ++j)
            scanf("%d",&a[i][j]);
    memset(dp,0x3f,sizeof dp);
    dp[0][1] = a[1][1];
    for(register int i = 1;i <= n; ++i)
        for(register int j = 1;j <= m; ++j)
            dp[i][j] = max((dp[i - 1][j] & a[i][j]),(dp[i][j - 1] & a[i][j]));
    printf("%d\n",dp[n][m]);
    return 0;
}

但是这个算法是假的，所以现在要你来 $\texttt{Hack}$ 他。

具体地，题目给定你一个 $k$ ，要求你输出一个 $n \times m$ 的矩阵 $(1 \le n,m \le 500,\forall \ 0 \le a_{i,j} \le 10^5)$

并且以上的 $\texttt{dp}$ 的答案与实际的最大值之差恰好为 $k$

题意终于讲完了

首先考虑一下以上的 $\texttt{dp}$ 错在哪里

我们发现对于 $\texttt{AND}$，也就是 按位与 操作，不见得一个最大的数字与上某个特定的数字就是最大的，例如：

100000 & 1 = 0 , 1 & 1 = 1

为什么呢？因为不见得大的数字就会和这个特定数字有更多的同为 $1$ 的二进制位

这个应该很显然

那么我们考虑根据这个东西来 $\texttt{Hack}$ 他

我们考虑 “骗” 这个 $\texttt{dp}$，让他选择一个看似更大的答案，最后把这个答案给卡掉，就可以让 $\texttt{dp}$ 的答案为 $0$，最后让这个方案的真正答案为 $k$，差值就是 $k$ 了。

我们发现 $k_{max} < 2^{17} < 10^5$，那么也就是说，如果我们令一个值为 $2^{17}+k$，那么 $2^{17}$ 和 $k$ 的二进制位是不会相互影响的，也就是不发生进位的，或者说 $k\ \&\ 2^{17} = 0$。

这很好，因为这样就让题目变得非常简单了，我们可以构造以下这个矩阵：

$$n=2,m=3$$

$$\begin{bmatrix} 2^{17}+k & 2^{17} & 0\\ k & 2^{17}+k & k \end{bmatrix}$$

就可以完美解决这个问题了

为什么？

我们可以一步一步看这个矩阵，首先显然的，我们不会走到 $(1,3)$，因此我们迫使$(1,1)\rightarrow (n,m)$ 的走法只有两种：走 $(1,2)$ 或者 $(2,1)$

我们发现 $dp[1][2]=2^{17},dp[2][1] = k$

那为什么 $(2,2)$ 这个位置放的又是 $2^{17}+k$ ？

因为这样能够保证 $dp[2][2]$ 从 $dp[1][2]$ 取值，这样就进入了我们的圈套

最后 $(2,3)$ 再放一个 $k$，此时的 $dp[2][2]=2^{17}$，$dp[2][3]$ 又只能从 $dp[2][2]$ 取值，所以我们就成功让 $\texttt{dp}$ 输出了 $0$

这时我们发现 $\texttt{dp}$ 选择的是走 $(1,2)$ 那一边，并且不难发现如果走 $(2,1)$，答案就恰好为 $k$ 了

因此 $\texttt{dp}$ 答案与正确答案的差值正好就是 $k$ 了

注意：本菜鸡一开始写得是 $2^{18}+k$，但是当 $k$ 取最大值 $10^5$ 时，$2^{18}+10^5$ 是超过了 $a_{i,j}$ 的限制 $3 \times 10^5$ 的，注意一下即可

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define int long long

int k;

signed main () {
    scanf("%d",&k);
    printf("%d %d\n",2,3);
    printf("%d %d %d\n",(1 << 17) + k,(1 << 17),0);
    printf("%d %d %d\n",k,(1 << 17) + k,k);
    return 0;//End.
}

代码很简单，不过这题我吹爆 真的好玩

初三的 $\texttt{OIer}$，请多关照