首页 > 试题广场 >

研究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

算法知识视频讲解

Python3

请叫我牛柳

燃尽了

import sys

def cal_red(word: str):
    nr = 0
    nre = 0
    nred = 0
    for l in word:
        if l == 'r':
            nr += 1
        elif l == 'e':
            nre += nr
        elif l == 'd':
            nred += nre
    return nred


n, q = input().split(' ')
n, q = int(n), int(q)

s = input()
t = input()
n_s, n_t = 0, 0
for _ in range(q):
    x = int(input())

    tmpt, tmps = t[x-1], s[x-1]
    s = s[:x-1] + tmpt + s[x:]
    t = t[:x-1] + tmps + t[x:]

    if tmpt in 'red'&nbs***bsp;tmps in 'red'&nbs***bsp;_ == 0:
        n_s = cal_red(s)
        n_t = cal_red(t)

    print(n_s - n_t)

发表于 2025-07-03 22:21:27 回复(1)

Python3

不会哈气学哈气

自认为时间复杂度已经最优了，但是还是超时。不知道有没有什么取巧的办法

def sub_count(s, sub):

n = len(sub)
dp = [0] * (n+1)
dp[0] = 1
for e in s:
for j in range(n, 0, -1):
if e == sub[j-1]:
dp[j] += dp[j-1]

return dp[n]

n, q = map(int, input().split())
s, t = list(input()), list(input())
for _ in range(q):
pos = int(input())-1
s[pos], t[pos] = t[pos], s[pos]

print(sub_count(s,'red')-sub_count(t,'red'))

发表于 2025-05-17 13:13:58 回复(0)

Python3

zzlh

感觉算法Segment Tree实现的没问题，但是局限于 python 语言太慢了所以这道题没法通过了。

import sys
import re
n,q=map(int,input().split())
s=list(input())
t=list(input())

class SegmentTree:
    def __init__(self,s):
        #
        self.n=len(s)
        N=1
        while N<self.n:
            N<<=1
        #叶子节点的位置
        self.N=N
        size=2*N
        self.r=[0]*size
        self.e=[0]*size
        self.d=[0]*size
        self.re=[0]*size
        self.ed=[0]*size
        self.red=[0]*size
        #叶子节点赋值
        for i in range(self.n):
            if s[i]=='r':
                self.r[N+i]=1
            elif s[i]=='e':
                self.e[N+i]=1
            elif s[i]=='d':
                self.d[N+i]=1
        for i in range(N-1,0,-1):
            self.merge(i)
    #把Id节点的左右节点合并到自身
    def merge(self,id):
        l=id*2
        r=id*2+1
        self.r[id]=self.r[l]+self.r[r]
        self.e[id]=self.e[l]+self.e[r]
        self.d[id]=self.d[l]+self.d[r]
        self.re[id]=self.re[l]+self.re[r]+self.r[l]*self.e[r]
        self.ed[id]=self.ed[l]+self.ed[r]+self.e[l]*self.d[r]
        self.red[id]=self.red[l]+self.red[r]+self.r[l]*self.ed[r]+self.re[l]*self.d[r]
    #修改节点
    def update(self,pos,ch):
        N=self.N
        self.r[pos+N]=0
        self.e[pos+N]=0
        self.d[pos+N]=0
        if ch=='r':
            self.r[pos+N]=1
        elif ch=='e':
            self.e[pos+N]=1
        elif ch=='d':
            self.d[pos+N]=1
        x=(pos+N)//2
        while x>=1:
            self.merge(x)
            x//=2
segtree1=SegmentTree(s)
segtree2=SegmentTree(t)       
for _ in range(q):
    pos=int(input())-1
    t[pos],s[pos]=s[pos],t[pos]
    segtree1.update(pos,s[pos])
    segtree2.update(pos,t[pos])
    print(segtree1.red[1]-segtree2.red[1])

发表于 2025-05-16 22:34:38 回复(0)

Python3

吃不饱的卷王很害怕一个人

#输出一样为啥也过不了，奇奇怪怪的

import sys

list_change = list()

formore = list(input().split())

str_length = int(formore[0])

trans_num = int(formore[1])

list_str1 = list()

list_str2 = list()

str1 = str(input())

str2 = str(input())

for i in range(len(str1)):

list_str1.append(str1[i])

list_str2.append(str2[i])

list_change = [0 for _ in range(trans_num)]

for i in range(trans_num):

list_change[i] = int(input())

def find_count(num: list):

e_i = [[0,0] for _ in range(len(num))]

num_r = 0

num_d = 0

count = 0

for i in range(len(num)):

if num[i] == 'r':

num_r += 1

elif num[i] == 'e':

e_i[i][0] = num_r

for i in range(len(num)-1,-1,-1):

if num[i] == 'd':

num_d += 1

elif num[i] == 'e':

e_i[i][1] = num_d

for i in e_i:

count += int(i[0]) * int(i[1])

return count

result = list()

for i in range(trans_num):

num = list_change[i]

str_copy1 = list_str1

str_copy2 = list_str2

str_copy1[num-1] = str2[num-1]

str_copy2[num-1] = str1[num-1]

count1 = find_count(str_copy1)

count2 = find_count(str_copy2)

res = count1-count2

result.append(res)

for i in range(len(result)):

print(result[i])

发表于 2025-03-11 12:51:49 回复(0)

提交观点

问题信息

线段树

难度：

6条回答 94收藏 334浏览

研究red子序列的红

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题