【题解】CF1332D Walk on Matrix

官方教你 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}$,请多关照

添加新评论