QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#873919 | #3445. Numbers On a Tree | fernandes_queila | TL | 82ms | 44504kb | Java17 | 1.5kb | 2025-01-27 09:01:48 | 2025-01-27 09:01:50 |
Judging History
answer
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine().trim();
String[] parts = input.split(" ");
int height = Integer.parseInt(parts[0]);
String path = parts.length > 1 ? parts[1] : "";
BalancedTree balancedTree = new BalancedTree(height);
int result = balancedTree.findNodeLabel(height, path);
System.out.println(result);
scanner.close();
}
}
class BalancedTree {
private TreeNode root;
public BalancedTree(int height) {
root = constructTree(height);
}
private TreeNode constructTree(int height) {
int totalNodes = (1 << (height + 1)) - 1;
return buildTree(1, totalNodes);
}
private TreeNode buildTree(int start, int end) {
if (start > end) return null;
int mid = (start + end) / 2;
TreeNode node = new TreeNode(mid);
node.left = buildTree(start, mid - 1);
node.right = buildTree(mid + 1, end);
return node;
}
public int findNodeLabel(int height, String path) {
int cur = 1;
for (char c : path.toCharArray()) {
cur = cur * 2 + (c == 'R' ? 1 : 0);
}
int totalNodes = (1 << (height + 1)) - 1;
return totalNodes - cur + 1;
}
}
class TreeNode {
int value;
TreeNode left, right;
TreeNode(int value) {
this.value = value;
this.left = this.right = null;
}
}
详细
Test #1:
score: 100
Accepted
time: 82ms
memory: 44192kb
input:
3 LR
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 78ms
memory: 44504kb
input:
3 RRL
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 77ms
memory: 44092kb
input:
2
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 73ms
memory: 44272kb
input:
3 LRL
output:
6
result:
ok single line: '6'
Test #5:
score: -100
Time Limit Exceeded
input:
26 RRLLLLRRRL