2020 函数调用 · 方案一直接模拟

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1772 字

数组 a[1..n] 初始给定

2020
拓扑

正文

// CSP-S 2020 复赛 T3 · 函数调用（方案一：直接模拟，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2020C
// 题意：数组 a[1..n] 初始给定。m 个函数：
//       类型 1：a[v] += val；类型 2：全部 a[i] *= val；类型 3：依次
//       调用 g_1..g_c（可嵌套）。Q 次操作，每次执行一个函数一次。
//       输出最终数组（mod 998244353）。
// 思路（模拟）：
//   递归执行：call(f) 按类型分派；类型 3 就按顺序递归 call(g_i)。
//   无记忆化、无标记传播，复杂度 = 实际执行的操作数总和。
//   测试点 1~2 / 8~9（调用链为树、ΣC = m-1）等部分分可过；
//   最坏嵌套深度 × 次数会超时。
// 复杂度：O(总执行的操作数)（最坏 O(Q · ΣC)）。
// 易错点：
//   1. 乘法取模别忘（val 可能很大）；
//   2. 递归深度可能很深，注意栈空间；
//   3. 多组操作叠加，数组元素全程用 long long 存模值。
#include <cstdio>
#include <vector>
using namespace std;

const int MOD = 998244353;
int n, m, q;
long long a[100005];
int type[100005];
long long val[100005];
vector<int> sons[100005];

void call(int f) {
    if (type[f] == 1) {
        a[pos1[f]] = (a[pos1[f]] + val1[f]) % MOD;
    } else if (type[f] == 2) {
        for (int i = 1; i <= n; i++) a[i] = a[i] * val1[f] % MOD;
    } else {
        for (int g : sons[f]) call(g);
    }
}

int main() {
    freopen("call.in", "r", stdin);
    freopen("call.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int f = 1; f <= m; f++) {
        scanf("%d", &type[f]);
        if (type[f] == 1) {
            scanf("%lld%lld", &pos1[f], &val1[f]);
        } else if (type[f] == 2) {
            scanf("%lld", &val1[f]);
        } else {
            int c;
            scanf("%d", &c);
            for (int j = 0; j < c; j++) {
                int g;
                scanf("%d", &g);
                sons[f].push_back(g);
            }
        }
    }
    scanf("%d", &q);
    while (q--) {
        int f;
        scanf("%d", &f);
        call(f);
    }
    for (int i = 1; i <= n; i++) printf("%lld ", a[i]);
    printf("\n");
    return 0;
}

2020 函数调用 · 方案一 直接模拟

正文

CSP-S 标程 · 复赛真题的其它内容

2020 函数调用 · 方案一直接模拟