本题的题目描述在赛时完全错误,且数据强度极低,输出实数 log2(n+1)\log_2(n + 1) 可以通过该题。

赛时题面:

你被要求扮演一个红石信号,手里握着一个初始值为 00 的变量 xx(红石信号强度),从 11 号结点出发:

  1. 根据当前所在的结点的元件改变 xx 值,具体规则见下表。
  2. 如果 x=0x = 0,你结束扮演。
  3. 如果你位于二叉树的某个叶子结点,你结束扮演。
  4. 你得到 11 分。
  5. 你前往当前结点的某个儿子,然后回到第 11 步重新执行本流程,直至扮演结束。

正确题面:

你被要求扮演一个红石信号,手里握着一个初始值为 1515 的变量 xx(红石信号强度),从 11 号结点出发:

  1. 如果 x=0x = 0ai=0a_i = 0,你结束扮演。
  2. 你得到 11 分。
  3. 根据当前所在的结点的元件改变 xx 值,具体规则见下表。
  4. 如果你位于二叉树的某个叶子结点,你结束扮演。
  5. 你前往当前结点的某个儿子,然后回到第 11 步重新执行本流程,直至扮演结束。

以增加的第 4 个测试点 #29 为例:

3
1 0 0
Record ID Author Output
#5207 0
#5217
#5402 2
#5085 1

我们决定:

  1. 为本题所有通过的选手减免 60 分钟罚时。
  2. 自 4 月 10 日 0:00 起,30 天内不再受理 RZOI 的比赛举办申请。
  3. 自 4 月 10 日 0:00 起,封禁相关账号 3 天。

1 条评论

  • @ 2026-4-9 19:27:19

    为什么 std 是 ai

    #include <bits/stdc++.h>
    using namespace std;
    
    struct NodeState {
        int index;
        int length;
        int signal;
    };
    
    int cs(int type, int signal) {
        if (type == 0) return 0;
        if (type == 2) return 15;
        if (type == 3) return signal - 1;
        if (type >= 4 && type <= 7) {
            int boost = 0;
            if (type == 4) boost = 0;
            else if (type == 5) boost = 1;
            else if (type == 6) boost = 2;
            else if (type == 7) boost = 4;
            return (signal + boost) - 1;
        }
        return signal;
    }
    
    int dfs(const vector<int>& tree) {
        if (tree.empty() || tree[0] != 1) {
            return 0;
        }
        int max_l = 0;
        stack<NodeState> stk;
        stk.push({0, 0, 15});
        while (!stk.empty()) {
            NodeState c = stk.top();
            stk.pop();
            if (c.index >= tree.size() || c.signal <= 0 || tree[c.index] == 0) {
                continue;
            }
            int new_s = cs(tree[c.index], c.signal);
            int new_l = c.length + 1;
            if (new_l > max_l) {
                max_l = new_l;
            }
            if (new_s > 0) {
                stk.push({2 * c.index + 2, new_l, new_s});
                stk.push({2 * c.index + 1, new_l, new_s});
            }
        }
        return max_l;
    }
    
    int main() {
        freopen("traversal.in", "r", stdin);
        freopen("traversal.out", "w", stdout);
        int n;
        cin >> n;
        vector<int> tree(n);
        for (int i = 0; i < n; i++) {
            cin >> tree[i];
        }
        int result = dfs(tree);
        cout << result << endl;
        return 0;
    }
    
    
  • 1

信息

ID
237
时间
ms
内存
MiB
难度
1
标签
递交数
13
已通过
7
上传者