全球要闻:CF 1747B. BAN BAN
来源:哔哩哔哩    时间:2023-06-30 13:19:28

You are given an integer n.

Let's define s(n) as the string "BAN" concatenated n

times. For example, s(1) = "BAN", s(3) = "BANBANBAN". Note that the length of the string s(n) is equal to 3n.


(资料图片仅供参考)

Consider s(n). You can perform the following operation on s(n)

any number of times (possibly zero):

Select any two distinct indices i and j (1≤i,j≤3n,i≠j).

Then, swap s(n)i and s(n)j.

You want the string "BAN" to not appear in s(n) as a subsequence. What's the smallest number of operations you have to do to achieve this? Also, find one such shortest sequence of operations.

A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters.

-----------------------------------------------

给定一个整数 n。

让我们将 s(n) 定义为字符串“BAN”连接 n

次。 例如,s(1) =“BAN”,s(3) =“BANBANBAN”。 请注意,字符串 s(n) 的长度等于 3n。

考虑 s(n)。 可以对 s(n) 执行以下操作

任意次数(可能为零):

选择任意两个不同的索引 i 和 j (1≤i,j≤3n,i≠j)。

然后,交换 s(n)i 和 s(n)j。

您希望字符串“BAN”不作为子序列出现在 s(n) 中。 要实现这一目标,您需要执行的最少操作次数是多少? 另外,找到一个这样的最短操作序列。

如果可以通过删除几个(可能是零个或全部)字符从 b 中获得 a,则字符串 a 是字符串 b 的子序列。

---------------------------------------------------

主要是判断是奇数还是偶数,然后依次去交换即可。

'

关键词:

X 关闭

X 关闭