codeforces-1332D-Walk on Matrix
传送门：https://codeforces.com/problemset/problem/1332/D
题意：有一个矩阵，每次可以向下或向右移动，把路径上的所有数都&起来，如果还是dp显然是错的。假设dp的到的结果是x，正确答案是y。
现在给定k，需要你构造一个矩阵，使得|y-x|=k
因为dp是错的，你就要找到他是哪里错了
我们可以看给出的样例
3 4 7 3 3 1 4 8 3 6 7 7 7 3
In the second example, the maximum score Bob can achieve is 7&3&3&3&7&3=3, while the output of his algorithm is 2.
模拟一下这个过程，我们把他转换为更为清晰的二进制
如图，橙色为dp路线，而根据样例给出的解释，红色才是正解，很明显，路线从第三行第三列开始偏了，那么我们就从这开始入手
他是怎么出错的呢？dp[3][3] 0111在面对0100和0011时选择了能让他与结果更大的0100，而他也变成了0100，在与0011进行与运算时答案变成了0
但如果是最优情况，他会与0011进行与运算变成0011，在与他的右面进行与运算变成0011=3
利用这个bug，我们就可以解题了，因为是要|y-x|=k，我们可以构造出dp情况=0，而正解为k的一个矩阵（准确的来讲，是这么一个拐角）
模拟上面的拐角，我们把拐角放到左下角，我们构造出的，长这样：
但是你模拟一下，发现不对，标橙的那个k跟上或左进行与运算后变成了0，然鹅我们要保证这个位置运算之后是k，而且那个111111不能变
别忘了11111111和任何数与运算都是它本身，所以蓝色部分应该变成1111111……
橙色两个数的位置也并不影响答案，换一下就行，11111……的10000……从上面传过来，k正好从左面传过来
它就变成了这样子
因为是自己决定矩阵的大小，我们发现，有用的只有灰色部分，那就只输出这部分就好了
还有就是位运算的优先级很低，能加括号的把括号都加上，还有规定a[i][j]最大是3e5，不能再往大了开了（wa了几发呢）
细节细节
上代码
1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 #define ll long long 5 int dp[5][5]; 6 int main() 7 { 8 memset(dp,0,sizeof(dp)); 9 int k; 10 scanf("%d",&k); 11 dp[1][1]=dp[2][2]=(1<<18)-1; 12 dp[1][2]=1<<17; 13 dp[2][1]=dp[2][3]=k; 14 puts("2 3"); 15 for(int i=1;i<=2;i++) 16 { 17 for(int j=1;j<=3;j++) printf("%d ",dp[i][j]); 18 printf(" "); 19 } 20 return 0; 21 }