Codeforces 1332 D. Walk on Matrix（构造矩阵）

怎么构造呢?

\(首先我们不可能去构造一个2000*2000的矩阵，那太复杂了\)

\(也许我们可以看看2*2的矩阵??\)

\[\left[
\begin{matrix}
x&y\\
z&q\\
\end{matrix}
\right]
\]

\(但是在这个矩阵中，小明的算法不可能出错。因为到达y和z的值固定，取个最大值一定是对的。\)

\(那就2*3的矩阵\)

\[\left[
\begin{matrix}
x&y&z\\
q&w&e
\end{matrix}
\right]
\]

\(同理知道算法出错，一定是在w的时候应该取最小而不是最大。(只有w有选择的方式)\)

令\(ans=(1<<17),然后我们想办法把正确的算法构造成K，小明的算法构造成0.\)

构造的其中一个是(这个就感性理解吧，有很多，全靠自己构造)

\[\left[
\begin{matrix}
ans+k&ans&0\\
k&ans+k&k
\end{matrix}
\right]
\]

#include <bits/stdc++.h>

using namespace std;

int k;

int main()

{

	cin>>k;

	long long ans=(1<<17);

	cout<<2<<" "<<3<<endl;

	cout<<ans+k<<" "<<ans<<" "<<0<<endl;

	cout<<k<<" "<<ans+k<<" "<<k<<endl;

	return 0;

}

巴特西

Codeforces 1332 D. Walk on Matrix（构造矩阵）

最新文章

热门文章