题目翻译
题目给我们一个n * n的矩阵，矩阵中的每个格子都是四联通的，有个小偷初始位于（0，0）要在这个矩阵中偷盗，我们有报警器，小偷每次经过报警器的数值都会异或上小偷经过的路径的长度，报警器的初始数值为0。当小偷进行盗窃时报警器会告诉我们数值并且将报警器数值重置为0，我们需要根据这个数值输出小偷具体的坐标。我们需要构造每个格子之间的距离，输出构造方案并完成交互，格子距离的和不可以超过48000。
思路
首先我们意识到我们要根据报警器确定小偷经过任何路径走到[x, y]的坐标，意味着从[0, 0]走到[x, y]的所有路径的边权异或和都是相同的，我们可以给每个坐标赋一个边权异或和的值，然后根据这个值我们就可以反推出所有的路径长度。我们首先想到可以令值为0到n * n，但是构造之后我们发现此时的边权和到达了1e5的级别，超出了限制。
我们注意到两个坐标的权值之间我们应该让其具备尽可能多的相同的位，这样我们就可以最小化边权的和。如果是一维的坐标问题，那么显然格雷码就是答案，其保证了每个元素不同且相邻两个元素之间只有1个位不相同，并且保证了使更低位的不同次数更多。我们发现如果可以将格雷码拓展到二维那么我们就可以解决这个问题了，数据范围n <= 32,我们只要构造32即可。对于2 ^ k阶的二维格雷码我们类比一维各类码的拓展方式将二维各类码拓展出来，具体的对于[2 ^ k , 2 ^ k]的二维格雷码，我们先将其拓展成[2 ^ k, 2 ^ (k + 1)],在拓展成[2 ^ (k + 1), 2 ^ (k + 1)],对于同列和同行的拓展和一维格雷码相同，我们先赋值一遍翻转后放置原先的后面，并将新添加的码值的新的最高位全部赋值成1。
构造方案出来后我们维护小偷走过的边权异或和即可。
代码
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
| std::vector<std::vector<int>> val;
void init(){
val.assign(2, std::vector<int>(2, 0));
auto change = [&](){
int x = std::__lg((val.size() - 1) * (val[1].size() - 1) - 1) + 1;
for(int i = 1; i < val.size(); i++){
for(int j = val[i].size() - 1; j >= 1; j--){
val[i].push_back(val[i][j]);
val[i].back() |= (1 << x);
}
}
x += 1;
int sz = val.size() - 1;
for(int i = 1; i <= sz; i++)
val.push_back({0});
for(int j = 1; j < val[1].size(); j++){
int str = sz + 1;
for(int i = sz; i >= 1; i--){
val[str].push_back(val[i][j]);
val[str].back() |= (1 << x);
str += 1;
}
}
};
int N = 32;
while(val.size() < N){
change();
}
}
void solve(){
int n, k;
std::cin >> n >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j < n; j++){
std::cout << (val[i][j] ^ val[i][j + 1]);
if(j == n - 1)
std::cout << std::endl;
else
std::cout << space;
}
}
for(int i = 1; i < n; i++){
for(int j = 1; j <= n; j++){
std::cout << (val[i][j] ^ val[i + 1][j]);
if(j == n)
std::cout << std::endl;
else
std::cout << space;
}
}
int now = 0;
while(k--){
int x;
std::cin >> x;
now ^= x;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(val[i][j] == now){
std::cout << i << space << j << std::endl;
}
}
}
}
}
|
