【题解】How many HDU - 2609 ⭐⭐⭐ 【最小表示法】
发布日期:2021-06-29 16:36:32
浏览次数:3
分类:技术文章
本文共 1416 字,大约阅读时间需要 4 分钟。
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’).Input
For each test case output a integer , how many different necklaces.
Output
Sample Input
4 0110 1100 1001 0011 4 1010 0101 1000 0001 Sample Output 1 2Hint
题意:
给出n个字符串, 每个字符串可以旋转移动, 问一共有多少个不同的字符串
题解:
看到这种循环字符串的问题, 考虑最小表示法, 一个很简单的算法.
对于每个字符串都求出其最小表示法的字符串, 然后丢set里去个重就好了经验小结:
#includeusing namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef long long LL;const int inf = 1 << 30;const int maxn = 1e4 + 10;string S[maxn];set se;int getMin(string S){ int n = S.length(), i = 0, j = 1, k = 0, t; while(i < n && j < n && k < n){ t = S[(i+k)%n] - S[(j+k)%n]; if(t == 0) ++k; else{ if(t > 0) i += k+1; else j += k+1; if(i == j) ++j; k = 0; } } return i > j ? j : i;}int main() { int n; while(cin >> n) { se.clear(); for(int i = 1; i <= n; ++i) cin >> S[i]; //逐个枚举 for(int i = 1; i <= n; ++i){ string T; int t = getMin(S[i]), len = S[i].length(); for(int j = t, k = 0; k < len; ++k) T += S[i][(j+k)%len]; se.insert(T); } cout << se.size() << endl; } return 0;}
转载地址:https://suprit.blog.csdn.net/article/details/101024446 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月12日 14时32分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
又一浏览器集成IPFS,分布式影响力再扩大
2019-04-30
IPFS为何被视为“明天的网络”?
2019-04-30
ubuntu14.04升级的道与术
2019-04-30
ubuntu 16.04在CPU 模式下安装arrayfire
2019-04-30
wav2letter++ 环境安装记录
2019-04-30
语音特征提取学习笔记--对比kaldi、htk、w2l的语音提取过程。
2019-04-30
wav2letter++ 第一次training 日志
2019-04-30
从wav2letter中提取语音属性的代码
2019-04-30
用于分析tensorflow 网络图的工具对比介绍
2019-04-30
WINDOWS UBUNTU18.04lts 双系统安装
2019-04-30
tensorflow mini batch 训练中线程和队列数据输入的问题
2019-04-30
神经网络优化学习思考
2019-04-30
vue单页面组件
2019-04-30
vue反向代理使用
2019-04-30
vue路由配置解析
2019-04-30
es6常用语法
2019-04-30
js 常见错误(待补充)
2019-04-30
moment插件使用
2019-04-30
react
2019-04-30