题解：P15294 [ROI 2012 Day 1] password 密码

违规用户名1377536 · 2026-05-10 17:06:48 · 题解

P15294 [ROI 2012 Day 1] password 密码 Solution

看到这道题发现就是个模拟，没别的了。

题目只说了一件事情：

• 把某一段数字替换为他的数位和。

我们需要枚举可能的数字段的长度，然后去和第二段数字匹配。

本来感觉要 \mathcal O(n^2) 了发现这段数字被替换之后最多有 \bm 6 位，所以内层循环只需要枚举 6 次了，是一个常数。

所以总复杂度 \mathcal O(n)。注意边界条件特判掉。

:::success[Code，不完整] 略去了变量定义。

int calc(int x, int y) {
    int sum = 0;
    for (int i = x; i <= y; i++) {
        sum = sum * 10 + t[i] - '0';
    }
    return sum;
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> s >> t;
    n = s.size(), m = t.size();
    s = " " + s, t = " " + t;
    lst[0] = 1;
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + s[i] - '0';
        if (lst[i - 1] && s[i] == t[i]) lst[i] = 1;
    }
    ne[0] = 1;
    for (int i = n, j = m, tmp = 1; j >= 1; j--, i--, tmp++) {
        if (ne[tmp - 1] && s[i] == t[j]) ne[tmp] = 1;
        else break;
    }
    for (int i = 1; i <= m; i++) {
        if (!lst[i - 1]) break;
        if (t[i] == '0') continue;
        for (int j = 1; j <= 6; j++) {
            if (i + j - 1 > m) continue;
            if (!ne[m-(i+j-1)]) continue;
            if (calc(i, i+j-1) == sum[n-m+(i+j-1)] - sum[i-1]) {
                cout << i << " " << n-m+(i+j-1) << endl;
                return 0;
            }
        }
    }
    return 0;
}

:::

完了？

完了。

玩 florr 去喽～

记得三连哦～