没进国赛就不能学国赛知识了?

没进国赛就不能学国赛知识了?

第一题:奇怪的捐赠

题目描述:

地产大佬先生临终的遗愿是拿出100万元给x社区的居民抽奖。

麻烦的是,他有个很奇怪的要求:

(1)100万元正好被分成若干份,不能有剩余。每份必须是7的若干次方元。比如1元、7元、49元。

(2)相同金额的分数不能超过5份。

(3)在满足上述条件的情况下,分成的份数越多越好。

请你帮忙计算一下,最多可以分成多少份?

# 两次遍历,从大到小,保证不会有剩余,然后遍历5次
a = 1000000
ans = 0
for i in range(7,-1,-1):
  for j in range(5):
    if (a - 7 ** i) >= 0:
      ans += 1
      a -= 7 ** i
    else:
      break
print(ans)

第二题:最长回文子串

题目描述:

给定一个字符串s,请你求出s的最长回文字符串。

输入描述:

输入一行,包含一个字符串s;

1 <= |s| <= 5 * 10^5,保证s只包含大写字母、小写字母和数字。

输出描述:

输出共1行,包含一个整数,表示答案。

import os
import sys

# 请在此输入您的代码
def longest_palindrome(s: str) -> int:
    def expand_around_center(left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

    max_length = 0
    for i in range(len(s)):
        # 以s[i]为中心的最长回文子串
        len1 = expand_around_center(i, i)
        # 以s[i]和s[i+1]为中心的最长回文子串
        len2 = expand_around_center(i, i + 1)
        # 更新最大长度
        max_length = max(max_length, len1, len2)

    return max_length

# 读取输入
s = input()
# 计算最长回文字符串的长度
result = longest_palindrome(s)
# 输出结果
print(result)

这个题我用的是中心扩展算法。


第三题:回文判定

题目描述:

给定一个长度为n的字符串s,请你判断字符串s是否回文。

输入描述:

输入仅一行包含一个字符串s。

1 <= |s| <= 10^6,保证s只包含大小写字母。

输出描述:

若字符串s为回文串,则输出Y,否则输出N。

import os
import sys

# 请在此输入您的代码
s = input()
if s[:] == s[::-1]:
  print("Y")
else:
  print("N")

ok,这次就做这几个题,明天继续!

07-26 15:40