模板展开

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

只维护变量值的长度，直接赋值立即求值，间接赋值保存操作数并在使用时递归展开。

OJ: shumeng

题目 ID: CSP202503C

难度:普及+/提高-

标签:模拟递归字符串

日期: 2026-07-31 16:21

形式化题目

有 $n$ 条语句按顺序执行，每条语句是下列三种之一：

1 <var> <expr>：直接赋值，求表达式的值作为变量当前值；
2 <var> <expr>：间接赋值，只记录表达式，使用时再求；
3 <var>：输出变量当前值的长度对 $10^9+7$ 取模的结果。

表达式由空格分隔的操作数拼接而成，$x 表示变量 $x$ 的值，其余为普通字符串。变量初始值为空串，依赖关系保证无环。

思路

真正需要的只有每个变量"当前值的长度"，字符串内容完全不参与后续计算，因此全程只维护长度。

直接赋值与间接赋值的区别

直接赋值：立即求表达式，之后长度固定，不受其它变量后续变化影响。
间接赋值：保存操作数列表。每次用到该变量时都要重新展开它依赖的变量，因此它的长度会随依赖变量的更新而动态变化。

朴素递归解释器

先用一个不带缓存的递归解释器验证语义：遇到间接变量就递归展开它的表达式。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:49
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

struct Variable {
    int type;
    long long length;
    vector<string> expression;
};

map<string, int> ids;
vector<Variable> variables;

int get_id(const string &name) {
    map<string, int>::iterator it = ids.find(name);
    if (it != ids.end()) return it->second;
    int id = (int)variables.size();
    Variable variable;
    variable.type = 0;
    variable.length = 0;
    variables.push_back(variable);
    ids[name] = id;
    return id;
}

// 朴素递归求值：不做任何缓存，每次遇到间接变量都重新展开其依赖变量
long long evaluate(int id) {
    if (variables[id].type == 0) return 0;
    if (variables[id].type == 1) return variables[id].length;

    long long answer = 0;
    for (int i = 0; i < (int)variables[id].expression.size(); i++) {
        string operand = variables[id].expression[i];
        if (!operand.empty() && operand[0] == '$') {
            answer += evaluate(get_id(operand.substr(1)));
        } else {
            answer += (long long)operand.size();
        }
        answer %= MOD;
    }
    return answer;
}

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

    int n;
    cin >> n;
    string line;
    getline(cin, line);
    for (int statement = 0; statement < n; statement++) {
        getline(cin, line);
        stringstream input(line);
        int operation;
        string name;
        input >> operation >> name;
        int id = get_id(name);
        if (operation == 3) {
            cout << evaluate(id) << '\n';
            continue;
        }

        vector<string> expression;
        string operand;
        while (input >> operand) expression.push_back(operand);
        if (operation == 1) {
            long long value = 0;
            for (int i = 0; i < (int)expression.size(); i++) {
                if (!expression[i].empty() && expression[i][0] == '$') {
                    value += evaluate(get_id(expression[i].substr(1)));
                } else {
                    value += (long long)expression[i].size();
                }
                value %= MOD;
            }
            variables[id].type = 1;
            variables[id].length = value;
            variables[id].expression.clear();
        } else {
            variables[id].type = 2;
            variables[id].expression = expression;
        }
    }
    return 0;
}

用时间戳缓存加速

递归展开中同一个变量可能被多次求值。给每次"表达式求值"分配一个递增时间戳 stamp，把本轮已经算出的长度缓存下来；下一轮开始时时间戳改变，缓存自动失效。由于依赖无环，缓存不会造成错误。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:49
 */
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

struct Variable {
    int type;               // 0 未赋值(空串)  1 直接赋值(固定长度)  2 间接赋值(保存表达式)
    long long fixed_length; // type==1 时保存的值长度
    vector<string> expression; // type==2 时保存的操作数列表
};

map<string, int> variable_id;   // 变量名 -> 编号
vector<Variable> variables;     // 所有变量，编号从 0 开始
vector<long long> memo;         // 最近一次求值时该变量的长度缓存
vector<int> seen;               // 标记变量在哪一轮求值中被缓存
int evaluation_stamp = 0;       // 当前求值轮次的时间戳

// 获取变量编号，不存在则新建一个空变量
int get_variable_id(const string &name) {
    map<string, int>::iterator it = variable_id.find(name);
    if (it != variable_id.end()) return it->second;

    int id = (int)variables.size();
    Variable variable;
    variable.type = 0;
    variable.fixed_length = 0;
    variables.push_back(variable);
    variable_id[name] = id;
    memo.push_back(0);
    seen.push_back(0);
    return id;
}

// 求一个变量当前值的长度；同一轮求值内用时间戳缓存避免重复展开
long long evaluate_variable(int id) {
    if (seen[id] == evaluation_stamp) return memo[id];

    long long answer = 0;
    if (variables[id].type == 1) {
        // 直接赋值：长度固定
        answer = variables[id].fixed_length;
    } else if (variables[id].type == 2) {
        // 间接赋值：逐个展开操作数，$ 开头的操作数递归求对应变量
        for (int i = 0; i < (int)variables[id].expression.size(); i++) {
            string operand = variables[id].expression[i];
            if (!operand.empty() && operand[0] == '$') {
                answer += evaluate_variable(get_variable_id(operand.substr(1)));
            } else {
                answer += (long long)operand.size();
            }
            answer %= MOD;
        }
    }

    seen[id] = evaluation_stamp;
    memo[id] = answer;
    return answer;
}

// 求一个表达式的长度：普通字符串贡献字符数，$x 贡献变量 x 当前值的长度
long long evaluate_expression(const vector<string> &expression) {
    evaluation_stamp++;
    long long answer = 0;
    for (int i = 0; i < (int)expression.size(); i++) {
        const string &operand = expression[i];
        if (!operand.empty() && operand[0] == '$') {
            answer += evaluate_variable(get_variable_id(operand.substr(1)));
        } else {
            answer += (long long)operand.size();
        }
        answer %= MOD;
    }
    return answer;
}

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

    int n;
    cin >> n;
    string line;
    getline(cin, line);

    for (int statement = 0; statement < n; statement++) {
        getline(cin, line);
        stringstream input(line);
        int operation;
        string name;
        input >> operation >> name;
        int id = get_variable_id(name);

        // 输出语句：打印该变量当前值的长度模 MOD
        if (operation == 3) {
            evaluation_stamp++;
            cout << evaluate_variable(id) << '\n';
            continue;
        }

        vector<string> expression;
        string operand;
        while (input >> operand) expression.push_back(operand);

        if (operation == 1) {
            // 直接赋值：立刻求值并保存固定长度
            long long value = evaluate_expression(expression);
            variables[id].type = 1;
            variables[id].fixed_length = value;
            variables[id].expression.clear();
        } else {
            // 间接赋值：只保存表达式，使用时再动态求值
            variables[id].type = 2;
            variables[id].expression = expression;
        }
    }

    return 0;
}

复杂度

设一次表达式求值访问了 $V$ 个变量、处理 $T$ 个操作数，则本次求值为 $O(V+T)$ ；每条语句至多触发一次求值，总时间复杂度为 $O(n)$ 级别，空间复杂度为 $O(n)$ 。

总结

间接赋值的本质是"保存表达式而不是保存结果"。把字符串替换成长度后，问题就变成带动态依赖的递归求值；用时间戳缓存可以避免同一轮内的重复展开，且无需显式清空缓存数组。

题目来自第 37 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛信息中心主持了岛上的信息化工作，为各个部门提供信息化服务。不同部门所需要的信息化服务内容各有不同，但是其中存在着一个共同的需求：通过模板生成文档。为了满足这个需求，信息中心开发了一个通用的文档模板系统。

模板系统有若干输入参数，这些参数都是字符串，模板系统根据模板，将这些字符串拼接为最终的输出。为了让模板系统能够支持更复杂的需求，信息中心决定开发一种模板语言，这种模板语言重点支持变量和其代换。

你的任务是能够读取这种模板语言，并按照模板语言的规则生成相应输出。

题目描述

模板语言涉及到的数据是字符串。我们约定，字符串是由零个或多个小写字母和数字（[a-z0-9]）组成的序列。

模板语言中的变量的名称是非空字符串，且变量的值也是字符串。在模板开始执行前，所有变量的值都是空字符串。

模板语言中的表达式涉及对变量的值和字符串进行拼接操作。表达式由空格分隔的若干个操作数组成，操作数可以是变量或非空字符串；

其中如果操作数的第一个字符是美元符号($)，则表示该操作数是一个变量，操作数的剩余部分为该变量的名称；否则，表示该操作数是一个字符串。

表达式的值是指先将表达式中的所有变量替换为其值，然后将所有操作数拼接在一起得到的字符串。

例如，假设有变量 a 的值为 hello，变量 b 的值为 world，则：

表达式 a 的值为 a；
表达式 $a 的值为 hello；
表达式 a b 的值为 ab；
表达式 $a b 的值为 hellob；
表达式 $a $b 的值为 helloworld；
表达式 $a $b a 的值为 helloworlda。

模板语言由一系列语句组成，每个语句占一行，每个语句按顺序执行。语句分为两类：赋值语句和输出语句。其中，赋值语句用于将变量和表达式关联起来，输出语句用于输出变量的值。赋值语句分为两种：直接赋值和间接赋值。

直接赋值语句的形式为空格分隔的数字 1、变量名称和表达式，形如 1 <var> <expr>，表示求表达式的值并将该值作为变量的值。

例如，语句 1 c $a $b 执行后，变量 c 的值为 helloworld。

间接赋值语句的形式为空格分隔的数字 2、变量名称和表达式，形如 2 <var> <expr>，表示暂时不求表达式的值，而是将该表达式与变量相对应。待到后续求其它表达式的值需要用到该变量时，再求该变量对应的表达式的值并将该值作为变量的值用于求所求的表达式的值。

例如考虑以下模板：

plain

1
2
3
4
5
61 a hello
1 b world
2 c $a $b
1 d good $c
1 a hi
1 e good $c

在执行第三个语句 2 c $a $b 时，变量 c 与表达式 $a $b 对应起来，但并不求表达式的值。

在执行第四个语句 1 d good $c 时，需要求表达式 good $c 的值，并将该值作为变量 d 的值。

此时需要用到变量 c，因此需要先求表达式 $a $b 的值，即 helloworld，然后再和 good 拼接得到 goodhelloworld。

因此，执行完第四个语句后，变量 d 的值为 goodhelloworld。在执行第五个语句 1 a hi 时，变量 a 的值被更新为 hi。

在执行第六个语句 1 e good $c 时，需要求表达式 good $c 的值，需要用到变量 c，此时仍要重新求表达式 $a $b 的值，即 hiworld，然后再和 good 拼接得到 goodhiworld。因此，执行完第六个语句后，变量 e 的值为 goodhiworld。

需要注意的是，虽然变量 c 没有被重新赋值，但由于 c 是间接赋值的，所以在每次用到 c 时都要重新求表达式 $a $b 的值，即 c 的值是动态的。

输出语句的形式为空格分隔的数字 3 和变量名称，形如 3 <var>，表示输出一行，内容为变量的值的长度除以 $10^9+7$ 的余数。例如，语句 3 d 表示输出变量 d 的值的长度。

用输出语句修改上述例子的模板：

plain

1
2
3
4
5
61 a hello
1 b world
2 c $a $b
3 c
1 a hi
3 c

将会输出：10 和 7，对应的变量的值为：

plain

1
2helloworld
hiworld

需要注意的是，在使用间接赋值语句时，在变量的值之间建立了依赖关系，在上述模板中，变量 c 的值依赖于变量 a 和 b 的值。

可以想见，如果变量的值间的依赖关系形成了环，那么模板将无法执行。我们约定，给定的表达式中不存在这样的环。

形式化地，模板语言用 BNF 表示如下：

plain

1
2
3
4
5
6
7
8
9
10
11
12CHAR ::= [a-z0-9]
SPACE ::= ' '
DOLLAR ::= '$'
NONEMPTY_STRING ::= CHAR | NONEMPTY_STRING CHAR
STRING ::= '' | NONEMPTY_STRING
VAR ::= NONEMPTY_STRING
OPERAND ::= DOLLAR VAR | NONEMPTY_STRING
EXPR ::= OPERAND | EXPR SPACE OPERAND
ASSIGN_OP ::= '1' | '2'
ASSIGN ::= ASSIGN_OP SPACE VAR SPACE EXPR
OUTPUT ::= '3' SPACE VAR
STATEMENT ::= ASSIGN | OUTPUT

输入格式

从标准输入读入数据。

输入的第一行为一个整数 $n$ ，表示模板语言的语句数量。接下来的 $n$ 行，每行为一个语句，语句的格式如上所述。

输出格式

输出到标准输出。

依次执行输入的语句：如果语句为输出语句，则相应输出一行变量的值的长度除以 $10^9+7$ 的余数。

input1

1
2
3
4
5
6
76
1 a hello
1 b world
2 c $a $b
3 c
1 a hi
3 c

output1

1
210
7

样例 1 解释

本样例即为题目描述中的例子。

input2

1
2
3
4
5
65
1 var value
3 var
3 val
1 var $var $val $var
3 var

output2

样例 2 解释

执行第一条语句后，变量 var 的值为 value，因此第二条语句输出 5；执行第三条语句时，变量 val 并未被赋值，因此其值为初始的空字符串，输出 0；执行第四条语句后，变量 var 的值为 valuevalue，因此第五条语句输出 10。

子任务

全部的数据满足：变量的总数不超过 1000 个，且每个变量的名称、字符串的长度不超过 50 个字符。

测试点编号	$n \le$	语句类型	表达式的性质
$1\sim 2$	$200$	无间接赋值语句	每个表达式仅有 1 个字符串操作数
$3\sim 4$	$200$	无间接赋值语句	每个表达式仅有 1 个操作数
$5\sim 6$	$200$	无间接赋值语句	每个表达式包含不超过 100 个操作数
$7\sim 8$	$200$	包含所有类型语句	每个表达式包含不超过 100 个操作数
$9\sim 10$	$2000$	包含所有类型语句	每个表达式包含不超过 100 个操作数

模板展开

目录

形式化题目

思路

直接赋值与间接赋值的区别

朴素递归解释器

用时间戳缓存加速

代码

复杂度

总结