异或矩阵

NC232602. 异或矩阵

描述

给定 $n,m$ ，表示矩阵大小。

矩阵中第 $i$ 行第 $j$ 列的数为 $(i-1)\times m+j$ 。

求异或和最大的子矩形，并构造方案。

输入描述

一行两个正整数 。

输出描述

第一行一个正整数，表示异或和最大的子矩形的异或值。

第二行四个正整数 ，满足  表示矩形的左上角为 ，右下角为 。

示例1

输入:

3 4

输出:

15
1 3 3 3

说明:

$n=3,m=4$ 时，矩形为：

$1~~~2~~~\color\red3~~~4$
$5~~~6~~~\color\red7~~~8$
$9~~10~~\color\red{11}~~12$

加粗的数字表示被选中的数字，这里 $3\oplus7\oplus11=15$ ，可以发现没有更优的选择

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 6ms, 内存消耗: 456K, 提交时间: 2022-03-17 12:23:51

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll n,m;
	scanf("%lld%lld",&n,&m);
	ll t=1;
	while(t*2<=n*m)t*=2;	
	int x=(t-1)/m+1,y=t-(x-1)*m;
	if(y!=1)printf("%lld\n%d %d %d %d",2*t-1,x,y-1,x,y);
	else
	{
		if(x==1&&y==1)printf("1\n1 1 1 1");
		else printf("%lld\n%d %d %d %d\n",2*t-1,x-1,1+m/2,x,1+m/2);
	}
    return  0;
}

上一题

下一题

详情