最小表示法就是一个字符串构成一个环,找以哪个点为开头字典序最小。

然后我们就可以用n2的算法愉快的做啦~实际上有O(n)的做法的,就是用两个指针扫,如果这两个位置的字典序相等,就一起往后,如果某一个大,就把那个指针指到大的那个的后面。

每次至少有一个指针往后移一个,复杂度就是线性的了。

(自己YY的,求不出锅)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
char s[];
int main() {
scanf("%d",&n);
char c;
for(int i=;i<n;i++) scanf(" %c",&c),s[i]=c;
int i=,j=,k=;
while(i<n&&j<n&&k<n) {
s[(i+k)%n]-s[(j+k)%n];
if(s[(i+k)%n]==s[(j+k)%n]) k++;
else {
if(s[(i+k)%n]>s[(j+k)%n]) i=i+k+;
else if(s[(i+k)%n]<s[(j+k)%n]) j=j+k+;
if(i==j) j++;
k=;
}
}
printf("%d\n",min(i,j));
}

Hidden Password

最新文章

  1. PHP日志压缩下载
  2. HTML 中级2
  3. Tushare的安装
  4. Hadoop 中疑问解析
  5. bzoj4046
  6. angular ui-route
  7. 从零开始写驱动——vfd专用驱动芯片HT16514并行驱动程序编写
  8. 获取listview当前滚动的高度
  9. HTML+CSS D09 定位
  10. asp脱离源代码管理
  11. [python爬虫]爬取学校教务处成绩
  12. cloud-init 典型应用 - 每天5分钟玩转 OpenStack(174)
  13. (MariaDB)MySQL内置函数大全
  14. Java基础--二进制运算
  15. CMDB-实例
  16. MySQL中有关NULL的计算
  17. [20170629]带过滤的复制项UI操作导致订阅全部初始化问题
  18. 新建react项目
  19. WPF禁止拖拽窗口到边缘自动最大化
  20. Oracle行列转换的思考与总结

热门文章

  1. HDU 4183 Pahom on Water(最大流SAP)
  2. ios 使用Starscream实现websocket简单例子
  3. QMessageBox 的四种用法
  4. XMPP 协议工作流程具体解释
  5. C++对象内存布局 (二)
  6. 使用 Swift 3.0 操控日期
  7. B1786 [Ahoi2008]Pair 配对 逆序对+dp
  8. AMD 与 CMD 区别
  9. HDU3085 Nightmare Ⅱ
  10. Cracking the Coding Interview 10.7