hdu-2609 How many---最小表示法模板+set判重
2024-09-05 17:43:48
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2609
题目大意:
有n个有01组成的字符串,每个字符串都代表一个项链,那么该字符串就是一个环状的结构,求可以经过循环旋转,最后不同的串有多少个。。
解题思路:
将所有字符串用最小表示法表示,然后存入set判重
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<set>
using namespace std;
const int maxn = + ;
const int INF = 0x3f3f3f3f;
set<string>tot;
string change_min(char s[])
{
int n = strlen(s);
int i = , j = , k = ;
while(i < n && j < n && k < n)
{
int t = s[(i + k) % n] - s[(j + k) % n];
if(!t)
k++;
else
{
if(t > )
i += k + ;
else
j += k + ;
if(i == j)j++;
k = ;
}
}
int ans = i < j ? i : j;
string cnt;
for(int i = ans; i < ans + n; i++)
{
cnt += s[i % n];
}
return cnt;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
char s[];
tot.clear();
string mins;
for(int i = ; i < n; i++)
{
scanf("%s", s);
mins = change_min(s);
//cout<<mins<<endl;
tot.insert(mins);
}
cout<<tot.size()<<endl;
}
return ;
}
最新文章
- vim的使用与配置
- MS SQL统计信息浅析下篇
- java 装饰者模式与继承的区别
- 简单的计算最值的MapReduce程序
- Android控件— — —ImageView
- php如何将数组保存为文件的方法? 三个方法让你快速把数组保存成为文件存储
- chromium浏览器开发系列第四篇:如何调试最新chromium源码
- python进程、线程、协程(转载)
- Devexpress GridControl中combobox级联显示 z
- Android Studio 实用快捷键
- 关于http状态码204理解
- C++学习之路—继承与派生(三):多重继承与虚基类
- LeetCode OJ 78. Subsets
- linux内核裁剪及编译可加载模块
- codeforces 997C.Sky Full of Stars
- 48- java Arrays.sort和collections.sort()再次总结
- 【Codeforces 17E】Palisection
- Linux下安装oracle的过程
- FPGA 概述2
- windows中80端口被System占用,PID=4的问题