123 周赛

第二题一直超时……

合格数

我的思路分为两步：

1. 先获取有效的区间
2. 然后判断问题区间中有多少个数在有效区间之内

第二步的复杂度不高，但第一步的复杂度太高。

看了别人的做法，发现它们的思路都是：通过查分数组和前缀和，计算出某个位置上的合格数的数量。

n, k, q = map(int, input().split())

diffArr = [0] * 200005

for _ in range(n):
    l, r = map(int, input().split())
    diffArr[l] += 1
    diffArr[r + 1] -= 1

# validNum[i] 表示 [0...i) 范围上的“合格数”数量
validNum = [0]
prefixSum = 0
for diff in diffArr:
    prefixSum += diff
    if prefixSum >= k:
        validNum.append(validNum[-1] + 1)
    else:
        validNum.append(validNum[-1])

for i in range(q):
    a, b = map(int, input().split())
    print(validNum[b + 1] - validNum[a])

py 缩进

没时间做，这里就直接看题解了：

• 当前行的语句是 for 时，下一行的缩进必须加 1
• 当前行的语句不是 for 时，下一行的缩进可以是任意值，但不能超过当前行缩进

或：

• 上一行是 for 时，当前行缩进必须加 1。此时当前行的缩进可能性等于上一行的缩进可能性
• 上一行不是 for 时，当前行缩进可以是任意值，但不能超过上一行缩进。

n = int(input())

linePossibleNum = 1
dp = [0] * (n + 1)
dp[1] = 1 # 第一行只有一种可能
for _ in range(n):
    curStatement = input()
    if curStatement == 'f':
        linePossibleNum += 1
    else:
        for j in range(1, linePossibleNum+1):
            dp[j] += dp[j - 1]

print(dp[linePossibleNum] % (10**9+7))