QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#873931#3445. Numbers On a Treefernandes_queilaTL 86ms44564kbJava171.7kb2025-01-27 09:22:242025-01-27 09:22:27

Judging History

你现在查看的是最新测评结果

  • [2025-01-27 09:22:27]
  • 评测
  • 测评结果:TL
  • 用时:86ms
  • 内存:44564kb
  • [2025-01-27 09:22:24]
  • 提交

answer

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine().trim();
        String[] parts = line.split(" ");
        int height = Integer.parseInt(parts[0]);
        String road = parts.length > 1 ? parts[1] : "";
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.constructTree(height);
        int result = binaryTree.searchNode(height, road);
        System.out.println(result);
        scanner.close();
    }
}

class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) {
        this.value = value;
        this.left = this.right = null;
    }
}

class BinaryTree {
    private TreeNode root;

    public void constructTree(int height) {
        int totalNodes = (1 << (height + 1)) - 1;
        root = 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 searchNode(int height, String road) {
        int rootLabel = (1 << (height + 1)) - 1;

        if (road.isEmpty()) {
            return rootLabel;
        }

        int label = rootLabel;
        int local = 0;

        for (char move : road.toCharArray()) {
            if (Character.toLowerCase(move) == 'l') {
                local = 2 * local + 1;
            } else if (Character.toLowerCase(move) == 'r') {
                local = 2 * local + 2;
            }
        }

        label -= local;
        return label;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 83ms
memory: 44172kb

input:

3 LR

output:

11

result:

ok single line: '11'

Test #2:

score: 0
Accepted
time: 81ms
memory: 44448kb

input:

3 RRL

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 86ms
memory: 44564kb

input:

2

output:

7

result:

ok single line: '7'

Test #4:

score: 0
Accepted
time: 86ms
memory: 44508kb

input:

3 LRL

output:

6

result:

ok single line: '6'

Test #5:

score: -100
Time Limit Exceeded

input:

26 RRLLLLRRRL

output:


result: