Codeforces Round 879 (Div. 2) 题解

发布时间 2023-06-19 22:41:04作者: SF71-H

寄!大!了!

Rating -= 124.

image

(恼)

https://codeforces.com/contest/1834

C. Game with Reversing

发现 \(\text{rev}(S) \to S\)\(\text{rev}(T) \to T\) 本质上是一样的。

赛时就一个劲的对着 \(S\) 操作,,,。

我们考虑单点修改在 \(S\) 上做,翻转操作在 \(T\) 上做。

\(\displaystyle diff(S, T) = \sum_{i = 1} ^ {|S|} [S_i \neq T_i]\)

  • \(T\) 的翻转次数为偶数,答案就是 \(diff(S, T)\) 再加上翻转次数,如果翻转次数是奇数,就再加 \(1\)。(注:翻转次数 = \(\max(0, diff(S, T) - 1)\)。)

  • \(T\) 的翻转次数为奇数,答案就是 \(diff(S, \text{rev}(T))\) 再加上翻转次数,如果翻转次数是偶数,就再加 \(1\);如果 \(diff(S, \text{rev}(T)) = 0\),答案就是 \(2\)。(注:翻转次数 = \(\max(0, diff(S, \text{rev}(T)) - 1)\)。)