AK杯 Python 简要题解

AK杯 Python 题解

由于 Daniel 大佬发的题解 华南师范大学软件学院 2020 AK 杯程序设计竞赛题解 - #6 由 Katalyst (分析与思路)已经非常详细,所以下面我给出的题解比较简陋。

A

Python 不需要头和 main 函数,一行代码输出即可。

print('yiming shixiong nvzhuang')

B

此题仍然不需要输入,直接根据题意输出答案即可。ps: Python 中三引号代表的是多行字符串,包括换行符。

print("""Sum:98
Product:69132994560""")

C

参考 Daniel 大佬提到的贪心算法,注意到 n=9a+b ,于是 S(n)_{min}=\overline{b\underbrace{999\cdots999}_{a}} ,然后得到下面代码。ps: 当 b=0 时,要去除 b

n = int(input())
a = n // 9
b = n % 9
print(('' if b == 0 else str(b)) + '9' * a)

D

按照题目输入判断输出即可。ps: 灵活使用 Python 提供的内置函数如 max() 等,Python缩进为 4 个空格,不建议使用 tab 制表符。

n, k = [int(i) for i in input().strip().split()]

ma = 0

a = [int(i) for i in input().strip().split()]
for i in a:
	if i >= k:
		print('hao! hen you jing shen!')
	else:
		print('ni bu gou jing shen!')

b = max(a)
if b >= k:
	print(b)
else:
	print('I am angry!')

E

本质上是把矩形分为若干个最大的正方形。不妨假设 n<mnm=n^2+n(m-n)n^2 是一个正方形,其周长为 4n ,接着对 n(m-n) 重复上述操作,并把周长全部加起来即可。

n = int(input())

for _ in range(n):
	a = [int(i) for i in input().strip().split()]
	s = 0
	while a[0] != a[1]:
		a.sort()
		s += a[0]*4
		a = [a[0], a[1] - a[0]]
	s += a[0]*4
	print(s)

F

按照题意统计并找到最大值然后依次做差再求和即可。

n = int(input())

for _ in range(n):
	input()
	a = [0 for _ in range(10)]
	s = input().replace(' ', '')
	for i in s:
		a[int(i) - 1] += 1
	a_max = max(a)
	sss = 0
	for i in a:
		if not i == 0:
			sss += a_max - i
	print(sss)

G

创建个字母表,然后按照题目做即可。

alp = 'abcdefghijklmnopqrstuvwxyz'

def add(s,x):
	ss = ''
	for i in s:
		ss += alp[(alp.index(i)+x)%26]
	return ss
	
def fuck(s):
	for i in range(0,26):
		ss = add(s,i)
		if not ("error" in ss) and not("warning" in ss):
			return True
	return False
	
t = int(input())

for _ in range(t):
	input()
	if(fuck(input())):
		print('0 error(s), 0 warning(s)')
	else:
		print('Oops!')

H

读题,看清题意,然后按照题目模拟即可。ps: 现实事物抽象并封装成类。

class Ym:
    def __init__(self,h,ark,k,kh):
        self.h = h
        self.ark = ark
        self.k = k
        self.kh = kh

class Bs:
    def __init__(self,h,ark,t):
        self.h = h
        self.ark = ark
        self.t = t
flag = True
def fuck():
    global flag
    flag = False
    print('My Milk!')
def win():
    global flag
    flag = False
    print('Mission Complete.')

ym = Ym(*[int(i) for i in input().strip().split()])
bs = []
ymh = ym.h
n = int(input())
for _ in range(n):
    bs.append(Bs(*[int(i) for i in input().strip().split()]))

tnn = 0

tt = 0
bss = []
for t in range(0,3100):
    for i in bs:
        if i.t == t:
            bss.append(i)
            tnn += 1
    if len(bss) > 1:
        fuck()
        break
    elif len(bss) == 1:
        tt = 0
        bss[0].h -= ym.ark
        ym.h -= bss[0].ark
        if bss[0].h <= 0:
            del bss[0]
        if ym.h <= 0:
            fuck()
            break
    else:
        tt += 1
        if tt == ym.k:
            ym.h += ym.kh
            if ym.h > ymh:
                ym.h = ymh
    if tnn >= n:
        win()
        break
if(flag):
    win()

I&J

由于这两道题需要较高的性能,所以我也懒得用 Python 尝试了。这里给出 J 题的一种叫做模式匹配判断合法括号序列的方法。

def cheak(s):
    while True:
        s2 = s
        s = s.replace('()','')
        if len(s) == 0:
            return True
        elif s2 == s:
            return False

这里给出简要的数学证明。按照题意给出的合法括号序列定义:

  • 空串是一个合法的括号序列。
  • 如果字符串 A 是一个合法的括号序列,那么字符串 (A) 也是一个合法的括号序列。
  • 如果字符串 AB 都是一个合法的括号序列,那么字符串 AB 也是一个合法的括号序列。

可以很容易得出括号序列的一个性质:考虑 *(*)* ,它是一种分形结构。

由此我们很容易可以知道在序列中,不断的将 () 去除,最后这个序列必定为空。反之,其不是合法括号序列。

2赞
粤 ICP 备 2020080455 号