算法菜鸟前来水一篇题解，写的很烂轻喷

模板展开

题目描述略过

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

间接赋值语句中的常量值也是不变的，且字符串拼接后的长度满足交换律，因此没有必要存储所有常量值，可以把所有常量字符串的长度压缩为一个整数存储

#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;
}

看到这里了，就祝各位大佬CSP都能拿400+分吧