第十一届蓝桥杯大赛第二次模拟（软件类）| Python（待补充）

短命女 2022-12-02 11:00 108阅读 0赞

### 1. 12.5MB ###

【问题描述】  
在计算机存储中，12.5MB是多少字节？  
【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

**题目解析：**

> 1MB=1024KB  
> 1KB=1024B(字节)  
> 1B=8bit（位）

**相应程序：**

print(12.5*1024*1024)

**题目答案：** `13107200`

### 2. 最多边数 ###

【问题描述】  
一个包含有2019个结点的有向图，最多包含多少条边？（不允许有重边）  
【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

**题目解析：**

> 有向图就是无向图的两倍。  
> 要求最多边数，那就是全连接了。  
> 三个点的边就是3×2=6  
> 四个点的边就是4×3=12  
> 五个点的边就是5×4=20  
> …  
> 以此类推2019个点的边就是2019×2018

**相应程序：**

print(2019*2018)

**题目答案：** `4074342`

### 3. 单词重排 ###

【问题描述】  
将LANQIAO中的字母重新排列，可以得到不同的单词，如LANQIAO、AAILNOQ等，注意这7个字母都要被用上，单词不一定有具体的英文意义。  
请问，总共能排列如多少个不同的单词。  
【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

**题目解析：**

> 这就是一个排列组合问题，字母A的话在这七个坑里面选两个填坑，那就是  C 7 2 C\_7^2 C72 剩下五个字母就是  A 5 5 A\_5^5 A55（全排列）  
> 结果就是  C 7 2 × A 5 5 C\_7^2×A\_5^5 C72×A55

**相应程序：**

from math import factorial
    
    def Permutation(m,n):
        '''A_n^m'''
        return factorial(n)/factorial(n-m)
    
    def Combination(m,n):
        '''C_n^m'''
        return factorial(n)/factorial(n-m)/factorial(m)
    
    n = Combination(2,7)*Permutation(5,5)
    print(n)

**题目答案：** `2520`

### 4. 括号序列 ###

【问题描述】  
由1对括号，可以组成一种合法括号序列：()。  
由2对括号，可以组成两种合法括号序列：()()、(())。  
由4对括号组成的合法括号序列一共有多少种？  
【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

**题目解析：**

> 问题规模小，可枚举

**题目答案：** `14`

### 5. 反倍数 ###

【问题描述】  
给定三个整数 a, b, c，如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。  
请问在 1 至 n 中有多少个反倍数。  
【输入格式】  
输入的第一行包含一个整数 n。  
第二行包含三个整数 a, b, c，相邻两个数之间用一个空格分隔。  
【输出格式】  
输出一行包含一个整数，表示答案。  
【样例输入】  
30  
2 3 6  
【样例输出】  
10  
【样例说明】  
以下这些数满足要求：1, 5, 7, 11, 13, 17, 19, 23, 25, 29。  
【评测用例规模与约定】  
对于 40% 的评测用例，1 <= n <= 10000。  
对于 80% 的评测用例，1 <= n <= 100000。  
对于所有评测用例，1 <= n <= 1000000，1 <= a <= n，1 <= b <= n，1 <= c <= n。

**题目解析：**

> 暴力求解

**相应程序：**

n = eval(input())
    a, b, c = map(eval,input().split())
    count = 0
    for i in range(1,n+1):
        if (i%a!=0)&(i%b!=0)&(i%c!=0):
            count += 1
    print(count)

### 6. 凯撒加密 ###

【问题描述】  
给定一个单词，请使用凯撒密码将这个单词加密。  
凯撒密码是一种替换加密的技术，单词中的所有字母都在字母表上向后偏移3位后被替换成密文。即a变为d，b变为e，...，w变为z，x变为a，y变为b，z变为c。  
例如，lanqiao会变成odqtldr。  
【输入格式】  
输入一行，包含一个单词，单词中只包含小写英文字母。  
【输出格式】  
输出一行，表示加密后的密文。  
【样例输入】  
lanqiao  
【样例输出】  
odqtldr  
【评测用例规模与约定】  
对于所有评测用例，单词中的字母个数不超过100。

si = input()
    so = ''
    for i in si:
        so += chr(ord(i)-23) if 'x' <= i <= 'z' else chr(ord(i)+3)
    print(so)

### 7. 螺旋 ###

【问题描述】  
对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。  
例如，一个 4 行 5 列的螺旋矩阵如下：  
1 2 3 4 5  
14 15 16 17 6  
13 20 19 18 7  
12 11 10 9 8  
【输入格式】  
输入的第一行包含两个整数 n, m，分别表示螺旋矩阵的行数和列数。  
第二行包含两个整数 r, c，表示要求的行号和列号。  
【输出格式】  
输出一个整数，表示螺旋矩阵中第 r 行第 c 列的元素的值。  
【样例输入】  
4 5  
2 2  
【样例输出】  
15  
【评测用例规模与约定】  
对于 30% 的评测用例，2 <= n, m <= 20。  
对于 70% 的评测用例，2 <= n, m <= 100。  
对于所有评测用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m。

def Matrix(n,m):
        # 生成步长向量
        a = m
        b = n-1
        A = []
        while a>=1 and b>=1:
            A.append(a)
            A.append(b)
            a -= 1
            b -= 1
        A.append(a)
        # 生成螺旋矩阵
        M = [[None for i in range(m)] for i in range(n)]
        Ai, count, col, row = 0, 0, -1, 0
        # 给每个数字安排位置
        for i in range(1,n*m+1):
            # 判断是否转向
            if count == A[Ai]:
                Ai += 1
                count = 0
            count += 1
            # 选择行进方向
            if Ai%4 == 0:
                col += 1
            elif Ai%4 == 1:
                row += 1
            elif Ai%4 == 2:
                col -= 1
            else:
                row -= 1
            # 给相应数字安排位置
            M[row][col] = i
        ''' # 输出螺旋矩阵 for i in range(n): for j in range(m): print('{:3}'.format(M[i][j]), end='') print(' ') '''
        return M
    
    n, m = map(eval, input().split())
    r, c = map(eval, input().split())
    M = Matrix(n,m)
    print(M[r-1][c-1])

### 8. 摆动序列 ###

【问题描述】  
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a\[2i\]<a\[2i-1\], a\[2i+1\]>a\[2i\]。  
小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。  
【输入格式】  
输入一行包含两个整数 m，n。  
【输出格式】  
输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。  
【样例输入】  
3 4  
【样例输出】  
14  
【样例说明】  
以下是符合要求的摆动序列：  
2 1 2  
2 1 3  
2 1 4  
3 1 2  
3 1 3  
3 1 4  
3 2 3  
3 2 4  
4 1 2  
4 1 3  
4 1 4  
4 2 3  
4 2 4  
4 3 4  
【评测用例规模与约定】  
对于 20% 的评测用例，1 <= n, m <= 5；  
对于 50% 的评测用例，1 <= n, m <= 10；  
对于 80% 的评测用例，1 <= n, m <= 100；  
对于所有评测用例，1 <= n, m <= 1000。

*  **此方法只能计算80% 的评测用例**

# 用来储存已经计算过的数据
    Data = [[[None for i in range(1001)] for i in range(1001)] for i in range(2)]
    # 递归算法
    '''m: 当前位的数字 n: 当前数字后的序列长度 lim: 数字最高取值 ji: 当前数字是否在奇数位上 '''
    def dfc(m, n, lim, ji):
        global Data
        if n==1:
            if ji==1:
                return m-1
            else:
                return lim-m
        else:
            if Data[ji][m][n] != None:
                return Data[ji][m][n]
            Data[ji][m][n] = 0
            if ji:
                for i in range(1,m):
                    Data[ji][m][n] += dfc(i, n-1, lim, 0)
            else:
                for i in range(m+1, lim+1):
                    Data[ji][m][n] += dfc(i, n-1, lim, 1)
            return Data[ji][m][n]
    
    s = 0
    m, n = map(eval, input().split())
    for i in range(1,n+1):
       s +=  dfc(i, m-1, n, 1)
    print(s%10000)

*  进一步优化算法待补充。。。。。

### 9. 通电 ###

【问题描述】  
2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。  
这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。  
现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。  
小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 (x\_1, y\_1) 高度为 h\_1 的村庄与坐标为 (x\_2, y\_2) 高度为 h\_2 的村庄之间连接的费用为  
sqrt((x\_1-x\_2)\*(x\_1-x\_2)+(y\_1-y\_2)\*(y\_1-y\_2))+(h\_1-h\_2)\*(h\_1-h\_2)。  
在上式中 sqrt 表示取括号内的平方根。请注意括号的位置，高度的计算方式与横纵坐标的计算方式不同。  
由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。  
【输入格式】  
输入的第一行包含一个整数 n ，表示村庄的数量。  
接下来 n 行，每个三个整数 x, y, h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。  
【输出格式】  
输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。  
【样例输入】  
4  
1 1 3  
9 9 7  
8 8 6  
4 5 4  
【样例输出】  
17.41  
【评测用例规模与约定】  
对于 30% 的评测用例，1 <= n <= 10；  
对于 60% 的评测用例，1 <= n <= 100；  
对于所有评测用例，1 <= n <= 1000，0 <= x, y, h <= 10000。