有一棵由 n 个结点组成的计算树。 结点编号为 1 到 n，1 号结点是根。 第一行给出 n 和输入值的个数 m，接下来 n 行从 1 号开始依次每行给出一个结点。 结点是以下六种之一。 num v 的值是整数 v。 in k 的值是询问的第 k 个输入值。 add a b 的值是（a 号结点的值）+（b 号结点的值），sub a b 的值是（a 号结点的值）−（b 号结点的值）。 div a b 的值是（a 号结点的值）÷（b 号结点的值）的商。 商的小数部分向 0 舍去（−7 ÷ 2 为 −3）。 若 b 号结点的值为 0，则这个结点无法计算。 if a b c d 先求出 a 号和 b 号结点的值。 若（a 号结点的值）<（b 号结点的值），这个结点的值就是 c 号结点的值，否则是 d 号结点的值。 没有选中的那一侧结点不计算。 计算某个结点时需要的结点中只要有一个无法计算，这个结点也无法计算。 接下来一行给出询问数 q，再接下来 q 行，每个询问给出 m 个用空格隔开的输入值。 用一个返回结点值的递归函数来解。 “无法计算”由这个函数用另外区分的值返回，或者按语言习惯用异常告知。 对每个询问，在一行中输出根的值。 若根无法计算，输出 "错误"。
输入
1 ≤ n ≤ 999，1 ≤ m ≤ 10，1 ≤ q ≤ 300。 在所有结点的 a、b、c、d 中，2 到 n 的每个编号恰好出现一次，1 不出现。 把这些结点称为子结点，子结点的编号大于父结点的编号。 从根到叶的结点数不超过 500。 1 ≤ k ≤ m。 v 和输入值是 -1,000,000 到 1,000,000 的整数。 凡是能计算的结点（包括没被选中那一侧的结点），其值的绝对值都不超过 1,000,000,000
输出
q 行
样例 1 · stdin
9 1
if 2 3 4 7
in 1
num 0
div 5 6
num 100
in 1
sub 8 9
num 0
in 1
4
5
-7
0
-3
stdout
-5
-14
0
-33
样例 2 · stdin
7 3
add 2 3
in 1
div 4 5
num -7
sub 6 7
in 2
in 3
4
1 3 1
0 5 5
-1 9 2
4 2 4
stdout
-2
错误
-2
7
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
返回“没有值”的方式因语言而异：Python None，JS・TS null（TS 写成 number | null，检查 === null 之后才收窄成 number），C# int?，C++ std::optional<int>，Craykon 空。 C 返回是否成功，值通过指针 int *out 放出去。 Java 用异常来解：int 除以 0 时 / 会抛出 ArithmeticException，异常会自己经过各层调用者一直传到最上面的 catch。 陷阱 ① 挑一个特殊值：用 -1 或 0 表示“无法计算”，会和正确答案 -1、0 混在一起。 ② 连没选中的一侧也计算：先算好 c = value(...)、d = value(...) 再选，没选中一侧的除以 0 会导致输出 "error"。 ③ 递归里漏写 return：Python 会悄悄返回 None，JS 返回 undefined。 C 的值不确定，Java・C# 会编译报错。 ④ 除以 0：Python ZeroDivisionError，Java ArithmeticException，C# DivideByZeroException，Craykon 数学.商 会停下，C・C++ 是未定义行为。 JS・TS 不会停，而是给出 Infinity・NaN。 ⑤ 商：Python 的 // 向下取整，-7 // 2 是 -4。 Craykon 的 / 会除出小数，要用 数学.商。 ⑥ C# 的 int? 在 + - / 中会自动传递 null，但 a < b 只要一边是 null 就直接是 false，不检查的话得到的是 d 的值而不是错误。 Craykon 用 空 计算或比较大小时会停下。
Pythonmain.py · 43 行
import sysdata = sys.stdin.read().split("\n")n, m = map(int, data[0].split())nodes = [None] + [data[i].split() for i in range(1, n + 1)]q = int(data[n + 1])def div(a, b): # 0 쪽으로 버리는 몫. Python의 //는 아래로 내려서 음수에서 다르다 qt = abs(a) // abs(b) return qt if (a < 0) == (b < 0) else -qtdef value(i, x): """i번 마디의 값을 돌려준다. 계산할 수 없으면 None을 돌려준다.""" op, *args = nodes[i] if op == "num": return int(args[0]) if op == "in": return x[int(args[0]) - 1] a = value(int(args[0]), x) if a is None: return None # 실패는 곧바로 위로 돌려보낸다 b = value(int(args[1]), x) if b is None: return None if op == "add": return a + b if op == "sub": return a - b if op == "div": return None if b == 0 else div(a, b) # if: 고른 쪽 하나만 계산한다 return value(int(args[2]) if a < b else int(args[3]), x)out = []for line in data[n + 2:n + 2 + q]: x = list(map(int, line.split())) v = value(1, x) out.append("错误" if v is None else str(v)) # 0이나 -1도 올바른 값이라 None으로 가른다print("\n".join(out))
JavaScriptmain.js · 28 行
const data = require("fs").readFileSync(0, "utf8").split("\n");const [n] = data[0].split(" ").map(Number);const nodes = [null];for (let i = 1; i <= n; i++) nodes.push(data[i].trim().split(" "));const q = Number(data[n + 1]);// i번 마디의 값을 돌려준다. 계산할 수 없으면 null을 돌려준다function value(i, x) { const [op, ...args] = nodes[i]; const k = args.map(Number); if (op === "num") return k[0]; if (op === "in") return x[k[0] - 1]; const a = value(k[0], x); if (a === null) return null; // 실패는 곧바로 위로 돌려보낸다 const b = value(k[1], x); if (b === null) return null; if (op === "add") return a + b; if (op === "sub") return a - b; if (op === "div") return b === 0 ? null : Math.trunc(a / b); // JS는 0으로 나눠도 멈추지 않고 Infinity를 준다 return value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다}const out = [];for (const line of data.slice(n + 2, n + 2 + q)) { const v = value(1, line.trim().split(" ").map(Number)); out.push(v === null ? "错误" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
TypeScriptmain.ts · 30 行
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").split("\n");const [n] = data[0].split(" ").map(Number);const nodes: string[][] = [[]];for (let i = 1; i <= n; i++) nodes.push(data[i].trim().split(" "));const q = Number(data[n + 1]);// i번 마디의 값을 돌려준다. 계산할 수 없으면 null을 돌려준다function value(i: number, x: number[]): number | null { const [op, ...args] = nodes[i]; const k = args.map(Number); if (op === "num") return k[0]; if (op === "in") return x[k[0] - 1]; const a = value(k[0], x); if (a === null) return null; // 실패는 곧바로 위로 돌려보낸다(검사해야 a가 number로 좁혀진다) const b = value(k[1], x); if (b === null) return null; if (op === "add") return a + b; if (op === "sub") return a - b; if (op === "div") return b === 0 ? null : Math.trunc(a / b); // JS는 0으로 나눠도 멈추지 않고 Infinity를 준다 return value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다}const out: string[] = [];for (const line of data.slice(n + 2, n + 2 + q)) { const v = value(1, line.trim().split(" ").map(Number)); out.push(v === null ? "错误" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
JavaMain.java · 50 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static String[] op; static int[][] arg; // i번 마디의 값을 돌려준다. 0으로 나누면 Java의 / 가 ArithmeticException을 던지고, // 그 예외가 부른 쪽들을 거쳐 맨 위까지 올라간다 static int value(int i, int[] x) { int[] k = arg[i]; switch (op[i]) { case "num": return k[0]; case "in": return x[k[0] - 1]; case "add": return value(k[0], x) + value(k[1], x); case "sub": return value(k[0], x) - value(k[1], x); case "div": return value(k[0], x) / value(k[1], x); // int의 / 는 0 쪽으로 버린다 default: // if: 고른 쪽 하나만 계산한다 return value(k[0], x) < value(k[1], x) ? value(k[2], x) : value(k[3], x); } } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]); op = new String[n + 1]; arg = new int[n + 1][]; for (int i = 1; i <= n; i++) { String[] p = in.readLine().trim().split(" "); op[i] = p[0]; arg[i] = new int[p.length - 1]; for (int j = 1; j < p.length; j++) arg[i][j - 1] = Integer.parseInt(p[j]); } int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { String[] p = in.readLine().trim().split(" "); int[] x = new int[p.length]; for (int j = 0; j < p.length; j++) x[j] = Integer.parseInt(p[j]); try { out.append(value(1, x)).append('\n'); } catch (ArithmeticException e) { out.append("错误\n"); } } System.out.print(out); }}
C#Main.cs · 50 行
using System;using System.Linq;using System.Text;class Program{ static string[] op = Array.Empty<string>(); static int[][] arg = Array.Empty<int[]>(); // i번 마디의 값을 돌려준다. 계산할 수 없으면 null(int?)을 돌려준다 static int? Value(int i, int[] x) { int[] k = arg[i]; if (op[i] == "num") return k[0]; if (op[i] == "in") return x[k[0] - 1]; int? a = Value(k[0], x); if (a is null) return null; // 실패는 곧바로 위로 돌려보낸다 int? b = Value(k[1], x); if (b is null) return null; switch (op[i]) { case "add": return a + b; case "sub": return a - b; case "div": return b == 0 ? null : a / b; // int의 / 는 0 쪽으로 버린다 default: return Value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다 } } static void Main() { int n = int.Parse(Console.ReadLine().Split(' ')[0]); op = new string[n + 1]; arg = new int[n + 1][]; for (int i = 1; i <= n; i++) { string[] p = Console.ReadLine().Trim().Split(' '); op[i] = p[0]; arg[i] = p.Skip(1).Select(int.Parse).ToArray(); } int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int t = 0; t < q; t++) { int[] x = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); int? v = Value(1, x); sb.Append(v is null ? "错误" : v.ToString()).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 55 行
#include <iostream>#include <optional>#include <string>#include <vector>struct Node { std::string op; std::vector<int> k;};std::vector<Node> nodes;std::vector<int> x;// i번 마디의 값을 돌려준다. 계산할 수 없으면 값이 없는 optional(std::nullopt)std::optional<int> value(int i) { const Node &nd = nodes[i]; if (nd.op == "num") return nd.k[0]; if (nd.op == "in") return x[nd.k[0] - 1]; auto a = value(nd.k[0]); if (!a) return std::nullopt; // 실패는 곧바로 위로 돌려보낸다 auto b = value(nd.k[1]); if (!b) return std::nullopt; if (nd.op == "add") return *a + *b; if (nd.op == "sub") return *a - *b; if (nd.op == "div") { if (*b == 0) return std::nullopt; return *a / *b; // 0 쪽으로 버린다 } return value(*a < *b ? nd.k[2] : nd.k[3]); // if: 고른 쪽 하나만 계산한다}int main() { std::ios::sync_with_stdio(false); int n, m, q; std::cin >> n >> m; nodes.resize(n + 1); for (int i = 1; i <= n; i++) { Node &nd = nodes[i]; std::cin >> nd.op; int cnt = nd.op == "if" ? 4 : (nd.op == "num" || nd.op == "in") ? 1 : 2; nd.k.resize(cnt); for (int &v : nd.k) std::cin >> v; } std::cin >> q; x.resize(m); std::string out; for (int t = 0; t < q; t++) { for (int &v : x) std::cin >> v; auto v = value(1); out += v ? std::to_string(*v) : "错误"; out += '\n'; } std::cout << out; return 0;}
Cmain.c · 45 行
#include <stdio.h>#include <string.h>static char op[1001]; /* n a s d i: num add sub div if, 'x'는 in */static int arg[1001][4];static int x[10];/* i번 마디의 값을 *out에 넣고 1을 돌려준다. 계산할 수 없으면 0을 돌려준다. 값과 성공 여부를 따로 돌려주니 -1이나 0도 올바른 값으로 쓸 수 있다 */static int value(int i, int *out) { int *k = arg[i], a, b; if (op[i] == 'n') { *out = k[0]; return 1; } if (op[i] == 'x') { *out = x[k[0] - 1]; return 1; } if (!value(k[0], &a) || !value(k[1], &b)) return 0; /* 실패는 곧바로 위로 */ switch (op[i]) { case 'a': *out = a + b; return 1; case 's': *out = a - b; return 1; case 'd': if (b == 0) return 0; /* C에서 0으로 나누면 정의되지 않은 동작 */ *out = a / b; /* C99부터 0 쪽으로 버린다 */ return 1; default: /* if: 고른 쪽 하나만 계산한다 */ return value(a < b ? k[2] : k[3], out); }}int main(void) { int n, m, q; char name[8]; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%7s", name); int cnt = strcmp(name, "if") == 0 ? 4 : strcmp(name, "num") == 0 || strcmp(name, "in") == 0 ? 1 : 2; op[i] = strcmp(name, "in") == 0 ? 'x' : strcmp(name, "if") == 0 ? 'i' : name[0]; for (int j = 0; j < cnt; j++) scanf("%d", &arg[i][j]); } scanf("%d", &q); for (int t = 0; t < q; t++) { for (int j = 0; j < m; j++) scanf("%d", &x[j]); int v; if (value(1, &v)) printf("%d\n", v); else puts("错误"); } return 0;}
Craykonmain.cray · 68 行
첫줄 = 控制台.读数字();n = 첫줄[0];마디들 = [空];循环 (i = 1; i <= n; i++){ 마디들.添加(控制台.读行().去空白().分割(" "));}q = 控制台.读行().转数字();x = [];// 번호 마디의 값을 돌려준다. 계산할 수 없으면 빈값을 돌려준다// 함수 안에서 처음 넣은 이름(마디, 가, 다)은 부를 때마다 따로 생겨서 재귀해도 섞이지 않는다값(번호){ 마디 = 마디들[번호]; 如果 (마디[0] == "num") { 返回 마디[1].转数字(); } 如果 (마디[0] == "in") { 返回 x[마디[1].转数字() - 1]; } 가 = 값(마디[1].转数字()); 如果 (가 == 空) { 返回 空; // 빈값으로 계산하면 멈추니, 실패는 곧바로 위로 돌려보낸다 } 다 = 값(마디[2].转数字()); 如果 (다 == 空) { 返回 空; } 选择 (마디[0]) { 情况 "add": 返回 가 + 다; 情况 "sub": 返回 가 - 다; 情况 "div": 如果 (다 == 0) { 返回 空; } 返回 数学.商(가, 다); // 0 쪽으로 버리는 몫 默认: // if: 고른 쪽 하나만 계산한다 如果 (가 < 다) { 返回 값(마디[3].转数字()); } 返回 값(마디[4].转数字()); }}循环 (t = 0; t < q; t++){ x = 控制台.读数字(); v = 값(1); 如果 (v == 空) { 控制台.输出("错误"); } 否则 { 控制台.输出(v); }}