abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ J2468 【地图】

发表于 更新于

Description

给出一个 $n \times n$ 的矩阵，如下图。

其中 $a_i$ 的值为 0 或者为 1。$c_i$ 表示第 $i$ 列和第 $n$ 列里面全部 $a$ 的异或和，$r_i$ 表示的是第 $i$ 行和第 $n$ 行全部 $a$ 的异或和。

现在这个矩阵里有一个数字错了，你能找出来吗？

Solution

分类讨论好题……

分九类来讨论即可，被 lxl 叉了三次以后总算 A 掉了这题……

事实上这题有个简单的做法，具体可以参见 Code 部分的第二份代码。

Code

  • By abcdeffa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#define maxN 2010
int r[maxN], c[maxN];
int a[maxN][maxN];
int main ()
{
	int n = 0, x = 0, y = 0;
	scanf("%d %d", &n, &x);
	if(x)
	{
		printf("1 1");
		return 0;
	}
	for(int i = 2;i < n; i++)
	{
		scanf("%d", &c[i]);
	}
	scanf("%d", &a[1][n]);
	for(int i = 2;i <= n; i++)
	{
		if(i < n)
		{
			scanf("%d", &r[i]);
		}
		else
		{
			scanf("%d", &a[n][1]);
		}
		for(int j = 2;j <= n; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	int cnt = 0, cntX = 0, cntY = 0, posX = 0, posY = 0;
	for(int i = 2;i < n; i++)
	{
		x = 0, y = 0;
		for(int p = 1;p <= n; p++)
		{
			x ^= a[p][i] ^ a[p][n];
			y ^= a[i][p] ^ a[n][p];
		}
		if(x != c[i])
		{
			cnt++;
			posX = i, cntX++;
		}
		if(y != r[i])
		{
			cnt++;
			posY = i, cntY++;
		}
	}
	if(cnt == 2 && posX && posY)
	{
		printf("%d %d", posY, posX);
	}
	else if(cntX == n - 2 && cntY <= 1)
	{
		if(!cntY)
		{
			printf("%d %d", 1, n);
		}
		else
		{
			printf("%d %d", posY, n);
		}
	}
	else if(cntY == n - 2 && cntX <= 1)
	{
		if(!cntX)
		{
			printf("%d %d", n, 1);
		}
		else
		{
			printf("%d %d", n, posX);
		}
	}
	else if(cntX == 1 && !cntY)
	{
		printf("%d %d", 1, posX);
	}
	else if(cntY == 1 && !cntX)
	{
		printf("%d %d", posY, 1);
	}
	else
	{
		printf("%d %d", n, n);
	}
	return 0;
}
  • By lxl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#pragma GCC optimize ("Ofast")
#include<cstdio>
char buf[16777216];
inline int Read()
{
	static char* c = buf;
	while (*c < '0' || *c>'9')
	{
		++c;
	}
	int ans = *c ^ 48;
	while (*(++c) >= '0' && *c <= '9')
	{
		ans = ans * 10 + (*c ^ 48);
	}
	return ans;
}
int a[2002][2002];
int main()
{
	fread(buf, 1, 16777216, stdin);
	const int n = Read();
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			a[i][j] = Read();
			a[i][0] ^= a[i][j];
			a[0][j] ^= a[i][j];
		}
	}
	int col = 1, line = 1;
	for (int i = 2; i < n; ++i)
	{
		if ((a[i][0] ^ a[n][0]) != 0)
		{
			col = (col == 1 ? i : n);
		}
		if ((a[0][i] ^ a[0][n]) != 0)
		{
			line = (line == 1 ? i : n);
		}
	}
	printf("%d %d", col, line);
	return 0;
}