[日本央行 27231，蟒蛇] 我为何期待 2023 年

问题链接

boj 27231

分类

暴力算法, 逆向追踪

描述

很高兴看到我能够解决以前无法解决的问题，所以我觉得我进步了。

就拿这道题来说，最后一次尝试是在五个月前提交给比赛的，但在此期间我已经把解题思路写了好几遍。

之所以会有多次尝试，是因为只缺少一个条件，但我还是不清楚为什么缺少这个条件会超时。整理博客是最棒的！

让我来介绍一下解决问题的方法

对 *+ 符号之间的坐标进行位屏蔽，检查是否为整数

• 在不允许重复的列表中设置或排序

• 计数直到最初输入的数字（因为无论如何切分，都不会大于该数字），方格尺寸不断增大

这里我们遇到了一个问题。

对于一个由 0 和 1 组成的数字，我们应该输出 Hello, BOJ 2023!，因为如果我们把它分割成一个数字，那么无论平方多少次，数值都不会改变，但我只是排除了 1 的情况。

为了检查这一部分，我通过检查是否有大于 2 的单个数字来处理边缘情况，如果没有大于 2 的项，则打印 Hello, BOJ 2023!，这就是正确答案。

求解代码

# 2023년이 기대되는 이유

import sys

input = sys.stdin.readline

def pow_target(target_num: int, exponent: int) -> int:

    result = 0

    now_number = target_num

    while now_number:
        result += pow((now_number % 10), exponent)
        now_number //= 10

    return result

testcase = int(input())
result_dict = dict()
output = []

for _ in range(testcase):

    target_number = input().rstrip('\n')

    if result_dict.get(target_number) is not None:
        output.append(result_dict[target_number])

    else:

        is_under_limit = True

        for each_element in list(target_number):
            if int(each_element) > 1:
                is_under_limit = False
                break

        if is_under_limit:
            result_dict[target_number] = 'Hello, BOJ 2023!'
            output.append('Hello, BOJ 2023!')
            continue

        length = len(target_number)

        check_list = []
        check_list.append(int(target_number))

        for i in range(1, 1 << length):

            calc_result = 0

            now_start = 0
            now_end = 0

            for j in range(length):

                if i & (1 << j):
                    now_end = j
                    if now_end:
                        calc_result += int(target_number[now_start : now_end])
                    now_start = now_end
                    
            calc_result += int(target_number[now_start : length + 1])

            if calc_result not in check_list:
                check_list.append(calc_result)

        else:
            result = 0

            check_amount = len(check_list)
            check_list.sort()

            max_value = check_list[-1]
            pointer = 0
            counter = 1

            while pointer < check_amount:
                now_result = pow_target(int(target_number), counter)

                # 종료 조건 1
                if now_result > max_value:
                    break

                while pointer < check_amount and now_result > check_list[pointer]:
                    pointer += 1

                # 종료 조건 2
                if pointer >= check_amount:
                    break

                if now_result == check_list[pointer]:
                    result += 1

                counter += 1

            result_dict[target_number] = result
            output.append(result)

for result in output:
    print(result)