codeforces 1332D - Walk on Matrix（构造，位运算）
题目大意：
有一个迷宫，小明从左上角可以走到右下角。每次小明走到一个格子，他都可以得到小明当前的分数 按位与 本个格子数字之后的分数。小明初始拿着的分数是：左上角的格子的数。现在有一位参赛者写了一个这样的dp：
很快参赛者bob发现了他的dp是有问题的，现在让你构造一个迷宫，使得bob的dp的输出和最优输出相差k.
k<=1e5. 注意，迷宫里的数字不能超过3e5.
解题思路：
首先，我们必须意识到bob的dp哪里有问题，其实问题就在于bob每一步dp都是贪心取的上一步最优来转移，但其实这在按位与的场景里面是不对的，我们有可能需要的次优的选择来达到全局最优。比如从二进制来看：
假如前一步我们选择了一个更大的数字1,0000 但是很可能我们这一步走的时候遇到了1001. 这样1,0000 & 1001 = 0.
但假如我们前一步选择了次优 1001 那么我们这一步遇到了1001 就会得到一个更优的选项 1001 & 1001 = 1001.
假如，没听懂的话，我们下一步构造就应该了解了。考虑构造这样的一个解：
假设cnt为k的二进制表示的长度.
那么按照bob的走法，输出为0
按照次优的解法输出为k：
比赛的时候m移成了(cnt+1)位，还一直没看出来.....
#include
#define int long long
using namespace std;
int32_t main(){
int k;cin>>k;
int tmp=k;
int cnt=0;
while(tmp){
tmp>>=1;
cnt++;
}
int most=(1<<(cnt))+k;
cout<<3<<" "<<4<<endl;
cout<<most<<" "<<k<<" "<<most<<" "<<0<<endl;
cout<<(1<<(cnt) )<<" "<<0<<" "<<most<<" "<< 0<<endl;
cout<<most<<" "<<most<<" "<<most<<" "<<k<<endl;
return 0;
}
作者：FrostMonarch
