[USACO5.5]隐藏口令Hidden Password [最小表示法模板]
2024-08-26 00:49:35
最小表示法就是一个字符串构成一个环,找以哪个点为开头字典序最小。
然后我们就可以用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
最新文章
- PHP日志压缩下载
- HTML 中级2
- Tushare的安装
- Hadoop 中疑问解析
- bzoj4046
- angular ui-route
- 从零开始写驱动——vfd专用驱动芯片HT16514并行驱动程序编写
- 获取listview当前滚动的高度
- HTML+CSS D09 定位
- asp脱离源代码管理
- [python爬虫]爬取学校教务处成绩
- cloud-init 典型应用 - 每天5分钟玩转 OpenStack(174)
- (MariaDB)MySQL内置函数大全
- Java基础--二进制运算
- CMDB-实例
- MySQL中有关NULL的计算
- [20170629]带过滤的复制项UI操作导致订阅全部初始化问题
- 新建react项目
- WPF禁止拖拽窗口到边缘自动最大化
- Oracle行列转换的思考与总结