【luogu P5826】【模板】子序列自动机
2023-09-27 14:28:25 时间
【模板】子序列自动机
题目链接:luogu P5826
题目大意
给你一个序列,每次再给你一个序列,问你新的序列是不是一开始的序列的子序列。
思路
如果字符少不难想象到一个
f
i
,
j
f_{i,j}
fi,j 表示
i
i
i 这个位置开始第一个字符是
j
j
j 的位置,然后直接走看看行不行。
但是字符多,于是考虑用时间换空间。
考虑用 vector 记录每个字符在哪些位置出现。
那把每个 vector 排序一下之后你就可以通过二分(lower_bound)找到你当前位置下一个要的字符最近在哪里。
然后就好了。
代码
#include<cstdio>
#include<vector>
using namespace std;
const int N = 1e5 + 100;
const int M = 1e6 + 100;
int type, n, q, m, a[N];
int sz, b[M];
vector <int> f[N];
int main() {
scanf("%d %d %d %d", &type, &n, &q, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), f[a[i]].push_back(i);
while (q--) {
scanf("%d", &sz); for (int i = 1; i <= sz; i++) scanf("%d", &b[i]);
int now = 0;
for (int i = 1; i <= sz && now <= n; i++) {
vector <int>::iterator it = lower_bound(f[b[i]].begin(), f[b[i]].end(), now + 1);
if (it == f[b[i]].end()) now = n + 1;
else now = *it;
}
if (now <= n) printf("Yes\n");
else printf("No\n");
}
return 0;
}
相关文章
- 【HDU 2063】过山车(二分图最大匹配模板题)
- Mibatis中tk忽略字段,以及使用模板查询
- 我最喜欢的模板jade(pug)学习和使用
- 如何选择Javascript模板引擎(javascript template engine)?
- Django 博客开发教程 10 - 页面侧边栏:使用自定义模板标签
- 期刊模板搜索网址
- IDEA修改Servlet代码模板
- 为QtCreator项目模板添加自动中文支持
- 基于SpringBoot的金刚模板化接口自动化测试项目(开源)
- 华为telnet连接(无用户名登录和aaa模板登录)
- thinkphp在模板中使用php的函数
- [git].gitignore使用及模板
- 接口测试用例模板
- mybatis模板