试题 A: 解密

【问题描述】
小明设计了一种文章加密的方法：对于每个字母 c，将它变成某个另外的字符 Tc。下表给出了字符变换的规则：

image

例如，将字符串 YeRi 加密可得字符串 EaFn。小明有一个随机的字符串，加密后为
EaFnjISplhFviDhwFbEjRjfIBBkRyY

模拟就行

试题 B: 纪念日

2020 年 7 月 1 日是中国共产党成立 99 周年纪念日。中国共产党成立于 1921 年 7 月 23 日。请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包含多少分钟？

import datetime
def cal(s, e):
    s1 = datetime.datetime.strptime(s, "%Y-%m-%d %H")
    e1 = datetime.datetime.strptime(e, "%Y-%m-%d %H")
    print((e1-s1).total_seconds()/60)
    print(int(str(e1-s1).split()[0])*24*60)

cal("1921-7-23 12","2020-7-1 12")
# 52038720

试题 C: REPEAT 程序

【问题描述】附件 prog.txt 中是一个用某种语言写的程序。其中 REPEAT k 表示一个次数为 k 的循环。循环控制的范围由缩进表达，从次行开始连续的缩进比该行多的（前面的空白更长的）为循环包含的内容。
例如如下片段：

image

该片段中从 A = A + 4 所在的行到 A = A + 8 所在的行都在第一行的循环两次中。 REPEAT 6: 所在的行到 A = A + 7 所在的行都在 REPEAT 5: 循环中。 A = A + 5 实际总共的循环次数是 2×5×6 = 60 次。请问该程序执行完毕之后，A 的值是多少？
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

会python的直接改成python即可，241830
或者用栈模拟一下

with open("C:/Users/17861/Desktop/prog.txt") as f:
    data = f.readlines()
A = 0
n = len(data)
tt = -1
st = [0 for i in range(n)]

def cal(s):
    cnt = 0
    x = 0
    flag = 0
    for i in range(len(s)):
        if (s[i] == ' '):
            cnt += 1
        else:
            if s[i] == "A":
                flag = 1
                x = int(s[i:].split()[-1])
            else:
                flag = 0
                # print(s, len(s), ":",s[i:])
                x = int(s[i:].split()[-1][:-1])
            break
    return cnt // 4, flag, x

res = 0 
pre = 0
mul = 1
for i in range(1, n):
    if len(data[i]) < 5: continue
    cnt, flag, x = cal(data[i])
    # print(data[i],cnt,flag,x)
    if pre <= cnt:
        pre = cnt
        if flag == 0:
            mul *= x
            tt += 1
            st[tt] = x
        else:
            res += mul * x
    
    else:
        while pre >  cnt:
            
            # print(pre, tt, st[tt])
            mul //= st[tt]
            tt -= 1
            pre -= 1
    
        if flag == 0:
            mul *= x
            tt += 1
            st[tt] = x
        else:
            res += mul * x
            
    
print(res)
# 241830

试题 D: 矩阵

本题总分：10 分
【问题描述】把 1 ∼ 2020 放在 2×1010 的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？
答案很大，你只需要给出方案数除以 2020 的余数即可。
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分

卡特兰数：参考数论知识

考虑把 1-2n 从小到大依次放进矩阵中，可以发现每次放置的位置只能是第一行的最左空位或第二行的最左空位（否则左边一定会放一个更大的元素，而这不合法）。同时，如果放在第二行，那么要保证它上方已经有数字（否则会放一个更大的进去，同样不合法）。那么这样子可以把放在第一行看成 (，放在第二行看成 )，也就是计数长度为 2n的合法括号序列。根据卡特兰数，这个数量为

# n = int(input())
MOD = 2020
N = 3000
c = [[0 for j in range(N)] for i in range(N)]
n = 1010

for i in range(0, N):
    for j in range(0, i+1):
        if j == 0:
            c[i][j] = 1
        else:
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD
        
print(((c[2*n][n]-c[2*n][n-1]) % MOD + MOD) % MOD)
# 1340

或者DP（集合表示一类方案）

# n = int(input())
MOD = 2020
N = 3000
dp = [[0 for j in range(N)] for i in range(N)] # 第1行i个人，第2行j个人的方案数
n = 1010

dp[0][0] = 1 # 不放也是方案
        
for i in range(0, n+1):
    for j in range(0, n+1):
        if i != 0 and i -1 >= j: # 转移前的状态也要合法，即第一行的数量不小于第二行的数量
            dp[i][j] = (dp[i][j] + dp[i-1][j])%MOD
        if j != 0 :
            dp[i][j] = (dp[i][j] + dp[i][j-1])%MOD
print(dp[n][n])       
# 1340

解释：

提高题：AcWing 271. 杨老师的照相排列

从小到大，在每一排里，当前排好的人在左边连续一段。

yxc大佬：

image

https://www.acwing.com/file_system/file/content/whole/index/content/1374560/

试题 E: 完美平方数

本题总分：15 分
【问题描述】如果整个整数 X 本身是完全平方数，同时它的每一位数字也都是完全平方数，我们就称 X 是完美平方数。前几个完美平方数是 0、1、4、9、49、100、144…… 即第 1 个完美平方数是 0，第 2 个是 1，第 3 个是 4，…… 请你计算第 2020 个完美平方数是多少？
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

这题感觉比较难
目前较快的解法为，是跳着枚举，因为只会出现0、1、4、9，比如到235了，咱们从头扫一遍，变成400，一个大佬的解法，牛逼

import math

list = [0, 1, 4, 9]
list_num = []
num = 0

def check(perfect):
    if perfect == 0:
        return True
    length = len(str(perfect))
    for i in range(0, length):
        # print(perfect)
        if int(str(perfect)[i]) not in list:
            tmp = int(str(perfect)[:i+1])
            #print("tmp  ", tmp)
            plus = int(str(perfect)[i])
            # print("plus ", plus)
            for k in range(1, 4):
                if int(list[k]) > plus:
                    plus = int(list[k])
                    break
            # print("plus ", plus)
            # print("tmp//10", tmp//10)
            plus = (tmp//10)*10 + plus   # 不用改动的数
            # print("qplus", plus)
            for j in range(1, length - i):
                plus = plus * 10

            # print("wwww ", plus)

            num_t = int(math.sqrt(plus))
            global num
            if num_t * num_t != plus:
                num = num_t + 1
            else:
                num = num_t
            # print("num :", num)
            return False
    return True


flag = True
cnt = 0
while cnt < 2030:
    # print("main " , num)
    perfect = num * num

    if check(perfect):
        cnt = cnt + 1
        num = num + 1
        print(str(perfect) + "    " + str(cnt))

下面的程序题，没法验证，口胡就行。

试题 F: 分类计数

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分
【问题描述】
输入一个字符串，请输出这个字符串包含多少个大写字母，多少个小写字母，多少个数字。
【输入格式】
输入一行包含一个字符串。
【输出格式】
输出三行，每行一个整数，分别表示大写字母、小写字母和数字的个数。
【样例输入】 1+a=Aab
【样例输出】 1 3 1
【评测用例规模与约定】对于所有评测用例，字符串由可见字符组成，长度不超过 100。

有手就行。

s = input()
cnt1, cnt2, cnt3 = 0, 0 , 0
for it in s:
    if it <= '9' and it >= '0':
        cnt1 += 1
    elif it <= 'z' and it >= 'a':
        cnt2 += 1
    elif it <= 'Z' and it >= 'A':
        cnt3 += 1
print(cnt3)
print(cnt2)
print(cnt1)

试题 G: 八次求和

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】给定正整数 n, 求 18 + 28 +···+ n8 mod 123456789 。其中 mod 表示取余。
【输入格式】
输入的第一行包含一个整数 n。
【输出格式】
输出一行，包含一个整数，表示答案。
【样例输入】 2
【样例输出】 257
【样例输入】 987654
【样例输出】 43636805
【评测用例规模与约定】对于 20% 的评测用例，1≤n≤20。对于 60% 的评测用例，1≤n≤1000。对于所有评测用例，1≤n≤1000000。

快速幂， python内置的pow是基于快速幂的

IA = lambda:map(int, input())
MOD = 123456789

res = 0
n = int(input()) 
for i in range(1, n+1):
    res = (res + pow(i, 8, MOD)) % MOD

print(res)

试题 H: 字符串编码

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】
小明发明了一种给由全大写字母组成的字符串编码的方法。对于每一个大写字母，小明将它转换成它在 26 个英文字母中序号，即 A→1, B→2, ... Z→ 26。这样一个字符串就能被转化成一个数字序列：比如 ABCXYZ → 123242526。现在给定一个转换后的数字序列，小明想还原出原本的字符串。当然这样的还原有可能存在多个符合条件的字符串。小明希望找出其中字典序最大的字符串。
【输入格式】
一个数字序列。
【输出格式】
一个只包含大写字母的字符串，代表答案
【样例输入】 123242526
【样例输出】 LCXYZ
【评测用例规模与约定】对于 20% 的评测用例，输入的长度不超过 20。对于所有评测用例，输入的长度不超过 200000

贪心凑最大的就行

s = input()
base = ord('A')
pre = s[0]
for i in range(1, len(s)):
    if pre == "-1":
        pre = s[i]
        continue
    x = int(pre + s[i])
    if x > 26:
        x = int(pre)
        pre = s[i]
    else:
        pre = "-1"
    print(chr(base + x - 1), end="")
        
if pre != "-1":
    x = int(pre)
    print(chr(base + x - 1), end="")

试题 I: BST 插入节点问题

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
【问题描述】给定一棵包含 N 个节点的二叉树，节点编号是 1 ∼ N。其中 i 号节点具有权值 Wi，并且这些节点的权值恰好形成了一棵排序二叉树 (BST)。现在给定一个节点编号 K，小明想知道，在这 N 个权值以外，有多少个整数 X (即 X 不等于任何 Wi ) 满足：给编号为 K 的节点增加一个权值为 X 的子节点，仍可以得到一棵 BST。例如在下图中，括号外的数字表示编号、括号内的数字表示权值。即编号 1∼4 的节点权值依次是 0、10、20、30。
如果 K = 1，那么答案为 0。因为 1 号节点已经有左右子节点，不能再增加子节点了。如果 K = 2，那么答案为无穷多。因为任何一个负数都可以作为 2 的左子节点。如果 K = 3，那么答案为 9。因为 X = 11,12,··· ,19 都可以作为 3 的左子节点。
【输入格式】
第一行包含 2 个整数 N 和 K。以下 N 行每行包含 2 个整数，其中第 i 行是编号为 i 的节点的父节点编号 Pi 和权值 Wi 。注意 Pi = 0 表示 i 是根节点。输入保证是一棵 BST。
试题 I: BST 插入节点问题 11
第十一届蓝桥杯大赛软件类省赛 Python 大学组
【输出格式】一个整数代表答案。如果答案是无穷多，输出 −1。
【样例输入】 4 3 0 10 1 0 1 20 3 30
【样例输出】 9
【评测用例规模与约定】对于 60% 的评测用例，1≤ K ≤ N ≤100，0≤Wi ≤200，且 Wi 各不相同。对于所有评测用例，1 ≤ K ≤ N ≤ 10000，0 ≤ Wi ≤ 100000000，且 Wi 各不相同。

二叉排序树的中序遍历是有序的，所以拍一个序，看一下左右即可

IA = lambda:map(int, input().split())
N = 10010
l = [-1 for i in range(N)]
r = [-1 for i in range(N)]

fa = [-1 for i in range(N)]



n, k = IA()
w = [[0, 0] for i in range(n)]
for i in range(1, n+1):
    a, b = IA()
    fa[i] = a
    if a == 0:
        root = i
    w[i-1][0] = b
    w[i-1][1] = i

for i in range(1, n+1):
    if i == root:
        continue
    if w[i-1][0] <= w[fa[i]-1][0]:
        l[fa[i]] = i
    else:
        r[fa[i]] = i


w = sorted(w)
pos = 0
for i in range(n):
    if w[i][1] == k:
        pos = i
# print(pos)
if l[k] != -1 and r[k] != -1:
    print(0)
elif pos == 0 or pos == n-1:
    print(-1)
else:
    if l[k] == -1 and r[k] == -1:
        print(w[pos+1][0] - w[pos-1][0] - 2)
    elif l[k] != -1 and r[k] == -1:
        print(w[pos+1][0] - w[pos][0] - 1)
    elif l[k] == -1 and r[k] != -1:
        print(w[pos][0] - w[pos-1][0] - 1)

试题 J: 网络分析

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
【问题描述】
小明正在做一个网络实验。他设置了 n 台电脑，称为节点，用于收发和存储数据。初始时，所有节点都是独立的，不存在任何连接。
小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。两个节点如果存在网线连接，称为相邻。
小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。一条信息只存储一次。
给出小明连接和测试的过程，请计算出每个节点存储信息的大小。
【输入格式】
输入的第一行包含两个整数 n,m，分别表示节点数量和操作数量。节点从 1 至 n 编号。接下来 m 行，每行三个整数，表示一个操作。如果操作为 1 a b，表示将节点 a 和节点 b 通过网线连接起来。当 a = b 时，表示连接了一个自环，对网络没有实质影响。如果操作为 2 p t，表示在节点 p 上发送一条大小为 t 的信息。
【输出格式】
输出一行，包含 n 个整数，相邻整数之间用一个空格分割，依次表示进行完上述操作后节点 1 至节点 n 上存储信息的大小。
试题J: 网络分析 13
第十一届蓝桥杯大赛软件类省赛 Python 大学组
【样例输入】 4 8 1 1 2 2 1 10 2 3 5 1 4 1 2 2 2 1 1 2 1 2 4 2 2 1
【样例输出】 13 13 5 3
【评测用例规模与约定】对于 30% 的评测用例，1≤n≤20，1≤m≤100。对于 50% 的评测用例，1≤n≤100，1≤m≤1000。对于 70% 的评测用例，1≤n≤1000，1≤m≤10000。对于所有评测用例，1≤n≤10000，1≤m≤100000，1≤t≤100。

带权并查集，d表示每一个点与根节点的差值（带正负）。

N = 1000010
IA = lambda:map(int, input().split())

n, m = IA()

fa = [i for i in range(N)]
d = [0 for i in range(N)]
res = [0 for i in range(N)]

def get(x):
    if x != fa[x]:
        t = fa[x]
        fa[x] = get(fa[x])
        d[x] += d[t] # 它到父节点的距离 + 它到根节点的距离 
    return fa[x]

for _ in range(m):
    a, b, c = IA()
    if a == 1:
        fx = get(b)
        fy = get(c)
        if fx != fy:
            fa[fy] = fx
            d[fy] = res[fy] - res[fx]
            
    else:
        f = get(b)
        res[f] += c
for i in range(1, n+1):
    print(res[get(i)] + d[i],end = " ")

C++ b组

整除序列

题目描述
有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，请输出这个序列中值为正数的项。

输入格式
输入一行包含一个整数 n。

输出格式
输出一行，包含多个整数，相邻的整数之间用一个空格分隔，表示答案。

数据范围
1≤n≤1018
输入样例：
20
输出样例：
20 10 5 2 1
水题一枚

#include <iostream>

using namespace std;

long long n;

int main(){
    cin >> n;
    while(n > 0){
        cout << n << ' ';
        n = n >> 1;
    }

    return 0;
}

解码

小明有一串很长的英文字母，可能包含大写和小写。

在这串字母中，有很多连续的是重复的。

小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。

例如，连续的 5 个 a，即 aaaaa，小明可以简写成 a5（也可能简写成 a4a、aa3a 等）。

对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。

为了方便表达，小明不会将连续的超过 9 个相同的字符写成简写的形式。
，请帮助小明还原成原来的串。

输入格式
输入一行包含一个字符串。

输出格式
输出一个字符串，表示还原后的串。

数据范围
输入字符串由大小写英文字母和数字组成，长度不超过 100。
请注意原来的串长度可能超过 100。

输入样例：
H3el5o2
输出样例：
HHHellllloo

模拟

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        
        if(s[i]<='9'&&s[i]>='0')
        {
            for(int j=0;j<s[i]-'0'-1;j++)
            {
                printf("%c",s[i-1]);
            }
        }
        else
        {
            printf("%c",s[i]);
        }
    }
    return 0;
}

走方格

在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。

现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。

只能向右或者向下走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

输入格式
输入一行包含两个整数 n,m。

输出格式
输出一个整数，表示答案。

数据范围
1≤n,m≤30
输入样例1：
3 4
输出样例1：
2
输入样例2：
6 6
输出样例2：
0

经典DP or 记忆化搜索

IA = lambda:map(int,input().split())
n,m = IA()
N = 35
dp = [[0 for j in range(N)] for i in range(N)]

for i in range(0,N):
    dp[i][1] = 1
for j in range(N):
    dp[1][j] = 1
    
for i in range(2,n+1):
    for j in range(2,m+1):
        if(i&1 or j&1):
            dp[i][j] = dp[i-1][j]+dp[i][j-1]

print(dp[n][m])

IA = lambda:map(int ,input().split())
N = 35
f = [[0 for j in range(N)] for i in range(N)]
n,m =IA()
f[n][m] = (n&1 or m&1)
def dfs(x, y):
    if (x&1 or y&1):
        if f[x][y]!=0:
            return f[x][y]
        if(x<n):
            f[x][y]+=dfs(x+1,y)
        if(y<m):
            f[x][y]+=dfs(x,y+1)
    return f[x][y]
print(dfs(1,1))

整数拼接

给定义个长度为 n 的数组A1, A2, · · · , An。你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai = Aj 时。

请你计算有多少种拼法满足拼出的整数是 K 的倍数。

思路
$(A[i] *10^{len(A[j]})+A[j]) \ \% K == 0$
$A[i] *10^{len(A[j]})\% K\ +\ A[j]\ \% \ K == 0$

那我们遍历A[j]之前预处理出来用cnr[i][j]预处里了出来A[i]在乘以长度为i的A[j]的得出结果为j的A[i]的个数。
$j = A[i] *10^{len(A[j]}\% K$
$也可以j =( (K - A[i] *10^{len(A[j]}\% K )\% K +K)\% K$

IA = lambda:map(int,input().split())
N = 100005
n,mod = IA()
a = list(IA())
cnt = [[0 for j in range(N)] for i in range(11)]
ans = 0
def cal(n):
    res = 0
    while n > 0:
        res += 1
        n //= 10
    return res
def work():
    global mod,ans
    for it in a:
        ans += cnt[cal(it)][it%mod]
        base = 10
        temp = it
        for i in range(1,11):
            temp = (temp * base) % mod
            cnt[i][(mod-temp%mod)%mod] += 1
        

work()        
a = a[::-1]
cnt = [[0 for j in range(N)] for i in range(11)]
work()
print(ans)

2020蓝桥杯七月真题(python和c++）

2020蓝桥杯七月真题(python和c++）

试题 A: 解密

试题 B: 纪念日

试题 C: REPEAT 程序

试题 D: 矩阵

试题 E: 完美平方数

试题 F: 分类计数

试题 G: 八次求和

试题 H: 字符串编码

试题 I: BST 插入节点问题

试题 J: 网络分析

整除序列

解码

走方格

整数拼接