牛客练习赛36 A Rabbit的字符串(字符串最小表示法)
2024-08-28 13:50:06
链接:https://ac.nowcoder.com/acm/contest/328/A
来源:牛客网
题目描述
Rabbit得到了一个字符串,她的好朋友xxx可以给这个字符串施加一次魔法。
魔法可以选择字符串的任一位置,并将该位置后面的所有字符水平拼接到串首。
例如:对于字符串abcde,可以通过施加魔法得到cdeab。
如果xxx通过施加魔法将字符串的字典序变得严格比之前的小,那么他将拿走这一字符串。
Rabbit想知道自己的字符串会不会被xxx拿走。
输入描述:
第一行一个整数n,表示字符串的长度。 接下来一行一个长度为n的只由小写字母组成的字符串。
输出描述:
如果Rabbit的字符串会被xxx拿走,输出“YES”。
否则输出“NO”。
(不输出引号)
备注:
1≤n≤100000 字典序的说明:https://en.wikipedia.org/wiki/Alphabetical_order
标答:
可以用字符串最小表示法解决。
#include <cstdio>
#include <bits/stdc++.h>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--) typedef long long ll;
const int maxn = ;
const ll INF = 1e18;
const ll mod=1e9+;
const double eps = 1e-; char s[maxn];
char tmp[maxn]; int find_min(char *s,int len)
{
int i=,j=,k=,t;
while(i<len&&j<len&&k<len)
{
t=s[(i+k)>=len?i+k-len:i+k]-s[(j+k)>=len?j+k-len:j+k];
if(t==)k++;
else
{
if(t>) i+=k+;
else j+=k+;
if(i==j) ++j;
k=;
}
}
return (i<j?i:j);
} void get_temp(int len)
{
int k=find_min(s,len);
for(int i=; i<len; i++)
{
tmp[i]=s[(i+k)%len];
}
} int main()
{
int n;
scanf("%d",&n);
scanf("%s",s);
get_temp(n);
tmp[n]='\0';
if(strcmp(s,tmp)==) puts("NO");
else puts("YES");
}
不会证明。攒个模板吧。
int find_min(char *s,int len)
{
int i=,j=,k=,t;
while(i<len&&j<len&&k<len)
{
t=s[(i+k)>=len?i+k-len:i+k]-s[(j+k)>=len?j+k-len:j+k];
if(t==)k++;
else
{
if(t>) i+=k+;
else j+=k+;
if(i==j) ++j;
k=;
}
}
return (i<j?i:j);
}
最新文章
- django 学习第一天搭建环境
- APP技术演化的路
- Stack的三种含义
- Tomcat的粗略介绍
- 趣谈unicode,ansi,utf-8,unicode big endian这些编码有什么区别(转载)
- java数组引用
- CCNA网络工程师学习进程(5)路由器和交换机的登录安全配置和vlan划分
- 面向服务架构(SOA)和企业服务总线(ESB)
- MyEclipse 代码自动提示
- Android 手动显示和隐藏软键盘
- 前端自动化构建工具 Gulp 使用
- gzip解压压缩的字符串数据
- Centos7.2 编译安装PHP7
- ThinkPHP中ajax绑定select下拉框无法显示
- Java程序的第一次作业
- python 函数参数为*和**的作用与区别
- SHOI2008仙人掌图(tarjan+dp)
- 需要看源码的java类
- [转]bootstrapValidator.js 做表单验证
- Linux 之 crontab 使用
热门文章
- Microsoft Dynamics CRM 批量上传web资源(非官方WebResourceUtility)并替换实体图标
- vue在移动端实现复制数值到剪贴版
- go modules 学习
- PostGIS 查询点在线上
- String字符串为什么不可变的深入理解
- Rocket框架多文件上传,介绍rocket_upload 使用
- spring+cxf 开发webService(主要是记录遇到spring bean注入不进来的解决方法)
- 20190908write from memory
- 程序员的算法课(18)-常用的图算法:广度优先(BFS)
- MySQL5.7.18自动化安装脚本