首页 > 试题广场 >

研究red子序列的红

[编程题]研究red子序列的红

热度指数：2881 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 小红有两个长度为 $n$ 的字符串 $s,t$ ，仅包含小写字母，下标从 $1$ 开始。
$\hspace{15pt}$ 她每次会进行一个操作，把 $s_i$ 和 $t_i$ 交换，你需要回答每一次交换后字符串 $s$ 中的 $\texttt{$ 子序列和 $t$ 中 $\texttt{$ 的子序列之差。
$\hspace{15pt}$ 每次询问不独立。

$\hspace{15pt}$ 子序列是指在一个序列中，通过删除某些元素（可以是零个或多个元素），而不改变其余元素的相对顺序所得到的序列。

输入描述:

第一行两个整数  代表字符串长度和操作次数。
第二行一个长度为  的字符串  。
第三行一个长度为  的字符串  。
此后  行，每行一个整数 ，表示每次交换的位置。

输出描述:

对于每一次询问，在一行上输出一个整数，表示交换后字符串  中的  子序列和  中  的子序列之差。

示例1

输入

5 2
redar
adade
5
4

输出

1
2

算法知识视频讲解

Bezime

发表于 2024-11-24 21:16:46

F题题解：题目说求字符串 s 中的子序列red的数目减去字符串 t 中的子序列red的数目。因为有修改，往维护方面想，考虑线段树，维护区间red6个非空子串（r、e、d、re、ed、red）的个数。众所周知，red=re+d或r+ed，而re=r+e，ed=e+d。区间 [l,r] 的r 展开全文

iamputin

发表于 2024-11-24 21:24:57

F题题解: 备注: 本人在这之前没写过这种类型题目, 所以我的思路应该可以帮到不会的同学这道题刚拿到手我是有点懵的, 因为我并没有读懂题目意思!!, 后来手算了一下样例才搞明白了这题目是什么意思!!! 就是算两个字符串里子序列为 red 数量之差我一开始觉得这道题有点难以下手, 因为想算个数就得展开全文

牛客856751393号

发表于 2025-03-04 17:00:06

输出结果和C++版一致，但是提交不通过，怀疑是系统问题。 class Node(object): # 线段树的结点类 def __init__(self): self.ln = -1 self.rn = -1 # 左子节点和右子节点，值为字符的索引展开全文

Goldminer

发表于 2025-04-19 17:33:07

#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll const int MAXN = 2e5 + 5; // 定义左子节点和右子节点的宏 #define ls(p) (p 展开全文

番禺小韭菜

发表于 2025-03-03 17:47:05

#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll const int MAXN = 2e5 + 5; #define ls(p) (p << 1) #def 展开全文

牛客754921490号

发表于 2025-12-14 20:05:56

package main import ( "fmt" ) // 使用线段树算法，第一次直到这个算法，参考了其他人的设计 // go string 内容不可修改，多次询问可能会在s、t之间来回变换，需要转存到数组中 // 吐槽一下go的运行速度真的慢 type SegNode 展开全文

阿彪b

发表于 2025-12-19 22:38:24

#include <any> // 包含any头文件（代码中未实际使用，保留原引入） #include<bits/stdc++.h> // 包含所有常用标准库头文件 using namespace std; #define LL long long / 展开全文

问题信息

线段树

难度：

16条回答 94收藏 331浏览

研究red子序列的红

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题