- [Sleeping Cup #10] Signal Traversal
本题增加 10 组 hack 数据 & 关于本题的说明
- @ 2026-4-9 12:45:50
本题的题目描述在赛时完全错误,且数据强度极低,输出实数 可以通过该题。
赛时题面:
你被要求扮演一个红石信号,手里握着一个初始值为 的变量 (红石信号强度),从 号结点出发:
- 根据当前所在的结点的元件改变 值,具体规则见下表。
- 如果 ,你结束扮演。
- 如果你位于二叉树的某个叶子结点,你结束扮演。
- 你得到 分。
- 你前往当前结点的某个儿子,然后回到第 步重新执行本流程,直至扮演结束。
正确题面:
你被要求扮演一个红石信号,手里握着一个初始值为 的变量 (红石信号强度),从 号结点出发:
- 如果 或 ,你结束扮演。
- 你得到 分。
- 根据当前所在的结点的元件改变 值,具体规则见下表。
- 如果你位于二叉树的某个叶子结点,你结束扮演。
- 你前往当前结点的某个儿子,然后回到第 步重新执行本流程,直至扮演结束。
以增加的第 4 个测试点 #29 为例:
3
1 0 0
| Record ID | Author | Output |
|---|---|---|
| #5207 | 0 | |
| #5217 | ||
| #5402 | 2 | |
| #5085 | 1 |
我们决定:
1 条评论
-
zhangruixiang LV 4 @ 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
- 上传者