[HDU 4162] Shape Number【最小表示法】

  • 2018-01-06
  • 0
  • 0

Problem:

Time Limit: 24000/12000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

In computer vision, a chain code is a sequence of numbers representing directions when following the contour of an object. For example, the following figure shows the contour represented by the chain code 22234446466001207560 (starting at the upper-left corner).

Two chain codes may represent the same shape if the shape has been rotated, or if a different starting point is chosen for the contour. To normalize the code for rotation, we can compute the first difference of the chain code instead. The first difference is obtained by counting the number of direction changes in counterclockwise direction between consecutive elements in the chain code (the last element is consecutive with the first one). In the above code, the first difference is

00110026202011676122

Finally, to normalize for the starting point, we consider all cyclic rotations of the first difference and choose among them the lexicographically smallest such code. The resulting code is called the shape number.

00110026202011676122
01100262020116761220
11002620201167612200
...
20011002620201167612

In this case, 00110026202011676122 is the shape number of the shape above.

Input

The input consists of a number of cases. The input of each case is given in one line, consisting of a chain code of a shape. The length of the chain code is at most 300,000, and all digits in the code are between 0 and 7 inclusive. The contour may intersect itself and needs not trace back to the starting point.

Output

For each case, print the resulting shape number after the normalizations discussed above are performed.

Sample Input

22234446466001207560
12075602223444646600

Sample Output

00110026202011676122
00110026202011676122

Source

The 2011 Rocky Mountain Regional Contest

Recommend

lcy   |   We have carefully selected several similar problems for you:  4161 4163 4164 4165 4168

Solution:

## 今天 POJ 被一个程序 (Run ID = 18020626) 卡着编译了 4 个多钟头!所以找了道 HDU 的 ##

字符串最小表示法的模板题。

只需要按题目要求将初始的 chain code 转化为 difference code

  • dif[i] = (chain[i + 1] - chain[i]) % 8

然后求 dif 的最小表示法即可。

【字符串的最小表示法】

为叙述简便,此处下标中的 % len 省略。

令哨兵 i = 0, j = 1, k = 0,循环执行以下步骤

  1. 若 s[i + k] == s[j + k],则将 k++。
  2. 若 s[i + k] > s[j + k],则将 i += k + 1,并将 k 重置为 0。
  3. 若 s[i + k] < s[j + k],则将 j += k + 1,并将 k 重置为 0。

若执行过程中 i == j,则将 j++。

整个过程至多比较 2n 次(每比较 1 次,i, j, k 之中的一个增大 1,而 k 的值最终会附加到 i 或 j 上),故时间复杂度为 O(n)。

【最小表示法线性算法的正确性证明】

步骤 1 显然正确,步骤 2 和步骤 3 轮换对称。下面只给出步骤 2 的证明:

令 s[i] ~ s[i + k] 组成的子串为 sisi+1si+2…si+k-1si+k,s[j] ~ s[j + k] 组成的子串为 sjsj+1sj+2…sj+k-1sj+k,其中 si+n = sj+n (0 ≤ n < k)si+k > sj+k

则以 si+n 开头的同构串一定比以 sj+n 开头的字典序大,可以跳过,故步骤 2 正确。

【华丽丽的 Q.E.D.】

Code: O(Tn) [2084K, 577MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

char cod[300005], dif[300005];
int len;

#define cyc(x) ((x) < len ? (x) : (x) - len)
inline int minRepresentation(char *str, int len){
	int i = 0, j = 1, k = 0, diff;
	while(i < len && j < len && k < len){
		diff = str[cyc(i + k)] - str[cyc(j + k)];
		if(!diff) k++;
		else{
			if(diff > 0) i += k + 1;
			else j += k + 1;
			if(i == j) j++;
			k = 0;
		}
	}
	return min(i, j);
}

int main(){
	while(scanf("%s", cod) != EOF){
		len = strlen(cod), cod[len] = cod[0];  // No need to worry '\0' covered
		for(register int i = 0; i < len; i++){
			dif[i] = cod[i + 1] - cod[i] + '0';
			if(dif[i] < '0') dif[i] += 8;
		}
		int startid = minRepresentation(dif, len);
		for(register int i = startid; i < len; i++) putchar(dif[i]);
		for(register int i = 0; i < startid; i++) putchar(dif[i]);
		puts("");
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai