CF1332 D. Walk on Matrix

题意

给你一个 $k(0\le k\le 105)$k(0≤k≤105)
要求你构造一个 $n\times m$n×m的矩阵满足下列条件

1. $1\le n,m\le 500$1≤n,m≤500
2. $0\le a_{i,j}\le 3\cdot 10^5$0≤ai,j​≤3⋅105
3. 由以上dp式子推出来的 $dp\left[n\right]\left[m\right]$dp[n][m]和真正路径最大位与相差k

思路

构造
首先这题是位于运算且和dp式子有关，我们可以将题目中的样例2转为二进制之后，去手动模拟一下为什么dp答案是错的?

我们发现 $d{p}_{3,3}$dp3,3​不一样导致了结果不一样，那么 $d{p}_{3,3}$dp3,3​为什么会不一样呢？
因为 $d{p}_{3,3}$dp3,3​取了 $d{p}_{3,2}$dp3,2​，那么为什么会这么取？
我们思考发现 $dp$dp的结果会取到大的数，但是这道题不能用dp做的原因在于这道题是有后效性的。我们前面选择了大的数，最终的结果不一定会是大的数。

说到这里再来复习一下 $dp$dp的条件：

1. 最优子结构性质： 由前面子问题的最优解可以推的后续子问题的最优解
2. 无后效性：前面的解怎么来的不会影响到后续的解
3. 子问题的重叠性： 可以把一个大规模的问题分为若干个小规模的问题，它们的本质是一样的。

我们思考一下如何构造相差k，为了简化问题，我们可以想办法让dp式子得出来的结果为0，那么只要再让路径最大位与的结果为k即可。
我们这里需要利用dp错误的原因在于他会优先取大的数，那我们就给他构造一个较大的数。

我们要取到k都能位与得到结果，?全部取1即可。

这样还是不够的，因为我们如果在 $a_{2,2}$a2,2​放入k，他会取左边的。

结合题目条件 $1\le n,m\le 500$1≤n,m≤500 $0\le a_{i,j}\le 3\cdot 10^5$0≤ai,j​≤3⋅105 $k(0\le k\le 105)$k(0≤k≤105)
我们确定数据范围 $2^{18}\approx 2.6e52^{17}\approx 1.3e52^{19}\approx 5.2e5$218≈2.6e5217≈1.3e5219≈5.2e5
我们发现若取 $2^{19}$219则超出a数组的范围，若取 $2^{17}$217则当k为1e5时会出现问题。
所以我们只能取2e18-1来构造。

推广

这道题如果再加深难度，就是构造一个要求长为n宽为m的一个矩阵，这时候应该再上面构造的基础上拓展成这样的形式

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int k;cin>>k;
	cout<<2<<" "<<3<<'\n';
	cout<<(1<<18)-1<<" "<<(1<<17)<<" "<<0<<'\n';
	cout<<k<<" "<<(1<<17)+k<<" "<<k<<'\n';
	return 0;
}