『JROI-4』淘气的猴子

GitHub跳转原题关系图返回列表

按操作倒序逆推数组，普通加乘分别用减除还原，而自加与自乘要特判成除以 2 和开平方。

OJ: luogu

题目 ID: P8318

难度:普及-

标签:模拟思维

日期: 2026-06-18 23:28

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定猴子操作后的最终数组 b1..bn，以及猴子执行过的 m 次操作：

  • 1 x y：第 x 个数加上第 y 个数
  • 2 x y：第 x 个数乘上第 y 个数

要求还原出最初的数组 a1..an。

思路

先看一个最直观的朴素解：

如果数据很小，可以枚举原数组的每一项，再把所有操作正着模拟一遍，看最后能不能变成题目给出的数组。

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXM = 20;

int n, m;
long long b[MAXN];      // 输入给出的最终数组
int op[MAXM], x[MAXM], y[MAXM];
long long cur[MAXN];
long long ans[MAXN];
int found;

void simulate() {
    for (int i = 1; i <= m; i++) {
        if (op[i] == 1) {
            cur[x[i]] = cur[x[i]] + cur[y[i]];
        }
        else {
            cur[x[i]] = cur[x[i]] * cur[y[i]];
        }
    }
}

void dfs(int dep) {
    if (found) {
        return;
    }
    if (dep > n) {
        long long bak[MAXN];
        for (int i = 1; i <= n; i++) {
            bak[i] = cur[i];
        }

        simulate();

        bool ok = true;
        for (int i = 1; i <= n; i++) {
            if (cur[i] != b[i]) {
                ok = false;
                break;
            }
        }

        if (ok) {
            found = 1;
            for (int i = 1; i <= n; i++) {
                ans[i] = bak[i];
            }
        }

        for (int i = 1; i <= n; i++) {
            cur[i] = bak[i];
        }
        return;
    }

    for (int v = 1; v <= 4; v++) {
        cur[dep] = v;
        dfs(dep + 1);
        if (found) {
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> op[i] >> x[i] >> y[i];
    }

    dfs(1);

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

这个办法只能做很小的数据，但它给了我们一个关键启发：

既然正向操作是确定的，那么更自然的办法就是从最终数组开始，按操作倒序还原。

倒着看每一步：

  • 若原操作是 1 x y
    • 当 x != y 时，之前的 x = 现在的 x - 现在的 y
    • 当 x == y 时，这一步其实是 x = old_x + old_x，所以之前的 x = 现在的 x / 2
  • 若原操作是 2 x y
    • 当 x != y 时，之前的 x = 现在的 x / 现在的 y
    • 当 x == y 时，这一步其实是 x = old_x * old_x，所以之前的 x = sqrt(现在的 x)

注意 x == y 时不能直接套“减当前值”或“除当前值”，因为这个位置本身被这一步改掉了。

所以我们只要从第 m 个操作一直逆推到第 1 个操作，就能恢复原数组。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXM = 205;

int n, m;
long long a[MAXN];   // 当前维护的数组，初始读入的是最终结果 b
int op[MAXM], x[MAXM], y[MAXM];

// 还原平方操作时，求一个整数平方根。
long long isqrt_ll(long long v) {
    long long r = (long long) sqrtl((long double) v);
    while ((r + 1) * (r + 1) <= v) {
        r++;
    }
    while (r * r > v) {
        r--;
    }
    return r;
}

void solve() {
    for (int i = m; i >= 1; i--) {
        if (op[i] == 1) {
            if (x[i] == y[i]) {
                a[x[i]] /= 2;
            }
            else {
                a[x[i]] -= a[y[i]];
            }
        }
        else {
            if (x[i] == y[i]) {
                a[x[i]] = isqrt_ll(a[x[i]]);
            }
            else {
                a[x[i]] /= a[y[i]];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << a[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> op[i] >> x[i] >> y[i];
    }

    solve();

    return 0;
}

复杂度

每次操作只需要常数时间逆推一次，总时间复杂度是 O(m)O(m)，空间复杂度是 O(n+m)O(n + m)。

总结

这题的核心不是正着模拟，而是意识到“最终状态 + 操作记录”足够支持倒着还原。

真正容易错的地方只有一个：x == y 时要单独处理，自加对应除以 2，自乘对应开平方。