语言漩涡

thirtiseven 的博客

0%

Algorithmic Engagements 2009 Fishes 拓扑+最小表示法

Posted on Edited on

Fishes

题意

在遥远的群岛上，生活着一种罕见的食肉鱼。这些鱼的生活节奏非常有规律。每条鱼每天早上在同一时间醒来，然后去打猎。傍晚，它又回到出发的地方 每天同一时间在那里睡觉，但它可能会在不同的地方醒来，因为它可能会被洋流稍微移动。 在一整天中，鱼儿都会坚持以下规则：每时每刻它都要能看到前一天同一时间的位置，也就是说，正好是24小时之前。当然，鱼儿不可能看到任何岛屿对面的一个点。 鱼类学家对群岛中的鱼类进行了相当长时间的观察，每隔几天，他们就会记录一些鱼类所走的一条路线。不幸的是，在收集了大量的数据之后，发生了意外。现在有些数据已经丢失了，剩下的数据也完全乱了套。科学家甚至不知道他们记录的每条路线是哪条鱼走过的。他们向你寻求帮助。他们要给你一些乱七八糟的鱼群路线描述，并请你告诉他们在研究过程中观察到的不同鱼类的最小数量。

输入

输入包括两部分：群岛描述和鱼群路线描述。群岛描述的第一行包含两个整数，w 和 h（3≤w≤1000，3≤h≤1000），用一个空格隔开。在下面的每一行 h 中都有一个 w 字符长的字符串，描述群岛的一部分。字符.代表海洋，而#代表陆地。地图边界上的所有单元格中都是水。群岛中的一个点可以从另一个点看到当且仅当它们连线的任何部分都没有与陆地内部或边界的共同点，而与鱼儿游动的方向无关。 在下一行中，有一个整数 n（2≤n≤1000），指定了记录的鱼群路线的数量。下面的 2n 行包含了这些路线的描述。在路线描述的第一行中，有三个整数 x、y 和 d（1≤x≤w，1≤y≤h，2≤d≤10000），用单个空格隔开。数字x和y是鱼醒的地方的坐标（列和行），d 是路线的长度。第二行是一个长度为 d 的字符串，每个字符是 N、W、S 或 E，代表鱼的运动方向。它们分别代表上、左、下、右。路线保证只穿过含水的单元，鱼儿不会离开输入中描述的群岛片段，并且每条路线的终点都是在它开始的那个单元。 鱼儿只能水平或垂直游动；它沿着连接沿途格子中心的连线移动。然而，我们不知道它的速度。鱼可以加速或减速，以便始终看到它 24 小时前所占据的点。 洋流最多可以将一条沉睡的鱼从它睡觉的地方向上、向下、向左或向右移动一格。

输出

第一行输出一个整数k，代表与科学家收集的数据一致的不同鱼类的最小数量。

接下来 k 行，每一行都应该包含一条鱼的路线列表。鱼儿不一定需要在连续的日子里沿着这些路线游动，只需要在它生命中的任意两天这样游动就可以。一条鱼可以在连续的两天内走过两条路线，如果两条路线都是从同一个格子或相邻的格子(共用一个边缘)开始的，而且鱼可以沿着第二条路线游动，在任何时候都能看到它24小时前所处的位置。 根据它们在输入中的顺序，路线的编号从1到n。输出的每一行中的路线数应按递增顺序写出，各行的排序应使所有行中的第一个数字形成递增序列。

样例

For the input data:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
10 8 
.......... 
.......#.. 
........#. 
.......... 
...#...... 
......###. 
......###. 
..........
4
2 7 12
nnnEEEssswww
2 8 24
wnnnnnnnEEEEEssssssswwww
1 8 46 
nnnnnnnEEEEEsssssssEEEEnnnnnnnssssssswwwwwwwww 
1 8 32
nnnnnnnEEEEEEEEEssssssswwwwwwwww

the correct result is:

1
2
3
2
1 2 3
4

解释：前两条路线可能是同一条鱼走过的（可以是连续两天）。几天后，该鱼可能走了第三条路线。然而，最后一条路线一定是由另一条鱼走过的。与前三条路线不同的是，它是绕着大岛走的。

解法

这个题意就是说，一种鱼有基本固定捕食路线，路线的变化方式是：在捕食的任意时刻，鱼都必须要可以看到它恰好24小时前捕食的位置。看不到的意思是：鱼的目光可能会被一个岛屿挡住。给出群岛的地图和路线，求出有多少种本质不同的路线。

如果两条路线是等价的，那么这两条路线就可以连续形变为另一条路线。于是我们可以非常感性地认识到，两条路线等价当且仅当它们拓扑同伦。抄维基百科：拉数学中，同伦个概念拉拓扑上描述了两个对象间个“连续变化”。 拉拓扑学中，两个定义拉拓扑空间之间个连续函数，如果其中一个能“连续地形变”为另一个，则箇两个函数叫作同伦个。（逃

感性理解一下就是，如果把路线想象成一个橡皮筋，岛屿想象成钉子，那我画完路线之后松开手，等价的路线就会被钉子绷成相同的形状。（我对拓扑学的认识还处在橡皮筋和肥皂泡阶段，感觉急需学习一个）。

比如说，下面这个图可以表示为一条鱼在连续几天里面的路线变化，显然它们是拓扑同伦的。

Fishes1

但是下面这个图的两个路线，虽然都绕着两个岛绕了两圈，但是它们显然并不等价。

Fishes2

下面的问题就是怎么表示路线。题解里给了一个牛逼方法，就是把地图上横着的连续线段标号，当路线上下穿过这些线段时，我们就可以记录它当前以什么方向穿过了哪条线段。如下图所示：

Fishes3

对于上图中的例子，我们将得到以下的交点序列。

2s, 4s, 8s, 10s, 11s, 11n, 10n, 8n, 8s, 9n, 5n, 2n,

其中n或s表示鱼分别向北或向南游动。然后，我们就可以模拟橡皮筋收缩的过程，消掉相邻且数字相同标号相反的线段。就像下面这样。在实际写代码的时候，可以用一个栈来模拟，如果当前入栈的元素和栈顶元素标号相同方向相反，那么就可以把栈顶元素弹出。最后，再判断一下栈两边的元素是不是相等，相等的话就把两头都弹出来，循环执行这个操作。然后我没用pair，用的是 和 分别代表两个方向。显然，方向是需要考虑的。

  1. 2s, 4s, 8s, 10s, 11S, 11N, 10n, 8n, 8s, 9n, 5n, 2n,
  2. 2s,4s,8s,10S,10N,8n,8s,9n,5n,2n,
  3. 2s,4s,8S,8N,8s,9n,5n,2n,
  4. 2S,4s,8s,9n,5n,2N
  5. 4s，8s，9n，5n。

然后，要判断两条线路是否等价，只需要判断一下它们的表示是不是循环等价。一个 的暴力算法是显然的，一个 的基于KMP的判循环等价的算法也是显然的，但是题解给了一个最小表示法判循环等价的方法，我闻所未闻。但是我猜这个东西还是 well-known in China 字符串选手的。我是字符串废物我不会。找资料的时候有网友说用 Sa-is 就是那个 O(n) 的后缀数组也是可以做的，复杂度一样，我是字符串废物我也不会。最小表示法看了一下，好像很简单啊，然后糊了一个板子上去。它大概是长着个样子的：

1
2
3
4
5
6
7
8
9
10
11
int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
  if (sec[(i + k) % n] == sec[(j + k) % n]) {
    k++;
  } else {
    sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
    if (i == j) i++;
    k = 0;
  }
}
i = min(i, j);

然后我们有了最小表示法，就可以直接把它哈希一下，把哈希值和路线标号扔进一个哈希表，然后把结果拉出来排个序，就做完了，是不是很简单呢（

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <vector>
#include <unordered_map>

const int maxn = 1004;

int w, h;
std::string mp[maxn];
int label[maxn][maxn];
int n, x[maxn], y[maxn], d;
std::string route[maxn];
std::vector<int> represent[maxn];
std::unordered_map<unsigned int, std::vector<int>> hashmap; 
std::vector<std::vector<int>> ans;

void input() {
	std::cin >> w >> h;
	for (int i = 0; i < h; i++) {
		std::cin >> mp[i];
	}
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> x[i] >> y[i] >> d;
		std::cin >> route[i];
	}
}

void LMCE(int x) {
	int k = 0, i = 0, j = 1, len = represent[x].size();
	while (k < len && i < len && j < len) {
		if (represent[x][(i + k) % len] == represent[x][(j + k) % len]) {
			k++;
		} else {
			represent[x][(i + k) % len] > represent[x][(j + k) % len] ? i = i + k + 1 : j = j + k + 1;
			if (i == j) i++;
			k = 0;
		}
	}
	i = std::min(i, j);
	std::vector<int> temp(len);
	int cnt = 0;
	for (int ii = i; ii < len; ii++) {
		temp[cnt] = represent[x][ii];
		cnt++;
	}
	for (int ii = 0; ii < i; ii++) {
		temp[cnt] = represent[x][ii];
		cnt++;
	}
	for (int ii = 0; ii < len; ii++) {
		represent[x][ii] = temp[ii];
	}
}

unsigned int RSHash(int x) {
	unsigned int b = 378551;
	unsigned int a = 63689;
	unsigned int hash = 0;
	for (int i = 0; i < represent[x].size(); i++) {
		hash = hash * a + represent[x][i];
		a *= b;
	}
	return (hash & 0x7FFFFFFF);
}

void gao() {
	int cur = 1;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (mp[i][j] == '#') {
				label[i][j] = -1;
				cur++;
			} else {
				label[i][j] = cur;
			}
		}
		cur++;
	}
	for (int i = 0; i < n; i++) {
		int nowx = x[i]-1, nowy = y[i]-1;
		for (int j = 0; j < route[i].length(); j++) {
			if (route[i][j] == 'W') {
				nowx--;
			} else if (route[i][j] == 'E') {
				nowx++;
			} else if (route[i][j] == 'N') {
				nowy--;
				if (represent[i].empty() || represent[i].back()/2 != label[nowy][nowx]) {
					represent[i].push_back(label[nowy][nowx]*2);
				} else {
					represent[i].pop_back();
				}
			} else if (route[i][j] == 'S') {
				if (represent[i].empty() || represent[i].back()/2 != label[nowy][nowx]) {
					represent[i].push_back(label[nowy][nowx]*2+1);
				} else {
					represent[i].pop_back();
				}
				nowy++;
			}
		}
		while (represent[i].size() > 1 && represent[i].front()/2 == represent[i].back()/2) {
			represent[i].pop_back();
			represent[i].erase(represent[i].begin());
		}
		if (represent[i].size() == 0) {
			represent[i].push_back(0);
		}
		LMCE(i);
		hashmap[RSHash(i)].push_back(i+1);
	}
}

void output() {
	for (auto it: hashmap) {
		ans.push_back(it.second);
	}
	for (auto it: ans) {
		std::sort(it.begin(), it.end());
	}
	std::sort(ans.begin(), ans.end());
	std::cout << ans.size() << '\n';
	for (auto it: ans) {
		for (auto it2: it) {
			std::cout << it2 << ' ';
		}
		std::cout << '\n';
	}
}

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	input();
	gao();
	output();
}

吐槽

好题！

c++好，matlab坏

拓扑学怎么学啊，不会数学分析能学吗（（

一开始以为方向不重要，错了几发。但是一开始交上去wa了我还以为是因为卡了哈希。建议不要用哈希以便减轻自己的心理负担，基数排序也是可以的呢（

字符串怎么学啊，我在做这个题之前扪心自问：我到底会不会KMP，最后发现用不上KMP。看到最小表示法就是找字典序最小的后缀，我扪心自问，我到底会不会后缀数组，最后发现也没用上。我快乐了

一开始用了 stack，然后改成 deque，然后改成 vector，没卡 vector 好评。

没卡读入好评。

看 Netflix 去了（