NOJ上机系统 准备中……

金卡换位

1000ms 262144K

描述：

💡 （如果考生对完整解答本题与下一题没有足够把握，可以尝试只解决本题的一到几个特定数据范围，特定数据范围相较完整版更为简单，详见注释。）

某珠宝店的展示柜中摆放着一排由纯金打造的金卡，每张金卡上刻有一个大写或小写字母。为了吸引顾客，店员会根据指示进行调换操作。每次操作选择两个位置的金卡进行交换。请计算经过所有操作后，金卡的排列顺序。

输入：

第一行包含两个整数 $$$n$$$ 和 $$$m$$$，表示金卡的数量和操作次数。第二行是一个长度为 $$$n$$$ 的字符串，表示初始的金卡排列。题目保证字符串仅包含大小写字母，且 $$$1 \leq n \leq 10^5$$$， $$$0 \leq m \leq 10^5$$$。

接下来 $$$m$$$ 行，每行两个整数 $$$a_i$$$ 和 $$$b_i$$$，表示本次要交换的两个金卡的位置（位置从 $$$1$$$ 开始编号）。

题目保证，所有操作中的位置都是有效的，即 $$$1 \leq a_i, b_i \leq n$$$。

输出：

输出一行，包含最终的字符串。

样例输入：

5 2
ABCDE
1 3
2 4

样例输出：

CDABE

样例输入：

3 1
abc
1 2

样例输出：

bac

样例输入：

4 2
Gold
1 4
3 2

样例输出：

dloG

注释：

在第一个样例中：

  1. 初始序列为 ABCDE；
  2. 交换位置 $$$1$$$ 和 $$$3$$$ （A↔C）得到 CBADE；
  3. 交换位置 $$$2$$$ 和 $$$4$$$ （B↔D）得到 CDABE。

第三个样例中：

  1. 初始序列为 Gold；
  2. 交换位置 $$$1$$$ 和 $$$4$$$ （G↔d）得到 dolG；
  3. 交换位置 $$$3$$$ 和 $$$2$$$ （l↔o）得到 dloG。

题目保证，对于 $$$10\%$$$ 的数据，$$$n = 1$$$。

题目保证，对于 $$$30\%$$$ 的数据，$$$m \leq 1$$$。

题目保证，对于 $$$60\%$$$ 的数据，$$$n \leq 10^3$$$。

题目保证，对于 $$$80\%$$$ 的数据，$$$1 \leq a_i \leq b_i \leq n$$$。

题目保证，对于 $$$100\%$$$ 的数据，$$$1 \leq n \leq 10^5$$$， $$$0 \leq m \leq 10^5$$$。

信息

机考平台

提供者 机考平台

代码 PROB1039

标签

提交 466

通过 281

通过率 60.3%

修改日期 2025-03-27 14:39:17

相关题目

暂无相关