新千题计划 11#：[CQOI 2018] 九连环
九连环 n n n 连环是一个 n n n 长全 0 序列，求使其变成全 1 序列的最小操作次数。一次变换改一个数，可改第 i i i 个数当且仅当 i = 1 i = 1 i=1 或 i i i 是序列中第一个 1 所在位置。
递推。 该数列已被 A000975 - OEIS 收录。
欲解 n n n 连环，需要 1）解 n − 1 n - 1 n−1 连环，即 111 ⋯ 10 111 \cdots 10 111⋯10；2）将前 n − 2 n - 2 n−2 位的 1 视为 0，反向解 n − 2 n - 2 n−2 连环，即 000 ⋯ 010 000 \cdots 010 000⋯010；3）将末位变为 1，即 000 ⋯ 011 000 \cdots 011 000⋯011；4）解 n − 2 n - 2 n−2 连环。故递推式为 a n = a n − 1 + 2 a n − 2 + 1 a_n = a_{n - 1} + 2a_{n - 2} + 1 an=an−1+2an−2+1，显然 a 1 = 1 , a 2 = 2 a_1 = 1, a_2 = 2 a1=1,a2=2。
我们用特征根法解通项公式。令 b n = a n + 1 2 b_n = a_n + \dfrac 1 2 bn=an+21，则 b n = b n − 1 + 2 b n − 2 , b 1 = 3 2 , b 2 = 5 2 b_n = b_{n - 1} + 2b_{n - 2}, b_1 = \dfrac 3 2, b_2 = \dfrac 5 2 bn=bn−1+2bn−2,b1=23,b2=25。其特征方程为 x 2 − x − 2 = 0 ⇒ x = − 1 or 2 x^2 - x - 2 = 0 \Rightarrow x = -1 \text{ or } 2 x2−x−2=0⇒x=−1 or 2，故通解为 b n = C 1 2 n + C 2 ( − 1 ) n b_n = C_1 2^n + C_2 (-1)^n bn=C12n+C2(−1)n，代入 b 1 , b 2 b_1, b_2 b1,b2 有 C 1 = 2 3 , C 2 = − 1 6 C_1 = \dfrac 2 3, C_2 = -\dfrac 1 6 C1=32,C2=−61，故 b n = 2 n + 1 3 − ( − 1 ) n 6 , a n = 2 n + 1 3 − ( − 1 ) n 6 − 1 2 b_n = \dfrac {2 ^ {n + 1}} 3 - \dfrac {(-1)^n} 6, a_n = \dfrac {2 ^ {n + 1}} 3 - \dfrac {(-1)^n} 6 - \dfrac 1 2 bn=32n+1−6(−1)n,an=32n+1−6(−1)n−21，容易改写成 ⌊ 2 3 ( 2 n − 1 ) ⌋ \lfloor \dfrac 2 3 (2^n - 1) \rfloor ⌊32(2n−1)⌋。
高精咕了，以下是 Python 代码。
m = int(raw_input())
while m > 0:n = int(raw_input())print int(((2 ** (n + 1)) - 2) / 3)m = m - 1
新千题计划 11#：[CQOI 2018] 九连环
九连环 n n n 连环是一个 n n n 长全 0 序列，求使其变成全 1 序列的最小操作次数。一次变换改一个数，可改第 i i i 个数当且仅当 i = 1 i = 1 i=1 或 i i i 是序列中第一个 1 所在位置。
递推。 该数列已被 A000975 - OEIS 收录。
欲解 n n n 连环，需要 1）解 n − 1 n - 1 n−1 连环，即 111 ⋯ 10 111 \cdots 10 111⋯10；2）将前 n − 2 n - 2 n−2 位的 1 视为 0，反向解 n − 2 n - 2 n−2 连环，即 000 ⋯ 010 000 \cdots 010 000⋯010；3）将末位变为 1，即 000 ⋯ 011 000 \cdots 011 000⋯011；4）解 n − 2 n - 2 n−2 连环。故递推式为 a n = a n − 1 + 2 a n − 2 + 1 a_n = a_{n - 1} + 2a_{n - 2} + 1 an=an−1+2an−2+1，显然 a 1 = 1 , a 2 = 2 a_1 = 1, a_2 = 2 a1=1,a2=2。
我们用特征根法解通项公式。令 b n = a n + 1 2 b_n = a_n + \dfrac 1 2 bn=an+21，则 b n = b n − 1 + 2 b n − 2 , b 1 = 3 2 , b 2 = 5 2 b_n = b_{n - 1} + 2b_{n - 2}, b_1 = \dfrac 3 2, b_2 = \dfrac 5 2 bn=bn−1+2bn−2,b1=23,b2=25。其特征方程为 x 2 − x − 2 = 0 ⇒ x = − 1 or 2 x^2 - x - 2 = 0 \Rightarrow x = -1 \text{ or } 2 x2−x−2=0⇒x=−1 or 2，故通解为 b n = C 1 2 n + C 2 ( − 1 ) n b_n = C_1 2^n + C_2 (-1)^n bn=C12n+C2(−1)n，代入 b 1 , b 2 b_1, b_2 b1,b2 有 C 1 = 2 3 , C 2 = − 1 6 C_1 = \dfrac 2 3, C_2 = -\dfrac 1 6 C1=32,C2=−61，故 b n = 2 n + 1 3 − ( − 1 ) n 6 , a n = 2 n + 1 3 − ( − 1 ) n 6 − 1 2 b_n = \dfrac {2 ^ {n + 1}} 3 - \dfrac {(-1)^n} 6, a_n = \dfrac {2 ^ {n + 1}} 3 - \dfrac {(-1)^n} 6 - \dfrac 1 2 bn=32n+1−6(−1)n,an=32n+1−6(−1)n−21，容易改写成 ⌊ 2 3 ( 2 n − 1 ) ⌋ \lfloor \dfrac 2 3 (2^n - 1) \rfloor ⌊32(2n−1)⌋。
高精咕了，以下是 Python 代码。
m = int(raw_input())
while m > 0:n = int(raw_input())print int(((2 ** (n + 1)) - 2) / 3)m = m - 1
![新千题计划 11#：[CQOI 2018] 九连环](/uploads/image/0387.jpg)
发布评论