CSP202503C题解
CSP202503C题题解
CSP202503C 模板展开
1.如何存储变量
变量名是非空字符串，且每个变量名都没有重复，不难想到使用unordered_map来存储变量并自动去重
60分做法
如果只考虑直接赋值语句，每个变量对应的值就是一个确定的字符串，我们可以使用unordered_map<string,string>
80分做法
考虑间接赋值语句，间接赋值后变量对应的值是一个表达式，也就是一个vector<string>，相应的，我们使用unorderedmap<string,vector<string>>
2.如何求值
20分做法
根据题意先计算出相应的字符串，然后取字符串的长度，不过题目都说了要取模，长度一定是非常夸张的，所以这么做只能拿20分
80分做法
注意到题目只要我们求字符串的长度，并不关心到底是什么样的字符串，很自然的想法就是把字符串常量直接转化为整数存储，但是我们的unordered_map存储的是vector<string>，变量名是字符串，为了表达式形式统一我们还需要使用to_string()和stoi()两个函数在整数和字符串之间转化
这样在求表达式值的时候，遇到变量字符串（以$开头）就递归地求变量的长度，遇到常量字符串（不以$开头）就使用stoi()函数求出长度，最后把所有长度边加边取模，就得到了表达式值
100分做法 记忆化搜索
最后两个测试点会TLE的原因很简单，考虑一个变量间接赋值了一百个变量，一百个变量又各自间接赋值了一百个变量，这样求值操作的时间复杂度是指数级的。
我们注意到，变量的值虽然是动态的，但是在求值过程中，所有变量的值都不会改变。使用记忆化搜索的办法就可以保证所有变量最多求一次值
这里我做了一个操作，使用unordered_map<string,int>将每个变量唯一映射为一个正数id，这样存储变量值的容器就可以使用vector<vector<int>>，第一维表示id唯一对应的表达式，第二维表示表达式内的每个操作数。操作数中正数表示常量字符串的长度，负数去掉负号表示变量的id。
这样就把常量字符串和变量区分开来了，不用再使用字符串和变量的转换函数。求表达式值函数的输入也直接换成整数id，这样变量只有在输入时进行一次哈希映射的插入操作，有O(logn)的时间复杂度，之后都以整数id存储，查询到对应表达式的时间复杂度缩减为O(1)
做完这个映射之后，记忆化搜索就很简单了，直接使用vector<int>来存储已经搜索过的id的值，每轮开始时所有元素初始化为-1，求出结果后存储，下一次搜索id时就可以直接返回。
AC代码
我并非专业Oier所以代码变量名可能有些繁琐且混乱，请求轻喷
细节
使用getline函数一次读取一行，再包装成字符流避免读取到下一行的内容
insert方法的使用：向map中插入一个键值对时，如果键已经存在不会改变值的内容，这样就保证了每个变量的id一旦分配就不会改变。
insert方法返回一个pair，第一个元素为map的迭代器，指向新插入的元素或旧有元素，第二个元素为布尔值，表示插入是否成功
我们在每次输入一个变量名的时候调用一次insert方法，如果是一个全新的变量，就会分配一个新的id，如果是已经插入的变量我们也可以得到它被分配的id
间接赋值语句中的常量值也是不变的，且字符串拼接后的长度满足交换律，因此没有必要存储所有常量值，可以把所有常量字符串的长度压缩为一个整数存储
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <sstream>
#define MOD 1000000007
using namespace std;
vector<vector<long long int>>value(1);//存储表达式
unordered_map<string, int>var_to_int;//变量名到id的映射
vector<long long int> mem;//记忆化搜索数组
long long int get_value(int id)//求表达式值函数
{
if (mem[id] != -1) return mem[id];
int ret = 0;
for (auto it : value[id])
{
if (it < 0) ret += get_value(-it);
else ret += it;
ret %= MOD;
}
mem[id] = ret;
return ret;
}
int num = 1;//已有变量的个数
int get_id(string var_name)//查询id，如果是新变量则分配一个新的id
{
int id;
auto p = var_to_int.insert({ var_name,num });
if (p.second)//插入成功，表明插入了新变量，分配一个新的id
{
id = num++;
value.push_back(vector<long long int>());
mem.push_back(-1);//插入新变量时对表达式数组和记忆化数组扩容，避免越界
}
else//插入失败，返回已分配的id
{
id = p.first->second;
}
return id;
}
int main()
{
ios::sync_with_stdio(false);
string line;
int t; cin >> t; getline(cin, line); int turn = 0;
int opt;
string var_name;
string var_value;
while (getline(cin, line) && ++turn <= t)
{
stringstream ss(line);//每行包装为字符流，避免读取下一行内容
ss >> opt;
mem = vector<long long int>(num, -1);//重置记忆化搜索数组
if (opt == 1)
{
ss >> var_name;
int id = get_id(var_name);
long long int result = 0;
while (ss >> var_value)
{
if (var_value[0] == '$')
{
result += get_value(get_id(var_value.substr(1)));
}
else result += var_value.size();
result %= MOD;
}
value[id] = vector<long long int>(1, result);//直接赋值语句，表达式为一个固定的数
}
else if (opt == 2)
{
ss >> var_name;
int id = get_id(var_name);
vector<long long int> result;
long long int c = 0;
while (ss >> var_value)
{
if (var_value[0] == '$')
{
result.push_back(-get_id(var_value.substr(1)));//变量id以负数形式存储
}
else c += var_value.length();//字符串拼接后的长度满足交换律，可以直接对常量值进行压缩
}
result.push_back(c);
value[id] = result;
}
else if (opt == 3)
{
ss >> var_name;
int id = get_id(var_name);
cout << get_value(id) << endl;
}
}
return 0;
}