欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #630 (Div. 2) D. Walk on Matrix(思维+构造)

程序员文章站 2022-04-27 11:35:50
...

题目链接
Codeforces Round #630 (Div. 2) D. Walk on Matrix(思维+构造)
Codeforces Round #630 (Div. 2) D. Walk on Matrix(思维+构造)
思路:又是个掉分场,比赛时思维转的实在太慢QAQ。最后30s过的,好像大佬们有别的构造方法,这里就写一下自己的。一开始太纠结怎么改这个dp伪代码浪费了太多时间,其实要想差值为k,我们就想想是否可以构造一个按照伪代码的思路求出来的是0,正常的最大值是k的矩阵不就行了?那怎么构造呢?我们发现这么个东西,(maxx^k)&k,其中maxn是个很大的数(我这里是1<<18-1),你会发现(maxx ^k)&k的值就是0,所以我们假象最后的结果就是:
??maxn ^k
? maxn^k k
于是剩下来的就是如果让(1,1)^(1,2) ^ (1,3)和(1,1) ^(2,1) ^(2,2)都等于maxn ^k,其实很简单为了方便我们设置一个极限就是maxn(因为它都是1111.。。。,所以与操作后永远都是另一个数),我们就在中间也就是(1,2)这个位置放maxn ^k,其他都是maxn就行了,最后答案就是:
maxn maxn^k maxn
k maxn k

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<18)-1;
vector<int>v[1001],ans,g[1001];
int num[maxn],a[maxn],p[maxn],val[maxn],vis[maxn];
int main()
{

ll k;
cin>>k;
	ll dp[4][4];
	memset(dp,0,sizeof(dp));
	dp[1][2]=maxn^k;
	dp[2][3]=dp[0][3]=dp[2][1]=k;
	cout<<2<<" "<<3<<endl;
	for(int i=1;i<=2;++i)
	{
			for(int j=1;j<=3;++j)
	{
			if(dp[i][j]==0) cout<<maxn<<" ";
	else cout<<dp[i][j]<<" ";
	}
	cout<<endl;
	}


}
相关标签: 构造