单选题

多选题

编程题1： 小红的01连续段

题目描述
小红定义一个01串的“连续段”为：连续相同字符的极大长度。例如：“110001111”有一个长度为2的连续段，有一个长度为3的连续段，有一个长度为4的连续段。
小红拿到了一个01串，但其中有一些字符部件了（用‘？’表示）。小红想知道，这些01串的连续段长度的最大值最多能达到多少？
输入描述

一个仅由‘0’、‘1’、‘？’组成的字符串，长度不超过200000。

输出描述

一个正整数，代表连续段长度的最大长度。

示例1
输入

1?0?1?

输出

3

代码
考试的时候太蠢了，竟然只想到了dfs爆搜

from webbrowser import gets = input()
max_len1 = 0
max_len2 = 0ans = 0
for ch in s:if ch=='0':max_len1 += 1max_len2 = 0elif ch=='1':max_len1 = 0max_len2 += 1else:max_len1 += 1max_len2 += 1ans = max(ans, max_len1, max_len2)print(ans)

编程题2： 月考成绩

题目描述
月考结束了，每个同学都拿到了自己的成绩单。共有语文、数学、英语三门科目。
对于一个同学而言，如果存在某个同学的总分比他高，但某个单科比他低，那么这个同学就会有优越感。
请问总共有多少同学会产生优越感？
输入描述

第一行输入一个正整数n，代表同学的数量。
接下来n行，每行输入三个整数a b c，代表每个同学语文、数学、英语的分数。
$1<=n<=10^5$
$0<=a,b,c<=100$

输出描述

一个整数，代表产生优越感的同学数量。

示例1
输入

4
100 20 10
100 50 30
20 20 20
60 60 60

输出

2

说明

第三个同学会产生优越感，因为第一个同学的总分比他高，但英语的分比他低。
第一个同学会产生优越感，因为第四个同学的总分比他高，但是语文分比他低。

代码
考试的时候没想起来$O(nlogn)+O(n)$的算法，只想到了$O(nlogn)+O(n^2)$

n = int(input())data = []
for _ in range(n):a, b, c = map(int, input().split())data.append((a+b+c, a, b, c))data.sort(key=lambda x: (x[0], x[1], x[2], x[3]))mina, minb, minc = float('inf'), float('inf'), float('inf')
ta, tb, tc = float('inf'), float('inf'), float('inf')
ans = 0
for i in range(n-1, -1, -1):total, a, b, c = data[i]if (a>mina and total<ta) or (b>minb and total<tb) or (c>minc and total<tc):ans += 1if a<mina:mina = ata = totalif b<minb:minb = btb = totalif c<minc:minc = ctc = total
print(ans)

编程题3：小红的红蓝硬币

题目描述
小红的n个硬币，其中一些硬币为红色，另外一些为蓝色。每个硬币有一个面值（保证所有硬币的面值不同）。
小红想选择一些硬币凑出总面值为p，且至少有一个红硬币和至少一个蓝硬币，你能求出选择的方案数吗？答案对$10^9+7$取模。
提示：建议python考生使用pypy提交。
**输入描述: **

第一行输入两个正整数n和p，用空格隔开。
第二行输入一个仅包含’R’和’B’的字符串，第i个字符为’R’代表第i个硬币为红色，'B’代表蓝色。
第三行输入n个正整数a，代表每个硬币的面值。
$1<=n,a_i<=1000$
$1<=p<=10000$

输出描述

一个正整数，代表方案数对$10^9+7$取模的值。

示例1
输入

5 10
BBRRR
1 2 3 6 8

输出

2

说明

1（蓝色）+3（红色）+6（红色）
2（蓝色）+8（红色）

代码
之前过了90%，才发现少了 %MOD

import functools
from lzma import MODE_FAST
n, p = map(int, input().split())
s = input()
vals = list(map(int, input().split()))MOD = 10**9+7
@functools.lru_cache(None)
def dfs(cnt, i, f1, f2):if cnt>p:return 0if cnt==p and f1 and f2:return 1if i>=n:return 0ans = 0ans += dfs(cnt, i+1, f1, f2)ans %= MODif s[i]=='B':ans += dfs(cnt+vals[i], i+1, True, f2)else:ans += dfs(cnt+vals[i], i+1, f1, True)ans %= MOD # 这里之前忘记MOD了return ans print(dfs(0, 0, False, False))