CodeForces - 1332D Walk on Matrix(构造)

题目链接：点击查看

题目大意：给出一个错误的dp程序，目的是为了求从点 ( 1 , 1 ) 到点 ( n , m ) 只能向下移动或向右移动，找出一条路径，使得 与运算 的结果最大，给出一个 k ，构造出正确答案与错误dp答案相差恰好为 k 时的一个矩阵

题目分析：首先要明白为什么题目给出的dp是错误的，乍一看其实没什么错误，但是仔细想一下，题目维护的dp是局部最大值，而对于位运算来说，局部最大值不一定能推出全局最大值的，举个很简单的例子，如果同时要和 3 进行 与运算 ，4 & 3 = 0，但 3 & 3 = 3，这样看来显然题目给出的dp无法求出全局最大值

到这里如果直接构造的话实际上难度是非常大的，但这个题目很良心的给出了样例二，我们只需要对于样例二稍微分析一下就能提取出构造的核心

样例二的 k 为 1 ，给出的答案为：

3 4

7 3 3 1

4 8 3 6

7 7 7 3

而dp矩阵为：

7 3 3 1

4 0 3 2

4 4 4 2

提示中也说了，最终答案应该是 3 ，而不是程序给出的 2 ，问题就出在了第 ( 3 , 3 ) 这一格上，本来应该将答案 3 一直下传的，但是到了第 ( 3 , 3 ) 这里，被一个较大的数给冲掉了，使得 3 & 4 = 0 ，故最终答案只能是 2 & 3 = 2 了

有了上面样例的提示，我们就知道了，应该在 ( 1 , 1 ) 处兵分两路，一路维护全局最大值，一路维护局部最大值，最后在 ( n , m ) 前一格汇合，最后在 ( n , m ) 这一格使得全局最大值与 a[ n ][ m ] 运算后的答案为 0 ，而实际最大值为 k 即可

最后放一下官方题解的构造方案吧：

这个矩阵从 ( 1 , 1 ) 到 ( 2 , 2 ) 只有两条路，( 1 , 1 ) -> ( 1 , 2 ) -> ( 2 , 2 ) 维护的是 2^17，另一条路维护的是 k ，显然 dp[ 2 ][ 2 ] 的值应该是 2^17 ，最后与 k 异或一下，会发现错误的dp的答案为 0 ，而实际上的答案为 k

非常巧妙的一道题

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int k;int num=1<<17;scanf("%d",&k);printf("2 3\n");printf("%d %d %d\n",num+k,num,0);printf("%d %d %d\n",k,num+k,k);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1332D Walk on Matrix(构造)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。