#a. 打权游戏

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h

Type: RemoteJudge

1000ms

256MiB

题目背景

请不要带入生活经验或时事政治。

题面描述

对于一个下标由 $1$ 开始的小写英文字符串 $s$ ，定义一次变换为同时进行以下的两种操作：

把所有 he 子串替换为 she。
把所有 his 子串替换为 her。

例如，hisheppybob 会变成 hersheppybob。

现在给定一个初始字符串 $s$ ，以及 $q$ 个询问。每个询问给定 $k, x$ ，表示要你输出 $s$ 经过 $k$ 次变换后的第 $x$ 个字符。如果不存在第 $x$ 个字符，输出 0。

询问之间互相独立，即不会真正地对 $s$ 进行变换。

输入格式

本题含有多组数据，并且有部分分。

第一行两个整数 $c, T$ ，表示当前数据的编号和数据组数。在样例中 $c = 0$ 。

每组数据包含 $q + 2$ 行，第一行两个整数 $|s|, q$ ，表示 $s$ 的长度和询问个数。

第二行 $|s|$ 个小写字母，表示字符串 $s$ 。

接下来 $q$ 行，每行两个整数 $k, x$ ，表示要求输出 $s$ 进行 $k$ 次变换之后的第 $x$ 个字符。

输出格式

对于每一个询问输出一行，如果存在第 $x$ 个字符，输出该字符，否则输出 0。

样例

0 1
11 3
hisheppybob
1 2
1 13
2 6

e
0
s

说明/提示

初始时 $s =$ hisheppybob。进行一次变换后， $s$ 变为 hersheppybob，第 $2$ 个字符为 e，不存在第 $13$ 个字符。

进行两次变换之后 $s$ 变为 sherssheppybob。

对于 $100\%$ 的数据， $1 \le T \le 5$ ， $1 \le n, q \le 2 \times 10^5$ 。对于每组询问， $1 \le k, x \le 10^9$ 。

保证 $s$ 仅由小写字母组成。

测试点编号	$n \le$	$q \le$	$k \le$	其他性质
$1$	$200$	$2 \times 10^5$	$200$	$s$ 中 `i` 后面不是 `h`
$2, 3$	$200$		$200$
$4$	$2000$		$10^9$	$s$ 中 `i` 后面不是 `h`
$5 \sim 7$	$2000$
$8$	$2 \times 10^5$			$s$ 中 `i` 后面不是 `h`
$9 \sim 20$	$2 \times 10^5$

国庆提高/省选组比赛

Attended

Status: Live... (Attended)
Rule: IOI
Problem: 40
Start at: 2025-10-15 19:32
End at: 2025-11-16 0:00
Duration: 1104 hour(s)
Host: 梁泽贤 (liangzexian)
Partic.: 85

#a. 打权游戏

打权游戏

题目背景

题面描述

输入格式

输出格式

样例

说明/提示

国庆提高/省选组比赛

Status

Development

Support

#a. 打权游戏

打权游戏

题目背景

题面描述

输入格式

输出格式

样例

说明/提示

国庆提高/省选组比赛

Status

Development

Support

Don't have an account?

SIGN IN