SNOI 2019 字符串

题目

题解:

解法一:

记一个数组\(f\),\(f[i]=\min_j\ s[j]\neq s[j+1] (j\geq i)\),直接sort即可,复杂度\(O(nlogn)\)

#include<bits/stdc++.h>

using namespace std;

namespace Tzh{

	const int maxn=1000010;
int f[maxn],rank[maxn],n; char s[maxn]; bool cm(int a,int b){
int x=a,y=b,flag=0;
if(x>y) swap(x,y),flag=1;
if(f[x]>=y) return 1^flag;
else return (s[f[x]]>s[f[x]+1])^flag;
} void work(){
cin>>n; cin>>s+1; f[n]=n;
for(int i=n-1;i;i--)
if(s[i]!=s[i+1]) f[i]=i;
else f[i]=f[i+1];
for(int i=1;i<=n;i++) rank[i]=i;
sort(rank+1,rank+n+1,cm);
for(int i=1;i<=n;i++) cout<<rank[i]<<" ";
return ;
}
} int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
ios::sync_with_stdio(false);
Tzh::work();
return 0;
}

解法二

将字符串相同的字符先缩起来,现在字符串相邻两个字符不同.

将字符串分成若干段严格上升的子段,将每个字段的末尾成为1位置,其他成为2位置。

即对于每个1位置\(i\)都有\(s[i]>s[i+1]\),对于每个2位置\(i\)都有\(s[i]<s[i+1]\)

对于两个删1位置的串比较,前面的小

对于两个删2位置的串比较,后面的小

对于一个删1,一个删2的串,删1的小

所以先把1位置的输出,剩下的倒序输出即可

复杂度\(O(n)\)

#include<bits/stdc++.h>

using namespace std;

namespace Tzh{

	const int maxn=1000010;
int n,top,st[maxn],last; char s[maxn]; void work(){
cin>>n>>s+1;
for(int i=1;i<=n;i++){
if(s[i]==s[i+1]&&!last) last=i;
else if(s[i]>s[i+1]){
if(!last) last=i;
for(int j=last;j<=i;j++) cout<<j<<" ";
last=0;
}
else if(s[i]<s[i+1]){
if(!last) last=i;
for(int j=i;j>=last;j--) st[++top]=j;
last=0;
}
}
for(int i=top;i;i--) cout<<st[i]<<" ";
return ;
}
} int main(){
Tzh::work();
return 0;
}

最新文章

  1. 【POJ 1182】食物链(并查集)
  2. UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode byte 0xff in position 0: illegal multibyte sequence
  3. Html-Css-div半透明
  4. CSS图片垂直居中方法
  5. [转]每天一个linux命令目录
  6. java rest框架jersey数组单记录问题解决
  7. html5定位并在百度地图上显示
  8. scrollView的几个属性contentSize contentOffset contentInset
  9. HDOJ/HDU 1242 Rescue(经典BFS深搜-优先队列)
  10. adb logcat命令查看并过滤android输出log
  11. android权限列表
  12. java 文件的基本操作
  13. MySQL解决&quot;is marked as crashed and should be repaired&quot;故障
  14. C#中MessageBox用法大全(附效果图)
  15. 推荐 git community book 中文版
  16. 开放源代码的设计层面框架Spring——day02
  17. MSTM年底总结
  18. Pytorch学习笔记
  19. ArrayList源码分析笔记(jdk1.8)
  20. 数学与猜想 合情推理模式 (G. 波利亚 著)

热门文章

  1. linux 监测函数
  2. java 字符串转成 json 数组并且遍历
  3. NSFileManager计算文件/文件夹大小
  4. APP设计师拿到APP产品原型开始,七步搞定APP设计(转)
  5. Android——模拟文件拷贝
  6. 解决Mysql的主从数据库没有同步的两种方法
  7. PHP — php精粹-编写高效的php代码 --- API
  8. pthread_rwlock_t读写锁函数说明
  9. SpringMVC04controller中定义多个方法
  10. go - 变量和常量
  11. rndc 错误解决 和 远程配置
  12. Open-Falcon 监控系统监控 MySQL/Redis/MongoDB 状态监控
  13. 13 用Css做下拉菜单
  14. Android --&gt; 常见控件
  15. testNG java.net.SocketException: Software caused connection abort: socket write error
  16. BZOJ 4259 残缺的字符串
  17. js写插件教程入门
  18. javascript知识整理之this
  19. python 什么是位置参数?
  20. gcc,make,cmake