汕头市队赛 SRM 06 A 撕书
2024-09-01 10:05:15
A 撕书 SRM 06
背景&&描述
游行寺汀正在杀书。
书总共有n页,每页都可以看作是一个小写英文字母,所以我们可以把书看成长度为n的字符串s。
琉璃静静地在旁边看着。根据他对汀的了解,汀+1s只会撕一页。令表示第i秒撕的是哪一页,显然是1..n的一个排列。
琉璃突然对s的一个非空子序列t产生了兴趣。他想知道,最多在汀撕多少页之后,t仍然是剩下的书的某个子序列。
输入格式
第一行一个字符串,表示s
第二行一个字符串,表示t
第三行n个整数(n为s的长度),表示。
输出格式
一个整数,表示最多在汀撕多少页之后,t仍然是剩下的书的某个子序列。
样例输入
sbkitssakitsak
kisaki
1 14 13 2 6 12 9 10 5 3 8 4 7 11
样例输出
6
数据范围与约定
- 对于100%的数据:
样例解释
6s后,剩下的书为kitsakit,此时kisaki还是书的子序列。第7s撕掉第二个k后就不是了。
查找最大最小的 我一般都会先考虑二分 果不其然这道题就是了 nlogn 完全可做
我们可以记录每个点的消失(也就是被撕)的时间
二分时间求每次是否能匹配就可以了 2333
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+;
char T[M],s[M];
int n,m,l,r,w[M];
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int check(int k){
int cnt=;
for(int i=;i<=n;i++){
if(w[i]<=k) continue;
if(T[i]==s[cnt]) cnt++;
if(cnt==m+) return ;
}
return ;
}
int main()
{
scanf("%s %s",T+,s+);
int k;
n=strlen(T+); m=strlen(s+);
for(int i=;i<=n;i++) k=read(),w[k]=i;
l=; r=n;
while(l<=r){
int mid=(l+r)>>;
if(check(mid)) l=mid+;
else r=mid-;
}
printf("%d\n",r);
return ;
}
最新文章
- 《CLR.via.C#第三版》第二部分第12章节 泛型 读书笔记(六)
- VirtualBox piix4_smbus Error
- operating system
- fir.im Weekly - 600个 Android 开源项目汇总
- 记录git多人协作开发常用的流程,供新手参考
- JS正则获取参数值
- 彻底弄明白之数据结构中的KMP算法
- 埃及分数(codevs 1288)
- SQLServer学习笔记<;>;日期和时间数据的处理(cast转化格式、日期截取、日期的加减)和 case表达式
- 学了C语言,如何利用CURL写一个下载程序?—用nmake编译CURL并安装
- 机器学习基石:Homework #0 SVD相关&;常用矩阵求导公式
- python3 数据科学基础
- (办公)mybatis工作中常见的问题(不定时更新)
- React事件绑定与解绑
- C#中基于GDI+(Graphics)图像处理系列
- Python基于dtw实现股票预测【多线程】
- Oracle 所有的权限列表
- 面试官让你讲讲acks参数对消息持久化的影响
- GROUP BY、HAVING、AS 的用法小例子
- NLP常用语料集合
热门文章
- jmeter动态获取jsessionid
- 问题 A: 分数矩阵
- visionpro halcon 哪个好
- 基于规则的中文分词 - NLP中文篇
- day-12 python实现简单线性回归和多元线性回归算法
- c# 生成dll
- 从微软msdn阅读事件的使用
- x86/x64的stack*****************************TBD
- jQuery插件jquery.fullPage.js
- C++——编程常见错误