蓝桥杯2015初赛python题解_蓝桥杯python初赛

传功门

方程整数解

思路：枚举+优化
不必写三个循环，可以直接通过a和b得出c的值，再判断c是否合法就行了。写三个循环会超时。

import math
while True:
        n = int(input())
        flag = 0
        for a in range(1, 101):
            for b in range(a, 101):
                c = n - a*a - b*b
                if c < 0:
                    continue
                c = math.sqrt(c)
                if(int(c) == c and  c >= b):
                    flag = 1
                    print("{0} {1} {2}".format(a, b, int(c)))
        if not flag:
            print("No Solution")


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

星系炸弹

思路:数据量比较小，可以模拟每次日期加一，n减1，直到n=0

while True:
    month = [-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    a, b, c, n = map(int, input().split())
    if (a%4 == 0 and a%100 != 0) or (a%400 == 0):
        month[2] = 29
    while n > 0:
        n-=1
        c+=1
        if month[b] < c:
            c = 1
            b+=1
            if b == 13:
                b = 1
                a += 1
                if (a%4 == 0 and a%100 != 0) or (a%400 == 0):
                    month[2] = 29
                else :
                    month[2] = 28
    print("{0:0>4d}-{1:0>2d}-{2:0>2d}".format(a, b, c))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

奇妙的数字

思路：枚举每一个数字然后判断这个数字是否符合题意就行了

for i in range(1, 999999999):
    string = str(i*i + i*i*i)
    ls = [1 for i in range(10)]
    for j in string:
        ls[int(j)] -= 1
    flag = 1
    for j in ls:
        if j != 0:
            flag = 0
            break
    if flag:
        print(i, string)
        break

1
2
3
4
5
6
7
8
9
10
11
12
13
14

奇妙的数字

思路：枚举所有数字，进行判断。判断的时候可以设置一个大小为10的列表，下标表示0~9的数字，值为该数字的数量。

def judge(s1, s2):
    flag = True
    ls = [1 for i in range(10)]
    for i in s1:
        ls[int(i)] -= 1
    for i in s2:
        ls[int(i)] -= 1
    for i in ls:
        if i != 0:
            flag = False
            break
    return flag
        

for i in range(1, 999999999):
    if judge(str(i*i), str(i*i*i)):
        print(i, end = '')
        break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

牌型种数

思路：相当于把牌分成13堆，每一堆有四张相同的牌，问你取13张牌有多少取法，等价于把数字13进行分解，分成13个数的和。可以枚举这13个数，然后统计合法的个数。直接写13个for循环，或者用递归。

ans = 0
def fn(sm, cnt):
    global ans
    if(sm > 13):
        return
    if cnt == 14:
        if sm == 13:
            ans = ans + 1
        return
    for a in range(5):
        fn(sm + a, cnt + 1)

fn(0, 1)
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

手链样式

思路：对于上题，手链的直排列数量（c(12, 4)*c(8, 3)）除以珠子个数（12）就是圆排列数量，再考虑链子的翻转情况，也就是对称情况，需要把这个数量再除以2，但是对于一些本身就对称的圆手链，上面除以2就多减了，需要补上本身就对称的情况（c(5, 1)*c(4, 2)//2）

def c(a, b):
    if a < b: return 0
    if b == 0:
        return 1
    return c(a-1, b) + c(a-1, b-1)
print(c(12, 4)*c(8, 3)//12//2 + c(5, 1)*c(4, 2)//2)

1
2
3
4
5
6
7

饮料换购

思路：先算额外兑换的饮料数量，再加上初始饮料，就是答案了。对于三瓶以下的饮料，额外的饮料为0，对于三瓶可以兑换1瓶饮料，接下来每买两瓶饮料，再加上上一次兑换饮料的瓶盖，就又可以兑换一瓶，所以对于 n > 3, 额外的饮料数量为(n-3)//2 + 1

while True:
    n = int(input())
    if n < 3:
        print(n)
    elif n == 3:
        print(n+1)
    else :
        print((n-3)//2 + 1 + n)

1
2
3
4
5
6
7
8
9

垒骰子

灾后重建

奖券数目

比较简单，不多说

cnt = 0
for i in range(10000, 100000):
    j = str(i)
    if j.find('4') == -1:
        cnt += 1
print(cnt)

1
2
3
4
5
6
7

三羊献瑞

思路：最暴力的做法，直接枚举所有的数字，然后判断是否合法就行了。

for xiang in range(10):
    for rui in range(10):
        if(xiang == rui):
            continue
        for sheng in range(10):
            if sheng == xiang or sheng == rui:
                continue
            for hui in range(10):
                if hui == xiang or hui == rui or hui == sheng:
                    continue
                for san in range(10):
                    if san == xiang or san == rui or san == sheng or san == hui:
                        continue
                    for yang in range(10):
                        if yang == xiang or yang == rui or yang == sheng or yang == hui or yang == san:
                            continue
                        for xian in range(10):
                            if xian == xiang or xian == rui or xian == sheng or xian == hui or xian == san or xian == yang:
                                continue
                            a = xiang*1000 + rui*100 + sheng*10 + hui
                            b = san*1000 + yang*100 + xian*10 + rui
                            c = a+b
                            strc = str(c)
                            if int(strc[0]) == san and int(strc[1]) == yang and int(strc[2]) == sheng and int(strc[3]) == rui and int(strc[-1]) != xiang and int(strc[-1]) != rui and int(strc[-1]) != sheng and int(strc[-1]) != hui and int(strc[-1]) != san and int(strc[-1]) != yang and int(strc[-1]) != xian and int(strc[-1]) != rui:
                                #print("{0:>5}\n{1:>5}\n{2:>5}".format(a, b, c))
                                print(b)
    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

加法变乘法

思路：枚举两个乘法的位置

for i in range(1, 50):
    #枚举第一个乘法左边的数字
    for j in range(i+2, 50):
        #枚举第二个乘法左边的数字
        res = 1225 - (i + i + 1) + (i*(i+1)) - (j + j + 1) + (j*(j+1))
        if res == 2015:
            if i != 10:
                print(i)
        

1
2
3
4
5
6
7
8
9
10

移动距离

思路：
**核心思想：**如果以左上角为原点建系，分别以竖直向下和水平向右为正方形，（x，y）为坐标，x代表点所在行数，y代表所在列数。则两点（x1, y1）(x2, y2)间的移动距离就是(abs(x1 - x2) + abs(x2, y2))。
那么最主要的就是根据序号求出其坐标。我定义行数和列数从零开始算起。可以根据我的代码推演以下公式，我不多说了。

while True:
    w, m, n = map(int, input().split())
    #表示m所在行正方向递增
    if ((m-1)//w)&1 == 0:、
    #cm表示m的行数，rm表示m的列数
        cm = (m-1)//w
        rm = (m-1)%w
    #m所在行反方向递增
    else:
        cm = (m-1)//w
        rm = w-(m-1)%w-1
    #下述代码的意义与上述同理
    if ((n-1)//w)&1 == 0:
        cn = (n-1)//w
        rn = (n-1)%w
    else:
        cn = (n-1)//w
        rn = w-(n-1)%w-1
    #print(cm, rm, cn, rn)
    ans = abs(cm-cn) + abs(rn-rm)
    print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

生命之树

ps：嗯……思路应该是没问题的，但是样例只过了44%，看了很久也没看出什么毛病，可以按照我的思路再写一遍，然后浇浇我。
思路：题目意思就是让你求出树中连通块（各个点都有路径连接）之和最大值。考虑动态规划，定义状态f[i]为以i节点为根并且s集合包括i的树的评分。因为f[i]评分中是包括i，则可以求出i的孩子的f值，如果f[孩子] > 0,这f[i] += f[孩子], 否则f[孩子] < 0则没有必要管它。最终的f[i]就是我们要的答案了。

N = int(1e5+10)
INF = 999999999
f = [-INF for i in range(N)]#f[i]以i节点为根的之树评分
w = [0]#权值
g = [[] for i in range(N)]#邻接表存图

def add(a, b):#增加一条a到b的边
    g[a].append(b)

def dfs(u, fa):#u的父节点是fa，求以u为根的树的评分
    f[u] = w[u]
    for i in g[u]:
        if i != fa and dfs(i, u) > 0:
            f[u] += f[i]
    return f[u]

n = int(input())
w.extend(list(map(int, input().split())))
for i in range(n-1):
    a, b = map(int, input().split())
    add(a, b)
    add(b, a)

dfs(1, 0)
ans = 0#树最小的评分是0，即一个都不选
for i in range(1, n+1):
    ans = max(ans, f[i])
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

打印大X

思路：模拟打印过程，先从左上角画，再从右上角画。

while True:
    m, n =  map(int, input().split())
    width = n-1+m
    #print(width, n)
	#初始化图
    ls = [['.' for i in range(width)] for j in range(n)]


    def paint(x, y):
        for i in range(m):
            ls[x][y+i] = '*'
    #往右下画
    x = 0
    y =0
    for i in range(n):
        paint(x, y)
        x += 1
        y += 1
        #print(x, y)
    #往左下画
    x = 0
    y = width-m
    #print("ok")
    for i in range(n):
        #print(x, y)
        paint(x, y)
        x += 1
        y -= 1
    for i in range(n):
        for j in range(width):
            print(ls[i][j], end = "")
        print("")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33