1 条题解
-
0
题意分析
本题需要我们实现一个评测程序,验证给定的访问频率是否使其成为唯一最优二叉搜索树。 因此我们需要:
- 解析并构建输入的 BST;
- 检查程序员输出是否合法:行数、token 数、整数格式、范围;
- 计算该 BST 在给定频率下的期望访问代价;
- 动态规划枚举所有 BST 的最小期望代价和唯一性;
解题思路
- 输入处理:读取原始树结构与程序员输出行,去除空格/制表符并切分 token。
- 合法性校验:输出需正好一行,含 $N$ 个非负整数,无前导零,$\le10^{15}$。
- 计算代价:DFS/BFS 求节点深度 $dep_i$,累加 $\sum f_i\times dep_i$。
- DP 枚举:设 $dp[i][j]$ 为标签区间 $[i,j]$ 的最小代价,
unique[i][j]
表示是否唯一,使用前缀和 $S[k]=\sum f_t$ 加速区间权重计算。 - 判断结果:若 $dp[1][N]$ 等于输入树代价且唯一,则
Accepted
,否则Wrong
。
解题代码
#include <cstdio> #include <cstring> #include <string> #include <vector> #include <algorithm> #include <cctype> using namespace std; typedef unsigned long long ull; const ull INF = (ull)-1; string trim_line(const string &s) { // remove spaces and tabs string r; for (size_t i = 0; i < s.size(); ++i) { char c = s[i]; if (c != ' ' && c != '\t') r.push_back(c); } return r; } int main() { char buf[2048]; vector<string> in_lines, out_lines; bool in_input = false, in_output = false; while (fgets(buf, sizeof(buf), stdin)) { string line(buf); if (line.find("#End#") != string::npos) break; if (line.find("#Start Input#") != string::npos) { in_input = true; in_lines.clear(); continue; } if (line.find("#End Input#") != string::npos) { in_input = false; continue; } if (line.find("#Start Programmer's Output#") != string::npos) { in_output = true; out_lines.clear(); continue; } if (line.find("#End Programmer's Output#") != string::npos) { in_output = false; // process one test case // parse input int idx = 0; int N; sscanf(in_lines[idx++].c_str(), "%d", &N); vector<int> left(N+1), right(N+1), parent(N+1, -1); for (int i = 1; i <= N; i++) { int l, r; sscanf(in_lines[idx++].c_str(), "%d %d", &l, &r); left[i] = l; right[i] = r; if (l != -1) parent[l] = i; if (r != -1) parent[r] = i; } // check output lines count if ((int)out_lines.size() != 1) { puts("Wrong"); } else { // tokenize vector<string> toks; { string s = out_lines[0]; int i = 0, L = s.size(); while (i < L) { while (i < L && (s[i] == ' ' || s[i] == '\t')) i++; if (i >= L) break; int j = i; while (j < L && s[j] != ' ' && s[j] != '\t' && s[j] != '\r' && s[j] != '\n') j++; toks.push_back(s.substr(i, j - i)); i = j; } } if ((int)toks.size() != N) { puts("Wrong"); } else { vector<ull> f(N+2, 0); bool ok = true; for (int i = 1; i <= N; i++) { const string &t = toks[i-1]; if (t.empty() || (t.size() > 1 && t[0] == '0')) { ok = false; break; } ull v = 0; for (size_t j = 0; j < t.size(); ++j) { char c = t[j]; if (!isdigit(c)) { ok = false; break; } v = v * 10 + (c - '0'); } if (!ok || v > (ull)1000000000000000ULL) { ok = false; break; } f[i] = v; } if (!ok) { puts("Wrong"); } else { // find root int root = 1; for (int i = 1; i <= N; i++) if (parent[i] == -1) { root = i; break; } // compute depth vector<int> depth(N+1, 0); vector<int> stack; stack.push_back(root); depth[root] = 1; for (size_t i = 0; i < stack.size(); i++) { int u = stack[i]; if (left[u] != -1) { depth[left[u]] = depth[u] + 1; stack.push_back(left[u]); } if (right[u] != -1) { depth[right[u]] = depth[u] + 1; stack.push_back(right[u]); } } // cost of given tree ull cost0 = 0; for (int i = 1; i <= N; i++) cost0 += f[i] * (ull)depth[i]; // prefix sums vector<ull> ps(N+2, 0); for (int i = 1; i <= N; i++) ps[i] = ps[i-1] + f[i]; // dp static ull dp_cost[52][52]; static bool dp_unique[52][52]; for (int i = 1; i <= N+1; i++) { dp_cost[i][i-1] = 0; dp_unique[i][i-1] = true; } for (int len = 1; len <= N; len++) for (int i = 1; i + len - 1 <= N; i++) { int j = i + len - 1; ull best = INF; bool unique = false; int ways = 0; ull wsum = ps[j] - ps[i-1]; for (int r = i; r <= j; r++) { ull c = dp_cost[i][r-1] + dp_cost[r+1][j] + wsum; if (c < best) { best = c; ways = 1; unique = dp_unique[i][r-1] && dp_unique[r+1][j]; } else if (c == best) { ways++; unique = false; } } dp_cost[i][j] = best; dp_unique[i][j] = unique && (ways == 1); } if (dp_cost[1][N] == cost0 && dp_unique[1][N]) puts("Accepted"); else puts("Wrong"); } } } continue; } if (in_input) { in_lines.push_back(line); } else if (in_output) { // trim trailing newline if (!line.empty()) { size_t last_pos = line.size() - 1; if (line[last_pos] == '\n' || line[last_pos] == '\r') { line.erase(last_pos); } } out_lines.push_back(line); } } return 0; }
- 1
信息
- ID
- 1727
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 10
- 已通过
- 1
- 上传者