目录
! 要求语言必须是： C/C++/Python
题目A 流量计费
题目描述
某运营商手机流量的收费规则是:每月要收取基本费用10元，提供500GB的免费流量，对于超出的流量部分则按1元/GB收费。现在给出用户john当月的流量清单，你能帮他算出应该交纳的费用吗?
输入
输入数据有若干组。第一行为整数T(1≤T≤10)表示数据的组数，接着依次输入T组数据。对于每组数据，第一行为整数m(1≤m≤10)表示数据内包含的流量记录条数，接下来输入m行，每行包含一个整数si(1≤si≤1000)表示使用的流量数。
输出
对于每组清单输出一行指出应缴纳的费用。
样例输入
2
2
100
300
3
100
400
20
样例输出
10
30
题目B 买水果
题目描述
宿舍楼下的水果滩正在搞促销活动，每买一个大小为A(1 ≤A≤100000)的苹果，就免费赠送一个大小为B(1≤B<A)的橘子(送完为止，先到先得)。」ohn最喜欢吃楼子，但不幸的是，橘子只能通过赠送的方式获得，不可以直接购买。水果摊上现有N(1≤N≤10)个苹果和M(1≤M≤1000)个橘子，给出每个苹果和橘子的大小，请帮助John算出他最多可以得到多少个橘子?
输入
第一行输入一个整数T(1≤T≤10)表示包含的数据组数。
接下来依次输入每组数据，对于每组数据第1行:2个整数，分别为N和M，中间用空格隔开。
第2至N+1行:每行给出一个整数，表示苹果的大小。
第N+2至N+M+1行:每行给出一个整数，表示橘子的大小。
输出
对于每组数据输出一行，指出John最多可以得到的橘子数。
样例输入
2
3 3
4
5
6
3
4
5
3 3
1
8
7
8
6
1
样例输出
3
2
题目C 星期几
题目描述
给出日期，计算出星期几？
输入
第一行包含一个整数T(1≤T≤20)表示包含的数据组数。每组数据只有一行，以年月日形式给出日期，格式为"0xX-X0X-XX"。所有给出的日期都是合法的，并且都不会早于1900-01-01。
输出
对于每组教据输出一行指出当前日期是周几(周日:sunday,周一:Monday,周二:Tuesday,周三:Wednesday,周四:Thursday,周五:friday,周六:Saturday)
样例输入
2
1900-01-01
2008-12-07
样例输出
Monday
Sunday
提示
1.1900年1月1日是星期一
2.4,6,11和9月有30天。其他月份除了2月有31天。闰年2月有29天,平年2月有28天。
3.年份可以被4整除的为闰年(1992=4*498 所以 1992年是闰年,但是1990年不是闰年)。
4.规则3不适合于世纪年。可以被400整除的世纪年为闰年,否则为平年,所以,1700,1800,1900和2100年是平年,而2000年是闰年
题目D 完美子序列
题目描述
给出一个长度为N(1≤N≤50000)的数字队列，定义完美区间为数字队列中连续的一段，并且其中最大与最小数字之差不得超过M(1≤M<50000)
输入
第一行包含一个整数(1≤T≤50)表示包含的数据组数。对于每组数据第1行:包含N和M两个整数，中间用空格隔开。第2行:给出N个整数的数字队列，且所有的整数都在1到1000000之间。
输出
对于每组数据输出一行，指出最长完美区间的长度。
样例输入
2
9 10
19 18 16 18 6 6 11 13 14
5 8
17 19 13 18 14
样例输出
5
5
提示
共有2组数据，第一组中的最长完美区间为66111314，第二组最长完美区间为17 19 131814。
题目E 最长子串
题目描述
给一个只包含小写字母且长度不超过100000的字符串，找出每个字母恰好出现两次的最长子忠
输入
第一行是一个正整数T，表示数据组数。每组数据包括一行，包含一个字符串
输出
对每组数据，输出符合要求的最长子串的长度。
样例输入
2
abbccdde
abcdefg样例输出
6
0
A
t = int(input())
while(t):
t-=1
m = int(input())# 流量记录条数
liu = []
for i in range(m):
liu.append(int(input()))
# 计费
liuliang = sum(liu)
if liuliang <= 500:
fee = 10
else:
fee = 10 + (liuliang - 500)
print(fee)B
暴力破解：时间复杂度 O(nlogn + mlogm + n*m) 小数据集可以过
def orangenum(apple, orange,n ,m):
res = 0
apple.sort(reverse=True)
orange.sort(reverse=True)
for i in range(n):
if i < m:
for j in range(i, m):
if apple[i] > orange[j]:
res += 1
break
return res
t = int(input())
while(t):
t-=1
n, m = map(int, input().split()) # 苹果个数 句子个数
apple = []
for i in range(n):
apple.append(int(input()))
orange = []
for i in range(m):
orange.append(int(input()))
print(orangenum(apple,orange,n,m))采用双指针即可，时间复杂度O(nlogn + mlogn + n + m)
C语言双指针更快一些
def max_oranges(N, M, apples, oranges):
apples.sort() # 将苹果按照大小排序
oranges.sort() # 将橘子按照大小排序
i, j = 0, 0 # i用于遍历苹果，j用于遍历橘子
count = 0
while i < N and j < M:
if oranges[j] < apples[i]: # 如果橘子的大小小于当前苹果的大小
count += 1 # 匹配成功
j += 1 # 移动到下一个橘子
i += 1 # 移动到下一个苹果
return count
T = int(input()) # 读取测试用例数量
results = []
for _ in range(T):
N, M = map(int, input().split())
apples = [int(input()) for _ in range(N)]
oranges = [int(input()) for _ in range(M)]
result = max_oranges(N, M, apples, oranges)
results.append(result)
for result in results:
print(result)
C
做这个题的时候最后想到了，python有一个日历库calendar ，利用其函数输入年月日可以自动转换为对应的星期几，但是输出的是星期几的索引，0-6 对应 Monday-Sunday,java也有类似库。时间复杂度O(T)
import calendar
def pro(date):
date = date.split('-')
date = calendar.weekday(int(date[0]), int(date[1]), int(date[2]))
week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
res = week[date]
return res
t = int(input())
while(t):
t-=1
date = input()
print(pro(date))当然也可以根据提示去计算，首先计算输入日期与基准日期之间的天数差值，差值除以7就可以确定星期几了。时间复杂度O(T*Y) Y是年份跨度，Y越大消耗时间越多，这两种方法应该都可以最终通过全部数据集。调用calendar更快。
def is_leap_year(year):
if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
return True
return False
def days_in_year(year):
return 366 if is_leap_year(year) else 365
def days_in_month(year, month):
days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
if month == 2 and is_leap_year(year):
return 29
return days_in_month[month - 1]
def days_from_1900(year, month, day):
total_days = 0
for y in range(1900, year):
total_days += days_in_year(y)
for m in range(1, month):
total_days += days_in_month(year, m)
total_days += day - 1
return total_days
def day_of_week(year, month, day):
days = days_from_1900(year, month, day)
week_days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
return week_days[days % 7]
T = int(input())
for _ in range(T):
date = input().strip()
year, month, day = map(int, date.split('-'))
print(day_of_week(year, month, day))
D
爆破：时间复杂度O(n**2) 最坏的时间复杂度O(n**3)
def pro(data , n, m):
res = 0
for i in range(n):
for j in range(i,n):
if abs(max(data[i:j+1])-min(data[i:j+1])) > m:
res = max(res,j-i+1)
break
else:
res = max(res,j-i+1)
return res
t = int(input())
while(t):
t-=1
n,m = map(int,input().split())
data = list(map(int,input().split()))
print(pro(data,n,m))可以选择滑动窗口或者双端队列，下面是滑动窗口，时间复杂度是O(n)
def longest_perfect_subsequence(N, M, arr):
i = 0 # 左边界
max_length = 0 # 最长完美区间的长度
for j in range(N): # 右边界
while max(arr[i:j+1]) - min(arr[i:j+1]) > M:
i += 1
max_length = max(max_length, j - i + 1)
return max_length
T = int(input()) # 读取数据组数
results = []
for _ in range(T):
N, M = map(int, input().split()) # 读取N和M
arr = list(map(int, input().split())) # 读取数字队列
result = longest_perfect_subsequence(N, M, arr)
results.append(result)
for result in results:
print(result)
E
滑动窗口 + hashtable
from collections import defaultdict
def longest_substring_with_pairs(s):
n = len(s)
max_length = 0
i = 0
count = defaultdict(int)
for j in range(n):
# 增加右边界字符的计数
count[s[j]] += 1
# 确保当前窗口中的每个字符都恰好出现两次
while any(c != 0 and c != 2 for c in count.values()):
count[s[i]] -= 1
i += 1
# 如果窗口中所有字符的出现次数都恰好为2，更新最大长度
if all(c == 0 or c == 2 for c in count.values()):
max_length = max(max_length, j - i + 1)
return max_length
t = int(input())
results = []
for _ in range(t):
s = input().strip()
result = longest_substring_with_pairs(s)
results.append(result)
for result in results:
print(result)
爆破
import collections
def pro(s):
res = 0
counts = collections.Counter(s)
count = 0
for i in counts.values():
if counts[i] == 1:
count+=1
if count == len(s):
return res
num = 0
for i in range(len(s)-1):
if counts.get(s[i]) == 1:
continue
else:
if s[i] == s[i+1] and counts.get(s[i]) >= 2:
num += 2
if i > 1 and i < len(s) - 1 and s[i] != s[i+1] and s[i] != s[i - 1]:
num = 0
res = max(res,num)
return res
t = int(input())
while(t):
t-=1
s = input()
print(pro(s))