问题背景

题目描述了一个关于锁的密码问题。锁由多个拨号盘和齿轮组成，每个拨号盘可以控制若干个齿轮的旋转。目标是通过拨动拨号盘，使所有齿轮的顶部齿达到指定的密码状态。我们需要判断是否能够通过有限次拨动达到目标，并求出最少的拨动次数。

问题分析

1. 问题建模：

   • 锁的状态可以用一个向量表示，每个齿轮的当前状态是一个数字（1 到 N）。
   • 每个拨号盘的拨动可以看作是对齿轮状态的线性变换。
   • 目标是找到一组拨号盘的拨动次数，使得齿轮的状态从初始状态（全为1）变为目标密码状态。

2. 难点：

   • 拨号盘的拨动次数可以是任意非负整数，且每个拨号盘可以被多次拨动。
   • 需要处理模 N 的线性方程组，因为齿轮的旋转是循环的。

3. 解题思路：

   • 使用高斯消元法（Gaussian Elimination）来处理模 N 的线性方程组。
   • 通过深度优先搜索（DFS）枚举可能的解，找到最小的拨动次数。

代码解析

1. 输入处理：

   • 读取输入的 K 和 N，以及密码和每个拨号盘控制的齿轮信息。
   • 将密码和齿轮的旋转信息存储到矩阵 A 中，其中 A[i][K] 表示第 i 个齿轮的目标状态。

2. 高斯消元法：

   • 高斯消元法用于将线性方程组化简为上三角矩阵。
   • 由于涉及模 N 的运算，不能直接使用除法，而是通过辗转相除法（类似欧几里得算法）来消元。

3. 深度优先搜索（DFS）：

   • 从最后一个方程开始，尝试所有可能的解。
   • 对于每个可能的解，递归地检查前一个方程是否满足条件。
   • 如果找到一个解，更新最小拨动次数。

4. 输出结果：

   • 如果找到解，输出最小拨动次数。
   • 如果没有找到解，输出 "No solution"。

代码详解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>  // 包含 Cpp98 标准输入输出库 
using namespace std;

typedef long long ll;

const int maxn = 25;  // 最大拨号盘和齿轮数量
const int INF = 1000000007;  // 一个足够大的数，表示无穷大

int n, K;  // n: 齿轮的齿数；K: 拨号盘数量
int a[maxn];  // 用于存储中间结果
int A[maxn][maxn];  // 线性方程组的增广矩阵
int ans;  // 存储最小拨动次数

// 高斯消元法，用于化简线性方程组
void Gauss() {
    int i, j, k, r;
    for (i = 0; i < K; ++i) {
        r = i;  // 当前行
        // 找到当前列第一个非零行
        for (j = i + 1; j < K; ++j)
            if (A[j][i])
                r = j;
        if (A[r][i] == 0)  // 如果当前列全为0，跳过
            continue;
        if (r != i)  // 如果非零行不在当前行，交换行
            for (j = 0; j <= K; ++j)
                swap(A[i][j], A[r][j]);

        // 对下方的行进行消元
        for (j = i + 1; j < K; ++j) {
            if (j != i) {
                // 使用辗转相除法消元，避免除法（模代数系统）
                while (A[j][i]) {
                    int rate = A[i][i] / A[j][i], tmp;
                    for (k = 0; k <= K; ++k) {
                        tmp = A[j][k];
                        A[j][k] = ((A[i][k] - rate * A[j][k]) % n + n) % n;  // 模 N 运算
                        A[i][k] = tmp;
                    }
                }
            }
        }
    }
}

int t[maxn][maxn], val[maxn];  // 用于保存状态和存储中间结果

// 深度优先搜索，用于枚举所有可能的解
void dfs(int pos, int res) {
    if (res >= ans)  // 剪枝：如果当前结果已经大于等于最小值，直接返回
        return;
    if (pos == -1) {  // 找到一个解
        ans = res;
        return;
    }

    // 保存当前状态
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j <= K; ++j) {
            t[i][j] = A[i][j];
        }
    }

    // 枚举当前拨号盘的拨动次数
    for (int i = 0; i < n; ++i) {
        val[pos] = i;  // 当前拨号盘的拨动次数
        int now = 0;
        // 计算当前行的值
        for (int j = pos; j < K; ++j) {
            now = (now + A[pos][j] * val[j]) % n;
        }
        // 如果满足条件，递归处理上一行
        if (now % n == A[pos][K] % n)
            dfs(pos - 1, res + i);
    }

    // 恢复状态
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j <= K; ++j) {
            A[i][j] = t[i][j];
        }
    }
}

// 自定义读取函数，用于读取整数
ll read() {
    ll s = 0, f = 1;  // s: 结果，f: 符号
    char ch = getchar();  // 逐字符读取
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;  // 处理负数
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';  // 构造整数
        ch = getchar();
    }
    return s * f;  // 返回结果
}

int main() {
    // 多组测试用例
    while (scanf("%d%d", &K, &n) == 2 && K) {
        memset(val, 0, sizeof(val));  // 初始化中间结果数组
        memset(A, 0, sizeof(A));  // 初始化增广矩阵
        int x;
        // 读取密码
        for (int i = 0; i < K; ++i) {
            scanf("%d", &x);
            A[i][K] = n + 1 - x;  // 密码转换为目标状态
        }

        int p, u, v;
        // 读取每个拨号盘控制的齿轮信息
        for (int i = 1; i <= K; ++i) {
            scanf("%d", &p);  // 当前拨号盘控制的齿轮数量
            for (int j = 1; j <= p; ++j) {
                scanf("%d%d", &u, &v);  // 齿轮编号和旋转齿数
                A[u - 1][i - 1] = v;  // 填充增广矩阵
            }
        }

        Gauss();  // 高斯消元化简方程组
        ans = INF;  // 初始化最小拨动次数为无穷大
        dfs(K - 1, 0);  // 深度优先搜索枚举解

        // 输出结果
        if (ans == INF) {
            printf("No solution\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

解题过程

1. 高斯消元：

   • 将线性方程组化简为上三角矩阵，便于后续求解。
   • 使用辗转相除法避免除法操作，确保所有运算都在模 N 的范围内。

2. 深度优先搜索：

   • 从最后一个方程开始，逐个尝试每个拨号盘的拨动次数。
   • 通过递归检查前一个方程是否满足条件，找到所有可能的解。
   • 使用剪枝技术（如果当前结果已经大于等于最小值，则直接返回）来优化搜索过程。

3. 输出结果：

   • 如果找到解，输出最小拨动次数。
   • 如果没有找到解，输出 "No solution"。

示例解析

输入数据 1：

1 4  
2  
1 1 2  
4 8  
8 8 8 8  
4 1 1 2 2 4 1 3 1  
2 4 7 3 2  
2 1 5 3 5  
1 2 7  
0 0

输出数据 1：

No solution  
2

解析：

• 第一个测试用例：

  • K = 1, N = 4，密码为 [2]。
  • 拨号盘 1 控制齿轮 1，旋转 2 个齿。
  • 目标状态是齿轮 1 的顶部齿为 2。
  • 通过拨动拨号盘 1 一次即可达到目标，但代码中没有找到解，输出 "No solution"。

• 第二个测试用例：

  • K = 4, N = 8，密码为 [8, 8, 8, 8]。
  • 每个拨号盘控制的齿轮和旋转齿数如下：
    • 拨号盘 1：齿轮 1 旋转 1，齿轮 2 旋转 2，齿轮 4 旋转 1。
    • 拨号盘 2：齿轮 2 旋转 4，齿轮 3 旋转 7。
    • 拨号盘 3：齿轮 1 旋转 3，齿轮 3 旋转 5。
    • 拨号盘 4：齿轮 2 旋转 7。
  • 通过高斯消元和深度优先搜索，找到最小拨动次数为 2。

总结

本题是一个典型的线性方程组求解问题，结合了高斯消元法和深度优先搜索。通过高斯消元化简方程组，再通过深度优先搜索枚举可能的解，最终找到最小的拨动次数。