8 月 1 日笔试-Python 版

目录

1. 第一题
2. 第二题
3. 第三题 HTML 模板解析（没做出来）

第一题

小袁报了 N 个课程，每个课程有开始时间和结束时间。但是有一些重复的课程，求小袁最多需要同时听多少门课。

样例：

4
1 4
1 2
2 3
3 4

样例输出： 2

AC 代码：

n = int(input())
s = []
e = []

for i in range(n):
    a, b = map(int, input().split(' '))
    s.append(a)
    e.append(b)
s.sort()
e.sort()
c = 0
m = 0
ii = 0
jj = 0
while ii < n and jj < n:
    if jj != n and (ii == n or e[jj] <= s[ii]):
        #print('end', e[jj])
        jj += 1
        c -= 1
    else:
        #print('start', s[ii])
        ii += 1
        c += 1
        m = max(m, c)
print(m)

第二题

有 N 个同学，需要给没人分发一张奖券。一个人先拿着所有奖券，留下一张，然后剩余的分个其他人，其他人继续用同样的方法分，直到每人都有一张。

开奖时，每个奖券获得一个整数值（可以是负数），每个人可以选择自己的奖券值作为奖励，也可以额外选择全部或部分他发送出去的奖券，但是如果不选某个奖券，则也无法选择后续的奖券。例如，A 的开始有 1，2，3，4 四张。给了 B 奖券2，3，4，B 又把 3 给了 C， 4 给了 D。则 A 可以选：

1
1，2
1，2，3
1，2，3
1，2，3，4

但不能选如 1， 4

题目分析：

所有人构成一颗树，第一个发的人是树根。使用后序遍历遍历一次就可以得到答案。策略是叶子节点的值只能是自身，其他节点的值是自身加所有非负的孩子。

Python 需要注意的地方：如果书高度很高，会超递归限制，可以模拟递归或者使用 sys.setrecursionlimit 设置递归深度。第二 Python 整数不会溢出，其他语言可能需要考虑递归过程中的溢出问题。

代码：

import sys
sys.setrecursionlimit(1000000)
mod = 1000000003

n = int(input())
ch = [[] for i in range(n)]
v = [0] * n
root = -1
for i in range(n):
    a, b = map(int, input().split(' '))
    v[i] = a
    if b != 0:
        ch[b-2].append(i)
    else:
        root = i
ans = v[root]
# print(ch)
# print(v)
def vis(i):
    global ans
    x = v[i]
    for child in ch[i]:
        r = vis(child)
        if r > 0:
            x += r
    ans = max(x, ans)
    return x
vis(root)

print(ans % mod)

第三题 HTML 模板解析（没做出来）

给出一个 JSON 对象，一段 HTML 模板代码，要求返回渲染后的 HTML。

语法类似于 vue：

1. {{}} 内的值替换为 JSON 对象中的值
2. y-if 如果为 false 或者 undefined 则删除该 DOM 元素（含子元素）
3. y-for 列表渲染

样例

{
"isMain": false,
"list": []
}

<div class="head">
<button y-if="{{isMain}}">首页</button>
</div>
<ul class="content">
<!– 卡片区域 –>
<li class="card isMain" y-for="lesson, index in list">
<div class="card-title">
<i y-if="{{lesson.label}}">{{lesson.label.type}}</i>
{{lesson.title}}
</div>
班课<span class="bold">-</span>老师：{{lesson.teacher}}
<div class="lesson-time">{{lesson.time}}<i class="tt"></i></div>
</li>
</ul>
end

这题没时间做了，感觉很麻烦。