Ugly Number Gym - 101875B (最小表示法)
2024-09-06 18:44:09
题意:给你一串长度为n的数,这个数可以将后面的数挪到前面来,如果没有小于最开始的那个数的话就输出YES,否则输出NO
题解:如果后面有数字小于第一个数的话就肯定是NO了,这题的坑点就是如果前面很长一串都相同但是后面有一个比前面相同位置的数小的话也要输出NO,因为n是5e5,我们不可能检查每一个串,其实对于这个字符串,我们可以求出这个数的最小表示法的答案,如果这个字符串的最小表示法的第一个字符不是第一个的话就是NO了】
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
LL read() {
int x = , f = ; char ch = getchar();
while(ch < '' || ch > '') {
if(ch == '-')f = -;
ch = getchar();
}
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
}
const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = 1e6 + ;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f; int n;
char s[maxn]; int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
scanf("%d", &n); scanf("%s", s + );
for(int i = ; i <= n; i++) {
s[i + n] = s[i];
}
bool flag = ;
for(int i = ; i <= n; i++) {
if(s[i] < s[]) {
flag = ;
break;
}
}
if(flag) {
cout << "NO" << endl;
} else {
int i = , j = , k;
while(i <= n && j <= n) {
for(k = ; k <= n && s[i + k] == s[j + k]; k++);
if(k == n) break;
if(s[i + k] > s[j + k]) {
i = i + k + ;
if(i == j)i++;
} else {
j = j + k + ;
if(i == j) j++;
}
}
int ans = min(i, j);
if(ans != ) cout << "NO" << endl;
else cout << "YES" << endl;
}
return ;
}
最大最小表示法模板
int getMin() {
int i = , j = ;
int l;
while (i < len && j < len) {
for (l = ; l < len; l++)
if (str[(i + l) % len] != str[(j + l) % len]) break;
if (l >= len) break;
if (str[(i + l) % len] > str[(j + l) % len]) {
if (i + l + > j) i = i + l + ;
else i = j + ;
}
else if (j + l + > i) j = j + l + ;
else j = i + ;
}
return i < j ? i : j;
} int getMax() {
int i = , j = , k = ;
while (i < len && j < len && k < len) {
int t = str[(i + k) % len] - str[(j + k) % len];
if (!t) k++;
else {
if (t > ) {
if (j + k + > i) j = j + k + ;
else j = i + ;
}
else if (i + k + > j) i = i + k + ;
else i = j + ;
k = ;
}
}
return i < j ? i : j; }
最新文章
- 利用Select2优化@Html.ListBoxFor显示,学会用MultiSelectList
- 161226、js日期格式化
- Java魔法堂:String.format详解
- ios开发随笔第一篇-button,label按钮的一些属性的使用
- centos查看设置端口开放状态
- 自定义滚动条CSS样式
- MYSQL数据库间同步数据
- 解决 Boot Camp 虚拟机升级到 Windows 10 后 Parallels Desktop 不能识别的问题
- Linux网络编程(五)
- python网络爬虫之LXML与HTMLParser
- Runtime.addShutdownHook的用法
- java编程(1)——servlet和Ajax异步请求的接口编程(没有调用数据库的数据)
- springboot动态修改日志级别+权限认证
- CentOS随笔——关机命令
- Kibana简单使用教程
- Memcached 命令行操作
- TypeScript基础学习
- ios虚拟机安装(二)
- [转] Maven 直接下载依赖项 artifact, dependency:get
- hdu 4193 Non-negative Partial Sums 单调队列。
热门文章
- Mac下怎么更新nodejs
- Leetcode Week2 Two Sum
- [Python]python已经安装了jieba库,Pycharm无法使用的问题
- 跨站脚本(XSS)
- 记录 Docker 的学习过程 (dockerfile自动制作镜像)
- springboot 扫描不到包 @SpringBootApplication 自动配置原理
- git&;github 的使用
- 0002 增加APP配置
- AcWing 532. 货币系统
- g++运行c++程序提示main()找不到