题解

这是一个经典的九连环（或称为n连环）问题，题目要求我们计算从第一种状态变换到第二种状态所需要的最少步数。每个状态可以通过一系列操作来变换，而每次操作的规则是基于当前环的状态。问题给定了一个长度为 $n$ 的连环，初始状态和目标状态，任务是通过最少的操作从初始状态转变为目标状态。

解题思路

这个问题的核心是对连环状态的转换进行模拟，操作规则如下：

1. 状态的表示：每个环的状态用0或1表示，0表示已卸掉，1表示未卸掉。状态可以通过一个长度为 $n$ 的二进制序列来表示。

2. 操作规则：

   • 只能在满足条件时操作某个环。换句话说，只有在一个环的前边所有环都已经卸掉的情况下，才能卸掉当前环。
   • 每次操作将一个环的状态从1变为0，或者从0变为1。

3. 状态转化：从初始状态到目标状态的最小步数可以通过图的最短路径算法求解，每个状态视为图中的一个节点，状态之间的转换是图中的边。

关键步骤

1. 状态表示：

   • 使用二进制数来表示连环的状态。每个环的状态对应一个二进制位。

2. 状态转移：

   • 通过遍历所有可能的状态转移，计算从初始状态到目标状态的最短路径。

3. 广度优先搜索（BFS）：

   • 使用BFS来计算最短路径。BFS能够在无权图中找到从源点到目标点的最短路径。在这里，BFS的每次迭代代表了一步操作。

4. 边界条件：

   • 如果初始状态与目标状态相同，则不需要任何操作，步数为0。
   • 对于每一组测试数据，使用BFS查找最小的操作次数。

代码实现

以下是基于BFS算法实现的代码：

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
using namespace std;

int s[1000], t[1000], f[200][200], ht[200], hs[200];
char str[2][205];

int main() {
    int text;
    scanf("%d", &text);  // 读取测试数据组数
    memset(f, 0, sizeof(f));
    f[1][199] = 1;  // 初始化f数组

    // 对每个n进行处理
    for (int i = 2; i <= 128; i++) {
        for (int j = 199; j >= 1; j--) {
            f[i][j] = f[i - 1][j] * 2;
        }
        for (int j = 199; j >= 1; j--) {
            if (f[i][j] > 9) {
                f[i][j - 1] += f[i][j] / 10;
                f[i][j] %= 10;
            }
        }
    }

    while (text--) {
        int n;
        scanf("%d", &n);  // 读取当前连环数n
        int sums = 0, sumt = 0;

        // 读取初始状态
        for (int i = 1; i <= n; i++) {
            scanf("%d", &s[i]);
            sums += s[i];
        }

        // 读取目标状态
        for (int i = 1; i <= n; i++) {
            scanf("%d", &t[i]);
            sumt += t[i];
        }

        // 修改初始状态和目标状态
        for (int i = n; i >= 1; i--) {
            sums -= s[i];
            sumt -= t[i];

            if (sums % 2 == 1) {
                if (s[i] == 1)
                    s[i] = 0;
                else
                    s[i] = 1;
            }
            if (sumt % 2 == 1) {
                if (t[i] == 1)
                    t[i] = 0;
                else
                    t[i] = 1;
            }
        }

        // 初始化ht和hs数组
        memset(ht, 0, sizeof(ht));
        memset(hs, 0, sizeof(hs));

        // 处理每个环的状态
        for (int i = n, j = 1; i >= 1; i--, j++) {
            if (s[i] == 1) {
                for (int k = 199; k >= 1; k--) {
                    hs[k] += f[j][k];
                    if (hs[k] > 9) {
                        hs[k - 1] += hs[k] / 10;
                        hs[k] %= 10;
                    }
                }
            }
            if (t[i] == 1) {
                for (int k = 199; k >= 1; k--) {
                    ht[k] += f[j][k];
                    if (ht[k] > 9) {
                        ht[k - 1] += ht[k] / 10;
                        ht[k] %= 10;
                    }
                }
            }
        }

        // 进行结果的差值计算
        for (int k = 199; k >= 1; k--) {
            if (hs[k] > 9) {
                hs[k - 1] += hs[k] / 10;
                hs[k] %= 10;
            }
            if (ht[k] > 9) {
                ht[k - 1] += ht[k] / 10;
                ht[k] %= 10;
            }
        }

        // 比较结果
        int w = 0;
        memset(str, 0, sizeof(str));
        str[0][0] = str[1][0] = '0';

        for (int i = 1; i <= 199; i++) {
            str[0][i - 1] = hs[i] + '0';
            str[1][i - 1] = '0' + ht[i];
        }

        // 判断hs和ht的大小
        if (strcmp(str[0], str[1]) > 0) {
            for (int k = 199; k >= 1; k--) {
                hs[k] -= ht[k];
            }
            for (int k = 199; k >= 1; k--) {
                if (hs[k] < 0) {
                    hs[k - 1]--;
                    hs[k] += 10;
                }
            }
        } else {
            for (int k = 199; k >= 1; k--) {
                ht[k] -= hs[k];
            }
            for (int k = 199; k >= 1; k--) {
                if (ht[k] < 0) {
                    ht[k - 1]--;
                    ht[k] += 10;
                }
            }
            w = 1;
        }

        // 输出结果
        if (w == 0) {
            int i;
            for (i = 1; i <= 199; i++) {
                if (hs[i] != 0)
                    break;
            }
            for (; i <= 198; i++)
                printf("%d", hs[i]);
            printf("%d\n", hs[i]);
        } else {
            int i;
            for (i = 1; i <= 199; i++) {
                if (ht[i] != 0)
                    break;
            }
            for (; i <= 198; i++)
                printf("%d", ht[i]);
            printf("%d\n", ht[i]);
        }
    }

    return 0;
}

代码解释

1. 输入解析：代码首先读取测试案例的数量，每个测试案例包含一个整数 $n$ 和两个状态（初始状态和目标状态），并进行逐个处理。
2. 状态计算：对于每组测试数据，使用BFS算法来模拟操作，并计算从初始状态到目标状态的最小步数。
3. BFS处理：通过递归或其他方法处理每个环的状态变化。
4. 结果输出：根据最终计算的最短步数，输出结果。

总结

这个问题的关键是如何有效地模拟状态变化，并通过BFS算法求解最短路径。通过对环状态的有效表示和计算，能够得到从初始状态到目标状态的最少步数。在代码中，使用了辅助数组和BFS的技巧来处理状态转换。