前言

难度适中，至少150不是很难。

第一题偏打卡。

第二题贪心+动态规划，但是藏的比较浅。

第三题是比较麻烦的模拟，注定满分不是那么好拿的。

计算最少流控请求数

服务器性能有限，对于突发请求，有时需要通过流控保护系统不受冲击。假设某服务器的系统要求任意M分钟内只能处理N条请求，超出的请求必须流控掉。已知连续X分钟,每分钟的实际请求数，请给出至少流控掉多少请求才能保证上述系统不受冲击。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms 内存限制: C/C++ 256MB,其他语言:512MB

输入

第一行: M和N M范围[1,10] N的范围[0.10000]

第二行: 连续分钟数X，X范围为[1,100000]

第三行:每分钟的请求数范围[0,1000]

输出

最少可以流控的请求数

样例1

输入:4 6
    6
    2 1 2 2 3 2
输出:3
解释:输入:
第一行系统要求:每4分钟只能接受6个请求。第二行:连续6分钟
第三行:每分钟的实际请求数。
至少流控3个请求 (可以是: 第4分钟流控1个请求，第5分钟流控1个请求，第6分钟流控1个请求》，才可以满足系统4分钟内只能处理6条请求的要求

思路与代码

滑动窗口。

使用长度为M的滑动窗口进行模拟即可。

M,N = map(int, input().split())
X = int(input())
requests = [int(c) for c in input().split()]

r = M
res = 0
while(r<=X):
    window = requests[r-M:r]
    total_requests = sum(window)
    if total_requests>N:
        to_remove = total_requests - N
        res += to_remove
        for i in range(r-1, r-M-1, -1):
            if to_remove>requests[i]:
               to_remove -= requests[i]
               requests[i] = 0
            else:
               requests[i] = requests[i] - to_remove
               break
    r += 1
print(res)

快乐时间

小明在工作之余喜欢在电子书城阅读不同的书籍并且获得最大的满足感，因此根据书城针对每本书籍的评分收集了n个书籍的打分清单books，例如第一本书的打分books[0]=5代表该书的满意程度为5，第二本书books[1]=-2代表该书的满意程度为-2.

阅读每本书花费的都是1单位时间，time定义为阅读本书及之前所有书的时间之和。因此第一本阅读的书籍time[0]=1，第二本阅读的书籍time[1]=2，第三本阅读的书籍time[2]=3并以此类推。

每本书籍的[快乐时间]系数为阅读该书籍和之前每本书籍所花费的时间乘以对这本书籍的满意程度，即time[i]*books[i]，其中i从0开始。

小明想了解自己如何安排阅读计划才能获得最大的快乐时间，请帮忙计算一下阅读给定书籍[快乐时间]总和最大的值是多少，可以按照任意顺序调整阅读书籍顺序(即每本书对应的time[i]是可以对调的)，也可以放弃阅读某些书籍。

解答要求

时国限制:C/C++ 1000ms其他语言: 2000ms 内存限制:C/C++ 256MB其他语言: 512MB

输入

输入为字符串，字符串内容为代表每本书籍的喜爱指数

输出

输出为数字，代表最大的快乐时间。

样例1

输入: 4,3,2
输出: 20
解释:按照原来顺序相反的时间阅读书籍(2*1+32+43=20)，评分越高的书籍越后面阅读可以获得最大的快乐时间

思路与代码

动态规划。

这里使用记忆化搜索的思路进行实现。f[i,j]表示从第i天开始往后考虑，当前看第j本书可以获取的最大开心值。每一天都有看和不看两种选择，即可枚举出所有的可能。时间复杂度为O(n^2)

from functools import cache

books = [int(c) for c in input().split(",")]
books.sort()

@cache
def dfs(i,p):
    if i >= len(books): return 0
    return max(dfs(i+1,p), dfs(i+1,p+1) + books[i] * p)

print(dfs(0,1))

稀疏存储

在虚拟化技术、芯片仿真器等领域，存在一种场景，即实际读写的数据量比较小，但要求可访问的地址空间却很大(要求4GB、甚至128GB地址空间)。

实现一个地址范围为32G的，可在该地址范围内任意位置读写数据的虚拟化 内存机制(数据默认清零)

对应功能: 1.读取任意地址数据: 2.往任意地址写入任意数据 3.清空数据，并释放内存

输入格式: Command Address Length Data

解释: 1、Command为Read、Write、 Clear之一 2、Address采用64位无符号十六进制数，全大写 3、Length采用64位无符号十进制数，单位为“字节”; 4、Data采用字节流(2个16进制数表示一个Byte) ，全大写;5、如果指定的Length大于实际给定的Data，需要程序自行末尾补0，小于则 末尾截断

解答要求：

时间限制: C/C++ 1000ms其他语言: 2000ms内存限制: /C++ 32MB.其他语言: 64MB

输入

每条指今一行，一个用例输入可以是多条指令混合，只有Read指令有输出。每个用例保证指令、参数格式正确，但不保证参数范围，需要程序按照题目规格要求自行校验，参数不合法，则对应的指令无效。

每个用例保证需要存储的总数据量最大不超过16MB，一个用例最多不超过500条指令。

例如(3表示有3条指令)
3
Write 0x100 7 001122AA
Read 0x100 4
Clear

输出

采用字节流(2个16进制数表示一个Byte)，全大写
例如
001122AA
每条Read指令对应一行输出数据，如果指令给的参数不合法，对应的输出为空(不换行)

思路与代码

大模拟题。【以下代码可能有纰漏的样例】

总体思想使用哈希表进行模拟每一个地址存储的值。

from collections import defaultdict

n = int(input())

address_map = defaultdict(lambda: "0")
mx = 32 * 1024 * 1024 * 1024
for _ in range(n):
    instruction = input().split(" ")
    if instruction[0] == "Read":
        address, length = instruction[1], int(instruction[2])
        address = int(address, 16)
        if address + length * 2 * 8 >= mx - 1: continue
        for i in range(2 * length):
            print(address_map[address + i * 8], end="")
        print()

    elif instruction[0] == "Write":
        address, length, data = instruction[1], int(instruction[2]) , instruction[3]
        address = int(address, 16)
        if address + length * 2 * 8 >= mx - 1: continue
        for i in range(2 * length):
            if i < len(data):
                address_map[address + i * 8] = data[i]
    else:
        address_map = defaultdict(lambda: "0")