「KDOI-06-J」翻转与反转 题解
Minions_love_dameile
·
·
题解
「KDOI-06-J」翻转与反转 题解
总起
各位大佬们好！
看了楼上的题解，觉得有些文字过多。
本蒟蒻想介绍一种仅使用初等代数知识的一种做法。
分析
读题发现，这道题主要分为两个部分：
我们可以分别解决这两个问题。
翻转
我们记 f(i, j) 表示以 i 为结尾的，下标为 j 的翻转后位置。（注：在这篇题解中，下标从 1 开始）
那么显然：
f(i, j) = i - j + 1
接下来，我们可以尝试“套娃”（更准确的说，我们继续计算 f(i+1, f(i,j)) ）
\begin{aligned}
f(i+1, f(i,j)) &= f(i+1, i - j + 1)\\
&= (i+1) - (i-j+1) + 1\\
&= j + 1
\end{aligned}
继续“套娃”：
\begin{aligned}
f(i+2, f(i+1, f(i,j))) &= f(i+2, j+1)\\
&= (i+2) - (j+1) + 1\\
&= i - j + 2
\end{aligned}
同理，我们可以得出多个这样的式子。
对比：
\begin{aligned}
f(i, \dots) &= i - j + 1 \\
f(i+1, \dots) &= j + 1 \\
f(i+2, \dots) &= i - j + 2 \\
f(i+3, \dots) &= j + 2
\end{aligned}
可以总结出：
对于 f(i+v, \dots)
v \bmod 2 = \begin{cases}
0 & f(i+v, \dots) = i - j + v / 2 + 1\\
1 & f(i+v, \dots) = j + v/2 + 1\text{（整除）}
\end{cases}