#CSP202503C. 模板展开

模板展开 - 题目详情 - 曙梦 OJ题目一共就三种操作操作一是直接赋值 这个很好理解操作二是间接赋值 此时相当于保存了一个字符串拼接公式 里面的字符串可能会随着后续赋值而改变操作三是输出长度这题根据子任务 很容易拿到40%的分数若想将分数拿满就需要优化过程#include bits/stdc.h using namespace std; using ll long long; const int MOD 1000000007; unordered_mapstring, ll len; unordered_mapstring, vectorstring expr; unordered_mapstring, ll mem; unordered_mapstring, int vis; int tim 0; // 返回变量 var 当前对应字符串的长度 ll dfs(string var) { // 不存在动态表达式说明是直接值 if (expr.count(var) 0) { return len[var]; } // 本次计算中已经计算过 if (vis[var] tim) { return mem[var]; } vis[var] tim; ll ans 0; for (int i 0; i (int)expr[var].size(); i) { string s expr[var][i]; if (s[0] $) { string nextVar s.substr(1); ans (ans dfs(nextVar)) % MOD; } else { ans (ans s.size()) % MOD; } } mem[var] ans; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; while (n--) { int op; string var; cin op var; if (op 1) { string line; getline(cin, line); stringstream ss(line); vectorstring tokens; string s; while (ss s) { tokens.push_back(s); } // 开始一次新的计算 tim; ll ans 0; for (int i 0; i (int)tokens.size(); i) { string token tokens[i]; if (token[0] $) { string nextVar token.substr(1); ans (ans dfs(nextVar)) % MOD; } else { ans (ans token.size()) % MOD; } } // 操作1是直接赋值 expr.erase(var); len[var] ans; } else if (op 2) { string line; getline(cin, line); stringstream ss(line); vectorstring tokens; string s; while (ss s) { tokens.push_back(s); } expr[var] tokens; } else if (op 3) { tim; cout dfs(var) \n; } } return 0; }unordered_mapstring, ll len; unordered_mapstring, vectorstring expr; unordered_mapstring, ll mem; unordered_mapstring, int vis; int tim 0;保存直接赋值字符串长度保存操作二的动态表达式保存本次计算得到的临时答案 比如动态表达式中会重复出现一个字符串 如果记忆化过 就可以省略dfs递归过程记录缓存属于哪一次计算当前是第几次求值tim情况立即计算右边表达式计算变量当前长度并输出