本文共计425个文字，预计阅读时间需要2分钟。

链接：https://vjudge.net/problem/HDU-2609题目：给定n（n+10000）个项链，项链长度不超过100，求总共有多少种不同的项链（如果两个项链可以通过旋转相等，则认为它们是相同的）。

链接:

vjudge.net/problem/HDU-2609

题意:

Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me
How many kinds of necklaces total have.(if two necklaces can equal by rotating ,we say the two necklaces are some).
For example 0110 express a necklace, you can rotate it. 0110 -> 1100 -> 1001 -> 0011->0110.

思路:

找到每个字符串的最小表示法.加到set里去重即可.

代码:

#include <iostream> #include <cstdio> #include <cstring> #include <vector> //#include <memory.h> #include <queue> #include <set> #include <map> #include <algorithm> #include <math.h> #include <stack> #include <string> #include <assert.h> #include <iomanip> #include <iostream> #include <sstream> #define MINF 0x3f3f3f3f using namespace std; typedef long long LL; const int MAXN = 1e4+10; const int MOD = 1e4+7; char a[MAXN][110]; set<string> St; int n; int GetStrMin(char *s) { int i = 0, j = 1, k = 0; int len = strlen(s); while (i < len && j < len && k < len) { int cmp = s[(i+k)%len]-s[(j+k)%len]; if (cmp == 0) k++; else { if (cmp > 0) i += k+1; else j += k+1; if (i == j) j++; k = 0; } } return min(i, j); } void Insert(char *s, int p) { int len = strlen(s); char tmp[210] = ""; strcat(tmp, s); strcat(tmp, s); tmp[p+len-1] = 0; St.insert(tmp+p); } int main() { while (~scanf("%d", &n)) { St.clear(); for (int i = 1;i <= n;i++) scanf("%s", a[i]); for (int i = 1;i <= n;i++) { int p = GetStrMin(a[i]); Insert(a[i], p); } printf("%d\n", (int)St.size()); } return 0; }