锐客网

  1. 首页 > 睿知 > it技术 > >

Codeforces 903E Swapping Characters

IT知识codeforces

敢说敢作敢为， 无怨无恨无悔。这篇文章主要讲述Codeforces 903E Swapping Characters相关的知识，希望能为你提供帮助。
题目大意考虑一个未知的长为 $n$（$2\le n\le 5000$）由小写英文字母构成的字符串 $s$ 。给出 $k$（$1\le k\le 2500$，$nk\le 5000$）个字符串 $s_1, s_2, \dots, s_k$，$s_i$ 由 $s$ 通过交换 $s[x_i]$ 和 $s[y_i]$（$x_i \ne y_i$ ）得到。求 $s$，若有多解输出任意一个接，无解输出 -1。
解法假设输入的 $k$ 个串不全相等。（否则平凡）
取 $s_1$、$s_2$，$s_1\ne s_2$ 。（此 $s_1, s_2$ 并非指输入的 $s_1, s_2$ 。）
设 $i$ 是两者不相同的第一个位置，则二者中至少有一个的「交换位置」包含 $i$ 。
据此，可以先假设 $s_1$ 的一个交换位置是 $i$ ，枚举 $s_1$ 的另一个交换位置，进行检验。
若不可能，再假设 $s_2$ 的一个交换位置是 $i$ ，枚举 $s_2$ 的另一个交换位置。
这种做法的时间复杂度为 $O(kn + n^{2}k)$，可接受。
TODO
能否进一步缩小可能的交换位置的范围（candidate swapping index pair），下面尝试讨论这一问题。
不失一般性，设 $s_1$ 的交换位置为 $(i, j)$，$s_2$ 的交换位置为 $(i‘, j‘)$ 。
【Codeforces 903E Swapping Characters】分类讨论：

  1. $i$ 不是 $s_1$ 的第一个交换位置，即 $j < i$ 。
    1.1 $s_1[i] = s_1[j]$
    1.2 $s_1[i] \ne s_1[j]$
  2. $i$ 是 $s_1$ 的第一个交换位置，即 $j > i$ 。

    推荐阅读


    上一篇：第二章（Android Studio概述[学习Android Studio汉化教程]）

    下一篇：win xp系统下运用ps制作艺术字的技巧