1 条题解

  • 0
    @ 2025-5-4 14:14:48

    题意分析

    本题需要我们实现一个评测程序,验证给定的访问频率是否使其成为唯一最优二叉搜索树。 因此我们需要:

    1. 解析并构建输入的 BST;
    2. 检查程序员输出是否合法:行数、token 数、整数格式、范围;
    3. 计算该 BST 在给定频率下的期望访问代价;
    4. 动态规划枚举所有 BST 的最小期望代价和唯一性;

    解题思路

    1. 输入处理:读取原始树结构与程序员输出行,去除空格/制表符并切分 token。
    2. 合法性校验:输出需正好一行,含 $N$ 个非负整数,无前导零,$\le10^{15}$。
    3. 计算代价:DFS/BFS 求节点深度 $dep_i$,累加 $\sum f_i\times dep_i$。
    4. DP 枚举:设 $dp[i][j]$ 为标签区间 $[i,j]$ 的最小代价,unique[i][j] 表示是否唯一,使用前缀和 $S[k]=\sum f_t$ 加速区间权重计算。
    5. 判断结果:若 $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
    上传者