2021年软件类第十二届蓝桥杯 省赛 python组 F-J题解

备战蓝桥杯的时候，记录一下写的题目和一些思考和理解

这里面的题目都可以从https://www.lanqiao.cn/courses/2786/learning/?id=280833得到，写了一些python的解法

在这一部分之中，我也配套做了一下视频的讲解，如果看题解太干涩，也可以去b站看看视频，这里给出链接B站视频

试题 F:时间显示

题目描述

小蓝要和朋友合作开发一个时间显示的网站。

在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

输入描述

输入一行包含一个整数，表示时间。

输出描述

输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值为 0 到 23，MM 表示分，值为 0 到 59，SS 表示秒，值为 0 到 59。时、分、秒 不足两位时补前导 0。

输入输出样例

示例 1

输入

46800999

输出

13:00:00

示例 2

输入

1618708103123

输出

01:08:23

评测用例规模与约定

对于所有评测用例，给定的时间为不超过 的正整数。

思路

对于这道题来说，其实也很简单，不过我这里给两种做法

第一种就是计算时间，这就需要我们计算秒，比如一天有24x60x60ms，然后计算天，时，分，秒，然后就可以得出来

第二种就是利用datetime库，那真的是很简单

代码1

# https://www.lanqiao.cn/problems/1452/learning/
t = int(input())
t = t//1000 # 转化为秒s
d = t % (24*60*60) # 得到一天的秒数，因为一天有24*60*60s
hh = d//(3600)  # 得到小时，因为一小时有3600
mm = d%3600//60
ss = d%60
print("%02d:%02d:%02d" % (hh, mm, ss))

代码2（利用datetime库）

# https://www.lanqiao.cn/problems/1452/learning/
import datetime
date = int(input())
start = datetime.datetime(1970,1,1,00,00,00)
timedelta = datetime.timedelta(milliseconds=date)
now = start+timedelta
strf = now.strftime("%H:%M:%S")
print(strf)

试题 G:杨辉三角形

题目描述

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：$ 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots$

给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

输入描述

输入一个整数 N。

输出描述

输出一个整数代表答案。

输入输出样例

示例 1

输入

6

输出

13

评测用例规模与约定

对于 20% 的评测用例，1 ≤ N ≤ 10 ； 对于所有评测用例1≤N≤1000000000。

实际上呢，这一道题是一道思维题，一开始我也搞不清楚这一道题要什么，后面发现居然是一道规律题。

这道题实在是有些复杂，首先我们就可以用我们的组合数，这个组合数我们也可以直接通过math库里面进行返回，实在不会我们也可以利用数学公式进行求得，也就是一个循环就可以得到。这里说明一下，好像在3.8之前的版本，这个函数是放在itertools里面的，不过现在调用math库即可，因为我们的官方环境是3.8.6

好吧，接下来就介绍一下这道题，我觉得吧，杨辉三角形最好的便是寻找规律，我们可以看到下图，是我做的一个笔记，我们需要看这个斜边，我们可以发现这个斜边实际上是有规律的，由于两边是堆成的，所以我们只需要看一边

我们会发现以上的规律，首先是单调递增的，其次，如果我们得到边的序号x，那我们的L=2x，比如我上面举的例子，第一条便就是2行，第二条边就是4行，第三条边就是6行，所以所有边的第开始的第一个序号就是我们

为了找到我们的数，我们就需要二分找到我们的[L，R]的区间，这里要注意的是，斜边上的数，都是出现的第一个数，换句话来说，就是第一次出现的数。

接着我们就需要确立第几个数了，首先我我们可以设

我们依旧可以找规律

所以总结就是，如果 ，那就就在( 1 + 2 + 3 + . . . + q ) + x + 1 = ( q + 1 ) ∗

然后我们所说的二分查找就是在不同的斜边来说，查找数，比如说第x条斜边中，我们查找q

代码

# https://www.lanqiao.cn/problems/1457/learning/
n = int(input())
import math
# 求组合数
def C(a, b):
    # return math.comb(a,b) # 可以调用数学库，直接计算
    res = 1
    i = a
    j = 1
    while j <= b:
        res = res * i // j # 分子是b的阶乘，b!
        if res > n: # 组合数是递增的，这时候已经比他大了，直接返回便可
            return res
        i -= 1
        j += 1
    return res
# 二分查找n，由于数字在1000w之内，所以确立一个上界为16
for k in range(16, -1, -1):
    l = 2 * k # 每一个斜边的上的数 L = 2*x
    r = max(n, l) 
    res = -1
    # 二分法寻找
    while l <= r:
        mid = l + r >> 1
        if C(mid, k) >= n: # 如果C(mid,k) >= n
            res = mid 
            r = mid - 1
        else:
            l = mid + 1
    if C(res, k) == n: # 这时候已经找到我们的行数res,和在第k个
        print((res + 1) * res // 2 + k + 1)
        break

试题 H:左孩子右兄弟

题目描述

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。

换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含 NN 个结点的多叉树，结点从 1 至 N编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。

请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。

注：只有根结点这一个结点的树高度为 0。

输入描述

输入的第一行包含一个整数 N。 以下 N −1 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。

输出描述

输出一个整数表示答案。

输入输出样例

示例 1

输入

5
1
1
1
2

输出

4

评测用例规模与约定

对于 30 % 的评测用例，1 ≤ N ≤ 20

对于所有评测用例，1 ≤ N ≤ 100000

思路

对于这道题来说，左孩子右兄弟，我们需要达到最深的二叉树，比较简单的来说，就是每次选择孩子更多的作为最后一个结点

比如对于这样一幅图，我们可以有以下的方法，我列出了其中的三种方法

我们可以看到，最深的就是最后一个，唯一的却别就是2有一个孩子5，所以深度就增加了

好了，简单理清思路我们就可以用我们的dfs了，首先我们可以从输入中创建邻接表，可以判断两个结点是否有联系。

每次的最大深度就是我们孩子数量，然后又加上孩子的孩子的数量，我们就用了深度优先搜索DFS，每次DFS孩子，取最大深度，最后从根，也就是1开始DFS，最后输出dp[1]就是我们的结果。

dp[u]：以点 u 为根节点，通过 “左孩子右兄弟” 表示法转化成二叉树后的最大高度；

dp[u] = 子节点数量 + 子树转化为二叉树后的最大高度

代码

# https://www.lanqiao.cn/problems/1451/learning/
import sys
# 树形DP
g = [[] for j in range(1, 100100)] # 邻接表
dp = [0] * 100100
# 设置递归深度
sys.setrecursionlimit(150000)
def dfs(u):
    dp[u] = len(g[u]) # 全部变为左孩子，那么长度就是孩子的数量
    maxv = 0
    for v in g[u]:
        dfs(v) # DFS孩子
        maxv = max(dp[v], maxv) # 取最大深度
    dp[u] += maxv # 每次加上最大深度
n = int(input())
for i in range(2, n + 1):
    v = int(input())
    g[v].append(i)
dfs(1)
print(dp[1])

试题 I:异或数列

题目描述

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 a 和 b，初始值均为 0。

有一个给定的长度为 n 的公共数列 X 1 , X 2 , ⋯   , X n 。Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：

选项 1：从数列中选一个 X i 给 Alice 的数异或上，或者说令 a 变为 a ⊕ X i 。（其中 ⊕表示按位异或）

选项 2：从数列中选一个 X i给 Bob 的数异或上，或者说令 b 变为 b ⊕ X i

每个数 X i 都只能用一次，当所有 X i均被使用后（n 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。 现在双方都足够聪明，都采用最优策略，请问谁能获胜？

输入描述

每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 T，表示询问数。

接下来 T 行每行包含一组询问。其中第 i 行的第一个整数 n i 表示数列长度，随后 n i 个整数 X 1 , X 2 , ⋯   , X n  表示数列中的每个数。

输出描述

输出 T行，依次对应每组询问的答案。 每行包含一个整数 1、0 或−1 分别表示 Alice 胜、平局或败。

输入输出样例

示例 1

输入

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

输出

1
0
1
1

评测用例规模与约定

对于所有评测用例

思路

这道题想了一会，首先来说对于每一个人，我们都有两种选择，既然足够聪明，就有两种想法，第一是让自己的数更大，第二就是让别人的数更小，所以对于先手来说，由于两个人都是0，所以会选择较大的数对自己异或

这里要记住两个异或的重要公式：a^a = 0, a ^ 0 = a

那我们判断一下，其实我们可以发现 a^b = X1^ X2 ^ X3… Xn，若a^b = 0，也就是说明我们的a=b,也就是平局的情况，所以会对所有数进行异或，如果sum=0，就说明是平局

其次就是sum！=0的情况，对于这种情况来说，我们就需要看最高位了，比如100的最高位是第3位为1，我们就要看最高位为one的个数了

例如我们有A,B,C三个最高位都为1的数，那我们对于我们先手来说，就会先把最大数的和自己异或，保证自己的数最大

之后可能1.后手用B与先手的a异或，使其的最高位为0，然后先手再拿C与自己的数异或，最高位还是1。2.或者是后手用B与自己数异或，使自己的数最高位为1，然后先手就会用C使其后手的数异或，让他变为1。我们会发现，这时候先手是一定赢的，因为他的最高位是1。

但是假设，我们还有最高位为0的数，如果多一个数，那么我们的后手就会把先手的最高位变成0，那么后手就赢了，如果有两个，那么先手就可以与自己的数异或，使自己的数的最高位还是1。

所以就可以总结一下

1.第一种情况：sum=0,说明Alice和Bob一定平手

2.第二种情况：sum!=0

计算出最大数的最大数位，假设是第i位，设这些数中有one个数在该为1，zero个数在该位为0

a.如果one是偶数，说明判断不出来，继续枚举下一位。

b.如果one是奇数，one只有一个，一定是Alice赢

one>1,zero是偶数，一定是Alice赢

one>1,zero是奇数，一定是Bob赢

代码

# https://www.lanqiao.cn/problems/1450/learning/
T = int(input())
for i in range(T):
    a,b = 0,0
    arr = list(map(int,input().split()))
    sum = 0
    ma = 0
    for x in arr[1:]:
        sum ^= x
        ma = max(ma,x) # 找出最大位的数
    if sum == 0: # a^b = X1^X2^X3...Xn=0
        print(0) # 平局
        continue
    x = 1
    while x < ma:
        x <<= 1 # 最高位
    if x > ma:
        x >>= 1
    while x > 0:
        one = 0
        zero = 0
        for i in arr[1:]:
            if i&x == 0: # x[i]的第i位是否为0
                zero += 1
            else:
                one += 1
        if one%2 == 1: # one为奇数
            if zero%2 == 1 and one > 1: # zero为奇数
                print(-1)
            else: # one 为1或者是zero为偶数
                print(1)
            break
        x >>= 1 # 对于x的第i位的one为偶数，则判断下一位

试题 J:括号序列

题目描述

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。

输入描述

输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。

输出描述

输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007

输入输出样例

示例 1

输入

((()

输出

5

评测用例规模与约定

对于 40% 的评测用例，

对于所有评测用例，

思路

这道题是最近做的，做的时候可苦死我们了，是真的难，到后面也只拿了50分，不过我是真卷不懂了

这道题首先要明白题目的一个定义，什么叫合法的括号序列

合法序列的定义：对于一段括号序列，从左往右起，一个字符一个字符的往前看，对于每一段小的括号序列“（” 数量 大于等于 “）” 数量，那么整个括号序列就合法。

所以我们要注意，我们可以左括号数大于我们的右括号数的，但是我们的右括号数不能大于我们的左括号数

明白了定义后，我们就看一下题目，首先我们需要添加我们的左括号和由括号，那我们的添加是不是相互独立的呢，答案当然是肯定的

考虑到我们只能在空隙中插入括号， 如果我们添加的一对左右括号不是在同一个空隙中， 那么他们显然是互不干扰的；如果是添加在同一个空隙中， 那么他们的添加顺序是唯一的， 只能是）（， 因为如果是（)的话， 那我们本次的添加就是无效的， 不满足添加最少的括号使得序列得到匹配。 由此可得， 我们只需要单独计算出添加左括号的方案数， 乘上单独添加右括号的方案数就是答案的数量。

明确了这一点之后，我们就可以分开讨论，我们可以判断在原括号序列添加左括号使之变得合法，然后变换原括号序列（先将括号序列逆序，再将左括号变成右括号，右括号变成左括号），这样调整之后我们在变换后的括号序列中添加左括号使之变得合法（相当于在原括号序列添加右括号）。

然后接着就是这道题的核心部分，这里面就定义了一个DP数组，dp[ i ] [ j ] [i ][j ][i][j]表示当前枚举到第i个右括号， 我们添加了j个左括号的合法方案，这里面会有一种情况，根据定义，就是如果我们添加的操作使得前i个右括号都被匹配完后还有剩余的左括号， 我们仍认为这个状态是合法的。也就是说，我们是不在意括号加多少个，我们在意的是左括号比右括号多多少个，并且j应该是一定大于0，因为我们枚举到第i个右括号，我们是一定存在右括号的，不可能是0种。

我们如果以右括号为端点， 将整个序列进行分割， 那么在分割后的每一小段添加左括号的方案数显然只和这段序列中左括号的数量有关， 因为这段序列里全是左括号， 怎么排列都是一种。所以我们只关注左括号的个数就好了， 更准确的来说， 我们只要关注我们添加的左括号的个数。

遇到左括号的时候，证明在这个左括号之前的括号序列已经被判断过如何使其合法了，那么加上这个左括号依然合法，所以我们不需要管这个左括号。也就是在他前面的括号序列添加左括号使其合法的种数等于加上这个左括号之后这个序列需要添加的左括号种数。ddp[i][j]=dp[i-1][j-1]

如果遇到我们的右括号，如果这个加上这个右括号的序列本身合法，那么我们仅需添加0个左括号就能使其合法，如果不合法就需要添加刚好使得其合法的左括号甚至可以更多。

简单解释一下要得到前i个字符的序列左括号比右括号多j个的合法情况，

前i-1个字符的序列左括号比右括号多0个（刚好合法）的情况，再在这个右括号前面加j+1个左括号得到

前i-1个字符的序列左括号比右括号多1个的情况，再在这个右括号前面加j个左括号得到

…

前i-1个字符的序列左括号比右括号多j+1个的情况，再在这个右括号前面加0个左括号得到

可是这样会超时，所以这里就把三维压缩成二维，我们会发现，d p [ i ] [ j − 1 ] = d p [ i − 1 ] [ 0 ] + d p [ i − 1 ] [ 1 ] + … d p [ i − 1 ] [ j ] ，那么这样的话，我们就可以得到

代码

# https://www.lanqiao.cn/problems/1456/learning/
#括号序列
MOD = (int)(1e9 + 7)
def works():
    dp = [[0]*5000 for _ in range(5000)]
    dp[0][0] = 1 # 初始化
    for i in range(1, n + 1): # 一个括号一个括号进行判断
        if str[i] == '(': # 遇到左括号
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][0] = add(dp[i - 1][0], dp[i - 1][1])
            # dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + ...... + dp[i - 1][j]
            # dp[i][j + 1] = dp[i - 1][0] + dp[i - 1][1] + ...... + dp[i - 1][j] + dp[i - 1][j + 1]
            for j in range(1, n + 1):# 最多加n个括号
                dp[i][j] = add(dp[i - 1][j + 1], dp[i][j - 1])
    for i in range(n + 1):
        if dp[n][i]:
            return dp[n][i]# 我们需要的就是长度为len添加括号的合法情况，而从前往后遍历出现的第一个有可能的情况就是需要括号数最少的情况，因为左括号可以加很多个，我们仅需添加最少的情况
def add(x, y):  
    return (x + y) % MOD
str = list(input())
n = len(str)
str.insert(0, 0)  #使目标字符串下标从1开始
ans_l = works()
str.reverse()
for i in range(n):
    if str[i] == '(':
        str[i] = ')'
    else:
        str[i] = '('
str.insert(0, 0)  #使目标字符串下标从 1 开始
ans_r = works()
print(ans_l * ans_r % MOD)