3 综合练习精选

sy538: 受到祝福的平方中等

在小元的世界里，任何人出生后会被世界分配一个随机ID，如果在被切割后，即ID满足按照从左至右顺序分割，且分割出来的数字都是某一个正整数的平方，分割时可以包括前导0，那么他就被这个世界祝福，最后获得快乐的数量和质量都比不满足这样的的人多的多。

令ID为A，且A是一个正整数，取值范围为 $1 \leq A \leq 10^{9}$ ，问是否是一个被受到祝福的。

比如A=8194时，它是一个被受到祝福的ID，因为他可以被分割为 ${81, 9, 4} = {9^{2}, 3^{2}, 2^{2}}$ ；

比如A=1001时，它是一个被受到祝福的ID，因为他可以被分割为 ${1, 001} = {1^{2}, 1^{2}}$ ，或者 ${100, 1} = {10^{2}, 1^{2}}$ 。注意 ${1, 00, 1} = {1^{2}, 0^{2}, 1^{2}}$ 不是一个合法切割，因为分割出来的数字必须为正整数的平方；

比如A=36时，36已经是一个平方数了，所以它同样满足条件；

比如A=54，它不是一个被受到祝福的ID，因为他无法被切割为满足条件的集合。

输入描述

一个正整数A，无前导0。

其中 $1 \leq A \leq 10^{9}$

输出描述

如果是一个满足题意的数字则输出Yes，否则No。

样例1

输入

输出

Yes

样例2

输入

输出

No

样例3

输入

输出

No

dfs，先定义一个集合，存储所有小 $10^{9}$ 的平方数。然后将数据按照位数生成列表，便于提取数据。定义dfs函数，将数字列表从高位开始分割，对于每次分割，检查前面的数字是否为平方数，以及后面的数字是否可以继续分割为平方数，如果可以，返回True，不可以，返回False。

是一道典型的dfs问题，先初始化变量，然后再把所有平方数生成列表，再套用dfs模版（最终状态，即idx=len(each_number)），中间状态（巧妙之处就在于它很好表示了拆分后再将数字给组合起来），再写出dfs从哪里开始（0）。

python

# 李天笑，24物理学院
squares = set()
i = 1
while i ** 2 < 10 ** 9:
    squares.add(i ** 2)
    i += 1
def dfs(idx):
    if idx == len(digits):
        return True

    num = 0
    for i in range(idx, len(digits)):
        num = num * 10 + digits[i]
        if num in squares:
            if dfs(i + 1):
                return True
    return False

A = int(input())
digits = list(map(int, str(A)))
if dfs(0):
    print('Yes')
else:
    print('No')

python

# 李欣妤 24地空学院
def is_blessed_number(n_str):
    squares = [str(i * i) for i in range(1, 31623)]

    def can_split(s):
        if not s:
            return True
        for square in squares:
            if s.startswith(square) and can_split(s[len(square):]):
                return True
        return False

    return "Yes" if can_split(n_str) else "No"


num = input()
print(is_blessed_number(num))

是否存在一种二分分割，使得前一半是正平方数且后一半也是祝福数。

python

# 吕金浩 24物理学院
from functools import lru_cache
import math


@lru_cache(maxsize=None)
def is_blessed_number(n):
    if int(n) < 1:
        return False

    # 检查整个数字是否为平方数
    if math.isqrt(int(n)) ** 2 == int(n):
        return True

    for i in range(1, len(n)):
        left = n[:i]
        right = n[i:]

        if is_blessed_number(left) and is_blessed_number(right):
            return True

    return False


# 测试
print('Yes' if is_blessed_number(input()) else 'No')

思路：回溯上次找到的平方数，继续往后找新的平方数

python

# 曹以楷 24物理学院
from math import isqrt


def is_square(x):
    """判断一个数字是否是完全平方数"""
    x = int(x)
    return x != 0 and isqrt(x)**2 == x


def dfs(s, x, n):
    """深度优先搜索，判断是否可以将字符串分割成完全平方数"""
    if x >= n - 1:
        return True
    value = ""
    for j in range(x + 1, n):
        value += s[j]
        if is_square(value) and dfs(s, j, n):
            return True
    return False


# 主程序
s = input()
n = len(s)

# 执行DFS并输出结果
result = dfs(s, -1, n)
print("Yes" if result else "No")

思路：DFS，寻找分段点，有一种方案成立即返回True。体现Python优势的题目，字符串切片转整数

python

# 徐至晟，24光华
import math
a=input()
n=len(a)

def dfs(x):
    global a,n
    if x==n:
        return True
    for y in range(x+1,n+1):
        b=int(a[x:y])
        if b>0 and b==(int(math.sqrt(b))**2):
            if dfs(y):
                return True
    return False

if dfs(0):
    print('Yes')
else:
    print('No')

思路：dfs，用了is_integer()函数，要是把小于等于a的完全平方数都算出来会超时

python

# 吴道宁 24元培学院
from math import sqrt
a=int(input())
s=str(a)
def dfs(s):
    if sqrt(int(s)).is_integer() and sqrt(int(s))!=0:
        return True
    for i in range(1,len(s)):
        if sqrt(int(s[:i])).is_integer() and sqrt(int(s[:i]))!=0:
            if dfs(s[i:]):
                return True
    return False
if dfs(s):
    print('Yes')
else:
    print('No')

把合法的点位放到一个数组里，也许有点dp想法但不是dp。

python

# 高景行 24数学科学学院
a = input()
n = len(a)
valid = [-1]
def check(x):
    if not x: return False
    tmp = int(x ** 0.5)
    return tmp * tmp == x
for i in range(n):
    for t in valid:
        if check(int(a[t + 1:i + 1])):
            valid.append(i)
            break
print("Yes" if n - 1 in valid else "No")

python

import math

def is_square(n):
    """判断一个数字是否为完全平方数"""
    if n == 0:
        return False  # 0不是有效的平方数
    root = int(math.sqrt(n))
    return root * root == n

def can_split_to_squares(s, start, memo):
    """递归函数，判断是否可以将字符串s从start位置开始切割成平方数"""
    if start == len(s):
        return True
    if start in memo:
        return memo[start]

    for end in range(start + 1, len(s) + 1):
        part = s[start:end]
        # 剪枝：避免数字超出合理范围
        if len(part) > 10 or int(part) > 10**9:
            break
        if is_square(int(part)) and can_split_to_squares(s, end, memo):
            memo[start] = True
            return True

    memo[start] = False
    return False

def is_blessed_number(number):
    """主函数，判断一个数字是否满足条件"""
    s = str(number)
    memo = {}
    return can_split_to_squares(s, 0, memo)

# 输入处理
number = input().strip()
if is_blessed_number(number):
    print("Yes")
else:
    print("No")

dp[i] is True if the substring num[0:i] can be split into perfect squares.

python

import math

def is_square(n: int) -> bool:
    if n == 0:
        return False
    root = int(math.isqrt(n))
    return root * root == n

def is_blessed_number(num: str) -> str:
    n = len(num)
    dp = [False] * (n + 1)
    dp[0] = True  # Base case: empty string is considered valid

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j]  and is_square(int(num[j:i])):
                dp[i] = True
                break

    return "Yes" if dp[n] else "No"

# Example usage
if __name__ == "__main__":
    #print(is_blessed_number("8194"))  # Output: Yes
    #print(is_blessed_number("100000"))     # Output: No
    print(is_blessed_number(input()))

python

# 曾孜博 24工学院
import math


def luck(a, r):
    if r[-1] == len(a):
        ans.append(r)
        return
    i = r[-1]
    for j in range(i, len(a)):
        k = ''.join(a[i:j + 1])
        t = math.sqrt(int(k))
        if t.is_integer() and t > 0:
            r.append(j + 1)
            luck(a, r)
            r.pop()


a = list(input())
ans = []
luck(a, [0])
if len(ans) > 0:
    print("Yes")
else:
    print("No")

思路：暴力枚举

python

# 陈一匡 24物理学院
square_nums=set()
for i in range(1,31624):
    square_nums.add(i*i)
def f(a):
    if int(a) in square_nums:
        return 'Yes'
    for i in range(len(a)):
        if int(a[:i+1]) in square_nums and f(a[i+1:])=='Yes':
            return 'Yes'
    return 'No'

a=input()
print(f(a))

思路：recursion

python

# 卢殷文  24物院
from math import sqrt
from functools import lru_cache

def is_power(s:str):
    n=int(s)
    if n==0:
        return False
    elif int(sqrt(n))**2 == n:
        return True
    else:
        return False

@lru_cache(maxsize=256)
def blessed(s:str):
    if is_power(s):
        return True
    for i in range(1,len(s)):
        if blessed(s[:i]) and blessed(s[i:]):
            return True
    return False

a=input()
if blessed(a):
    print("Yes")
else:
    print("No")

3 综合练习精选 ​

sy538: 受到祝福的平方 中等 ​

3 综合练习精选

sy538: 受到祝福的平方中等