【日常小测】二维数组

  • 本文为博主原创，未经许可不得转载

测试时，我的想法是把相邻的矩形之间连一条边，然后在图上做四分图染色

但是四分图染色不是NPC问题吗？

然后我就gg了

其实我注意到了矩形的长宽都是奇数，但没有想出怎么用这个条件

正解的做法就是按照矩形的奇偶性分组，可以证明同一组中的矩形一定不相邻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n=read();
	for(int i=1;i<=n;++i){
		int x=read(),y=read(),l=read(),r=read();
		if((x&1)&&(y&1))  puts("0");
		else if((x&1)&&!(y&1))  puts("1");
		else if(!(x&1)&&(y&1))  puts("2");
		else puts("3");
	}
	return 0;
}

本文标题:【日常小测】二维数组

文章作者:chty

发布时间:2017年04月06日 - 19时33分

最后更新:2018年07月25日 - 21时31分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,