HDU 2609 How many（最小表示法）

Problem Description 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.  

 

Input The input contains multiple test cases. Each test case include: first one integers n. (2<=n<=10000) Next n lines follow. Each line has a equal length character string. (string only include '0','1').  

 

Output For each test case output a integer , how many different necklaces.  

 

Sample Input 4 0110 1100 1001 0011 4 1010 0101 1000 0001  

 

Sample Output 1 2  

 

Author yifenfei  

 

Source 奋斗的年代   思路：一开始就想到了最小表示法，本来想着用一个 bool sign[100000] 数组去判断哪个字符串是重复的，但是发现这个办法很麻烦，而且我还wa了。后来用着 set 判重，妈妈再也不用担心我的学习， so easy~   /// /// _ooOoo_ /// o8888888o /// 88" . "88 /// (| -_- |) /// O\ = /O /// ____/`---'\____ /// .' \\| |// `. /// / \\||| : |||// \ /// / _||||| -:- |||||- \ /// | | \\\ - /// | | /// | \_| ''\---/'' | | /// \ .-\__ `-` ___/-. / /// ___`. .' /--.--\ `. . __ /// ."" '< `.___\_<|>_/___.' >'"". /// | | : `- \`.;`\ _ /`;.`/ - ` : | | /// \ \ `-. \_ __\ /__ _/ .-` / / /// ======`-.____`-.___\_____/___.-`____.-'====== /// `=---=' /// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ /// Buddha Bless, No Bug ! /// #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <vector> #include <set> using namespace std; #define MAXN 100010 #define ll long long string s; int len, ans; set<string>se; int minma(string x)///最小表示法 { int len = x.size(); int i = 0, j = 1, k = 0; while(i < len && j < len && k < len)///如果还在范围内 { int t = x[(i + k) % len] - x[(j + k) % len];///比较两个字符之间的字典序大小 if(t == 0)///如果两个字典序都相等，就一起向前比较 k++; else { if(t > 0)///如果 x[(i + k) % len]的字典序比 x[(j + k) % len]的字典序大，则 x[i+1] x[i+2] ... x[i+k]的字典序都会比 x[j+k]大，让 i 直接跳过这一段 i += k + 1; else///如果 x[(j + k) % len]的字典序比 x[(i + k) % len]的字典序大，则 x[j+1] x[j+2] ... x[j+k]的字典序都会比 x[i+k]大，让 j 直接跳过这一段 j += k + 1; if(i == j)///如果 i == j，就让 j 指向下一个字符 j++; k = 0; } } return i < j ? i : j; } int main() { int n; while(cin >> n) { se.clear(); for(int i = 0; i < n; i++) { cin>>s; len = s.size(); int id = minma(s); s += s; se.insert(s.substr(id, len));///用 set 判重，除去相等的部分 } printf("%d\n", se.size()); } return 0; }

 

转载于:https://www.cnblogs.com/RootVount/p/11360063.html