代码收藏家 牛客周赛Round 80 —— 举手赢棋 python 补题 + 题解
文章目录
前言
紧跟时事的两道算法题
牛客周赛 Round 80
举手赢棋easy
题目描述
本题为《举手赢棋hard》的简单版本，两题的唯一区别在于对举手次数的限制不同，在本题中，小红有1次举手的机会。
小红获得了参加鹿瓜杯的资格，在赛前，她预测了接下来的几场比赛，使用一个仅由‘0’和‘1’构成的字符串s表示。其中，Si=‘0’代表第i场比赛会失利，Si=‘1’代表第i场比赛会胜利。
为了胜利，小红希望任意时刻自己的胜场不低于负场。因此，小红有1次通过"举手"强行获得一场比赛胜利的机会（即将字符串的任意一位修改为‘1’）。
请你帮小红计算有多少种安排这1次举手的方案。
一个合法的方案需要满足：恰好有1局是举手的，且任意时刻胜场数量不小于负场数量。
请注意，小红在预测胜场的局也可以选择举手。
输入描述：
第一行输入一个正整数n(2≤n≤1e5)代表比赛场数。
第二行输入一个长度为n、仅由‘0’和‘1’构成的字符串s。其中，Si=‘0’代表在不举手的情况下，第i场比赛会失利，Si=‘1’代表在不举手的情况下，第i场比赛会胜利。
输出描述：
输出一个整数，代表有多少种安排这1次举手的方案。
示例1
输入：
7
0100000
输出：
0
解释：
在这个样例中，无论小红怎么举手，都无法挽回口碑。因为即使在最开始举手，也无法避免后续的负场超过胜场。
示例2
输入：
5
10110
输出：
5
解释：
在这个样例中，任意选择一场举手均可。因为在任意一场比赛举手都不会导致负场超过胜场。
示例3
输入：
5
01110
输出：
1
思路分析
- 问题建模
n的字符串s，由’0’和’1’组成，表示比赛结果。- 前缀和的概念
我们可以使用前缀和来跟踪当前的胜负情况：
pre_sum[i]表示从第1场到第i场比赛的累计得分（即胜场减去负场的数量）。如果在某一点i，前缀和pre_sum[i]小于0，则意味着在这一点上负场超过了胜场，需要通过举手来调整。
- 关键点分析
n。具体步骤
-
初始化前缀和：
pre_sum[i]：记录从第1场到第i场比赛的累计得分。-
判断是否无需举手：
- 如果所有前缀和都非负，说明不需要任何举手操作即可满足条件，输出所有可能的举手位置数，即
n。 -
判断是否无法满足条件：
- 如果最小前缀和小于-2，说明无论如何举手都无法使胜场数量始终不低于负场数量，直接输出0。
-
寻找需要举手的位置：
- 找到第一个前缀和小于0的位置
pos。 -
计算合法方案数：
- 遍历前
pos个位置，如果在这些位置上是失败（即a[i] == -1），则举手可以使得前缀和变为非负，从而增加一种合法的方案数。
code实现与注释
n = int(input())
s = input()
# 将字符串s转换为列表a，其中胜利记为1，失败记为-1
a = [int(x) if x == '1' else -1 for x in s]
# 初始化前缀和数组pre_sum
pre_sum = [0] * (n + 1)
for i in range(1, n + 1):
pre_sum[i] = pre_sum[i - 1] + a[i - 1]
# 如果所有前缀和都非负，说明不需要任何举手操作即可满足条件
if min(pre_sum[1:]) >= 0:
print(n)
# 如果最小前缀和小于-2，说明无论如何举手都无法使胜场数量始终不低于负场数量
elif min(pre_sum[1:]) < -2:
print(0)
else:
ans = 0
pos = -1 # 记录需要第一次举手的位置
# 找到第一个前缀和小于0的位置pos
for i in range(1, n + 1):
if pre_sum[i] < 0:
pos = i
break
for i in range(pos):
if a[i] == -1:
ans += 1 # 在这些位置举手可以使前缀和变为非负
print(ans)
举手赢棋hard
题目描述
本题为《举手赢棋easy》的困难版本，两题的唯一区别在于对举手次数的限制不同，在本题中，小红有2次举手的机会。
小红获得了参加鹿瓜杯的资格，在赛前，她预测了接下来的n场比赛，使用一个仅由‘0’和‘1’构成的字符串s表示。其中，si=‘0’代表第i场比赛会失利，Si=‘1’代表第i场比赛会胜利.
为了胜利，小红希望任意时刻自己的胜场不低于负场。因此，小红有2次通过“举手”强行获得一场比赛胜利的机会（即将字符串的任意一位修改为‘1’）。
请你帮小红计算有多少种安排这2次举手的方案。
一个合法的方案需要满足：恰好有2局是举手的，且任意时刻胜场数量不小于负场数量。
请注意，小红在预测胜场的局也可以选择举手。
输入描述：
第一行输入一个正整数n(2≤n≤1e5)代表比赛场数。
第二行输入一个长度为n、仅由‘0’和‘1’构成的字符串S。其中，Si=‘0’代表在不举手的情况下，第i场比赛会失利，Si=‘1’代表在不举手的情况下，第i场比赛会胜利。
输出描述：
输出一个整数，代表有多少种安排这2次举手的方案。
示例1
输入：
7
0100000
输出：
0
解释：
在这个样例中，无论小红怎么举手，都无法挽回口碑。
示例2
输入：
5
10110
输出：
10
解释：
在这个样例中，任意选择两场举手均可。
示例3
输入：
5
01000
输出：
3
说明
在这个样例中，有以下三种可行的方案：
这道题的题目要求是在给定的比赛序列中，通过最多两次“举手”（即将某个’0’变为’1’）使得任意时刻胜场数量不低于负场数量。我们需要计算所有可能的合法方案数。
思路分析
1. 问题建模
n的字符串s，由’0’和’1’组成，表示比赛结果。- 前缀和的概念
我们可以使用前缀和来跟踪当前的胜负情况：
pre_sum[i]表示从第1场到第i场比赛的累计得分。如果在某一点i，前缀和pre_sum[i]小于0，则意味着在这一点上负场超过了胜场，需要通过举手来调整。
- 关键点分析
C(n, 2)。具体步骤
-
初始化前缀和和失败次数：
pre_sum[i]：记录从第1场到第i场比赛的累计得分。cnt0[i]：记录前缀中’0’的个数。-
判断是否无需举手：
- 如果所有前缀和都非负，说明不需要任何举手操作即可满足条件，输出所有可能的组合数
C(n, 2)。 -
判断是否无法满足条件：
- 如果最小前缀和小于-4，说明无论如何举手都无法使胜场数量始终不低于负场数量，直接输出0。
-
寻找需要举手的位置：
- 找到第一个前缀和小于0的位置
pos1。 - 找到第一个前缀和小于-2的位置
pos2。 -
计算合法方案数：
- 如果只需要一次举手即可满足条件，则第二次举手可以任意选择。
- 如果需要两次举手，则根据前缀和的变化情况计算符合条件的方案数。
题解code：
n = int(input())
s = input()
# 将字符串s转换为一个列表a，其中胜利记为1，失败记为-1
a = [int(x) if x == '1' else -1 for x in s]
pre_sum = [0] * (n + 1) # 前缀和数组，记录从第0场到当前场次的累计得分
cnt0 = [0] * (n + 1) # 记录前缀中失败（'0'）的个数
for i in range(1, n + 1):
cnt0[i] = cnt0[i - 1] + (a[i - 1] == -1) # 更新失败次数
pre_sum[i] = pre_sum[i - 1] + a[i - 1] # 更新前缀和
# 如果所有前缀和都非负，说明不需要任何举手操作即可满足条件
if min(pre_sum[1:]) >= 0:
print(n * (n - 1) // 2) # 输出所有可能的组合数C(n, 2)
# 如果最小前缀和小于-4，说明无论如何举手（两次）都无法使胜场数量始终不低于负场数量
elif min(pre_sum[1:]) < -4:
print(0)
else:
ans = 0
pos1, pos2 = -1, -1 # 记录需要第一次和第二次举手的位置
# 找到第一个前缀和小于0的位置pos1
for i in range(1, n + 1):
if pre_sum[i] < 0:
pos1 = i
break
# 找到第一个前缀和小于-2的位置pos2
for i in range(pos1, n + 1):
if pre_sum[i] < -2:
pos2 = i
break
# 如果只需要一次举手即可满足条件，则第二次举手可以任意选择
if pos2 == -1:
for i in range(pos1):
if a[i] == -1:
ans += n - i + i - cnt0[i + 1]
else: # 需要两次举手
for i in range(pos1):
if a[i] == -1:
ans += cnt0[pos2] - cnt0[i + 1] # 第二次举手在【i，pos2】
print(ans)
END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢
作者：查理零世
