CodeForces 1332D Walk on Matrix

题意

$Bob$想解决一个问题：一个$n\cdot m$的矩阵，从$(1,1)$出发，只能走右和下，问从$(1,1)$到$(n,m)$的最大$\&$和

他的算法如下($C++$)

memset(dp, 0, sizeof(dp));
dp[0][1] = a[1][1];
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        dp[i][j] = max(dp[i - 1][j] & a[i][j], dp[i][j - 1] & a[i][j]);
    }
}
cout << dp[n][m];

已知他的算法并不能得到最大的$\&$和

给定一个$k$，请构造出一个$n\cdot m$的矩阵，使得最大$\&$和比他的代码得出的答案大$k$

$1\leq n,m\leq 500$

$0\leq a_{i,j}\leq 3\cdot 10^5$

$0\leq k\leq 10^5$

分析

既然要针对$Bob$的算法进行构造，那么肯定要知道他的算法错在哪里（知己知彼，百战百胜）

我们将第二个样例的矩阵作为输入，得到$Bob$的答案，发现是$2$，在答案路径中，$(3,4)$前的节点是$(3,3)$

我们输出$dp[3][3]$发现是$4$，但是在答案路径中，走到$(3,3)$时是$3$，大概清楚了$\&$和并不能进行贪心

且可以模仿样例在答案路径中放入一个另一个更大的$\&$值

我们考虑能否直接构造矩阵使得答案是$k$，使得$Bob$的代码得到$0$

首先考虑二维矩阵，发现$(2,2)$是的确是挑最大的$\&$和，无法构造

我们看到第二个样例是$3\cdot 4$的矩阵，我们考虑能否构造出一个$2*3$的矩阵

考虑设计两个路径

$(1,1)->(1,2)->(2,2)->(2,3)$
$(1,1)->(2,1)->(2,2)->(2,3)$

通过样例得到灵感，第二条路径得到的$(2,2)$中的答案比第一条路径中大，但是不满足条件

那么思考如果\&$要大，不妨在$k$的二进制前面加上一个$’1’$，如果第二条路径要大，可以在$k$取反后前面在加一个$’1’$

我们直接设计$a[2][3]=k$，我们看数据范围看到$a[i][j]$的最大值可以为$3\cdot k$，考虑如下构造：

将$k$变为$2$进制，设字符串为$s$，将其各位取反得到字符串$s1$

构造$2\cdot 3$矩阵：

$(‘1’+s)$ $(s)$ $(0)$

$(‘1’+s1)$ $(‘1’+s)$ $(s)$

然后将其转换为十进制即可

路径一我们可以直接忽略$s$前面的$1$直接得到答案$k$

路径二我们发现走到$(2,2)$时，答案是$s$前面的$1$，那么这个和$(2,3)$的值$\&$一定是$0$

取反也可以用^，但写代码时没考虑那么多

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int k;
int a[30];

signed main() {
    start;
    cout << 2 << ' ' << 3 << '\n';
    cin >> k;
    int maxx = 0;
    for (int i = 0; i < 30; ++i) {
        if (k & (1 << i))
            a[i] = 1, maxx = i;
        else
            a[i] = 0;
    }
    cout << k + (1 << (maxx + 1)) << ' ' << k << ' ' << 0 << '\n';
    int ans = (1 << (maxx + 1));
    for (int i = maxx; i >= 0; --i) {
        if (!a[i])
            ans += (1 << i);
    }
    cout << ans << ' ' << k + (1 << (maxx + 1));
    cout << ' ';
    cout << k;
    return 0;
}

废话好多，构造还是思路重要，所以大部分篇幅都用来讲思路