#5458. 「ROI 2012 Day 1」古代日历 题解

问题分析

我们有一个 $N \times M$ 的数字表格：

• 每行是一个 $M$ 位数字
• 第 $i+1$ 行 = 第 $i$ 行 $+ 1$（考虑 $M$ 位循环，$999...9 + 1 = 000...0$）
• 部分数字缺失（用 * 表示）
• 需要恢复第一行的数字

关键观察

1. 数字关系：如果知道第 $i$ 行的数字，可以推导出第 $i+1$ 行的数字（加1运算）
2. 约束传递：已知的数字会对其他行产生约束
3. 循环特性：$M$ 位数字是循环的，从 $999...9$ 到 $000...0$

算法思路

方法：从已知数字推导约束

设第 $i$ 行的数字为 $A_i$，则：

• $A_{i+1} = (A_i + 1) \mod 10^M$

对于每个位置 $(i,j)$：

• 如果该位置有数字 $d$，那么 $A_i$ 的第 $j$ 位必须是 $d$
• 通过这个约束，我们可以建立关于 $A_1$ 的方程

具体步骤

1. 建立约束系统：

   • 对于每个已知数字 $d$ 在位置 $(i,j)$
   • 设 $A_1 = x$，则 $A_i = (x + i - 1) \mod 10^M$
   • 所以 $x + i - 1$ 的第 $j$ 位必须等于 $d$

2. 处理循环：

   • 由于是 $M$ 位循环，需要考虑进位
   • $x + i - 1$ 可能产生进位，影响高位数字

3. 求解最小解：

   • 由于可能有多个解，我们寻找满足所有约束的最小 $x$
   • 从最低位到最高位逐位确定

算法实现

更实用的方法：逐位确定

由于 $M \times N \leq 100000$，我们可以直接模拟：

1. 初始化：设第一行为未知数 $x_0 x_1 ... x_{M-1}$

2. 处理已知数字：

   • 对于每个已知数字 $d$ 在位置 $(i,j)$
   • 计算 $A_i$ 的第 $j$ 位应该是 $(A_1 + i - 1)$ 的第 $j$ 位
   • 这给出了 $x$ 必须满足的条件

3. 解决冲突：

   • 如果同一个位置有多个已知数字产生冲突，调整进位
   • 从最低位开始处理，逐步向高位传播进位

代码框架

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<string> table(N);
    for (int i = 0; i < N; i++) {
        cin >> table[i];
    }
    
    // 结果数组，存储第一行的数字
    vector<int> result(M, -1); // -1 表示未知
    
    // 处理每一行的约束
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (table[i][j] != '*') {
                int digit = table[i][j] - '0';
                
                // 第i行第j位 = (第一行 + i) 的第j位
                // 考虑进位的影响
                // 这里需要复杂的进位处理逻辑
            }
        }
    }
    
    // 输出结果，未知位填0（或其他满足条件的数字）
    for (int j = 0; j < M; j++) {
        if (result[j] == -1) {
            cout << '0';
        } else {
            cout << result[j];
        }
    }
    cout << endl;
    
    return 0;
}