Long Long Ago 二分查找
2024-08-24 05:55:30
L: Long Long Ago
时间限制: 1 s 内存限制: 128 MB
提交 我的状态
题目描述
今天SHIELD捕获到一段从敌方基地发出的信息里面包含一串被经过某种算法加密过的的序列L
组织的间谍活动如下几个线索:
这个算法不会改变秘密消息的字符顺序,但是会两个字符之间在中间加入未知个数的字符
如原信息
ab
可能的加密结果
ammmxxxxb
现在你有n个待选关键字
如果这个关键字可能是秘密消息输出Yes,否则输出No
如ammmmxxxxb
可能包含的关键字有
ab
mb
mxb
......
输入
第一行输入一串字符串LL(1≤L≤105)(1≤L≤105)
第二行输入一个整数NN,表示查找字符串的个数。(1≤N≤105)(1≤N≤105)
接下来NN行表示,输入一行字符串MM n个字符的长度之和为[1,100000]
输出
输出NN行,如果是符合提议就输出Yes,否则输出No
样例输入
noiauwfaurainairtqltqlmomomo
8
rain
air
tql
ntt
xiaobai
oiiiooo
orzcnzcnznb
ooooo
样例输出
Yes
Yes
Yes
Yes
No
Yes
No
No
题解:题目意思是若询问的字符串是原字符串切割出来的,输出Yes,否则输出No,用map记录(我用的是字符与a的差值作为下标)每个字符对应的所有位置,然后每输入一串字符就遍历一次该字符串的所有字母,对于每一个字符二分查找出大于前一个字符所取位置的第一个位置,若未找到则退出遍历,输出No;
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
#define ll long long
char s[1000011],ss[1000011];
vector<ll>p[33];
ll sort2(ll i,ll k){
if(p[i].size()==0)
return -1;
ll x=0,y=p[i].size()-1;
while(x<=y){
ll m=x+(y-x>>1);
if(p[i][m]>k)
y=m-1;
else
x=m+1;
}
return x<p[i].size()?p[i][x]:-1;
}
int main(){
scanf("%s",s);
for(int i=0;s[i];i++)
p[s[i]-'a'].push_back(i);
// for(int i=0;i<26;i++)
// for(int j=0;j<p[i].size();j++)
// cout<<p[i][j]<<endl;
ll n,k;
scanf("%lld",&n);
while(n--){
scanf("%s",ss);
ll len=strlen(ss)-1;
bool flag=0;
k=-1;
for(int i=0;ss[i];i++){
k=sort2(ss[i]-'a',k);//二分查找大于k的第一个数
if(k==-1)
{flag=1;break;}
}
if(!flag)
printf("Yes\n");
else
printf("No\n" );
}
return 0;
}
最新文章
- 【转】C/S,B/S区别
- 谷歌/微软/必应web页面免费翻译插件
- Linux不重启的情况下添加硬盘
- win8.1/win10 UEFI + GPT 安装(测试机型:华硕S56CM)
- 生理周期[PKU1006]
- bzoj4518
- D3序
- PDF编译出现错误解决办法
- 10.29 afternoon
- Apache MINA NioSocketAcceptor类的实现
- 强化一下,QDialog有专门的exec函数和finished信号,QWidget都没有
- python购物淫秽数据分析(2)
- 【集美大学1411_助教博客】个人作业2——英语学习APP案例分析 成绩
- mySQL语法中的存储过程及if语句的使用简例
- Object 中 equals()使用
- Scaffold-DbContext 命令参数
- kickstart ---无人值守安装
- mybatis之sql执行有数据但返回结果为null
- linux-Centos 7下mysql 5.7.9的rpm包安装
- JavaScript二(第一个js程序)
热门文章
- 【XSY3345】生成树 并查集
- 快速傅里叶变换FFT&; 数论变换NTT
- 通过10046 event来获取真实的执行计划
- Mysql高性能笔记(一):Schema与数据类型优化
- springMVC统一异常处理
- Codeforces Round #554 (Div. 2) B. Neko Performs Cat Furrier Transform(思维题+log2求解二进制位数的小技巧)
- SQL Server数据库中表的查
- SimpleDateFormat 线程不安全及解决方案
- mysql的The user specified as a definer (”@’%&#39;) does not exist 的解决办法
- win 域