猿辅导 笔试 2020.08.01 python
猿辅导 笔试 2020.08.01
第一题：
大意是给出每堂课的开始和结束时间，课程之间可能有冲突，有特异功能，上全部课最少需要一心几用。
输入N表示N节课，接下来输入N行每行输入课程的开始时间和结束时间
最直接想到用hash表，遍历记下每个时刻的课程数，求最大值。肯定超时啦~~
也可以如以下做法，区间计数的套路，当场没调完。应该可以全a。
import sys
if __name__ == "__main__":
# 读取第一行的n
n = int(sys.stdin.readline().strip())
d={}
for i in range(n):
# 读取每一行
line = sys.stdin.readline().strip()
# 把每一行的数字分隔后转化成int列表
value = list(map(int, line.split()))
s,e=value
if d.get(s)!=None:
d[s]+=1
else:
d[s]=1
if d.get(e)!=None:
d[e]-=1
else:
d[e]=-1
cnt,res=0,0
for key in sorted(d):
cnt+=d[key]
res=max(res,cnt)
print(res)
第二题：
分发奖品（值有正有负），最大收益
用到dfs
一个人自己只能留一个奖品，剩下的给别人，一层一层分发下去
每个人只能计算自己的奖券(必须要算)，以及从自己这里分出去的奖券的收益（可以选择部分）。如果要计算间接从自己这里分出去的收益，则经由中间转手送出去的收益都要被计算。举个例子就是A分出去BCD，B分出去了C和D，如果A要计算C或D的收益，则必须要计算中间收益B。
输入示例：
3
2 0
1 2
-1 2
输入说明：第一行表示有n张奖券，第二行到第n+1行的两个数，表示这个人的奖券收益，和奖券来源。
3
2 0
1 2
-1 2
输入说明：第一行表示有n张奖券，第二行到第n+1行的两个数，表示这个人的奖券收益，和奖券来源。
奖券来源i表明这个人的奖券来自于第i行的这个人。0表示他是奖券的源头。如2表示奖券来源于输入第二行这个人。
输出示例： 3
输出示例： 3
当场只有75%，下面是我下来调整过的，感觉没啥问题了：
from collections import defaultdict n=int(input()) rs=defaultdict(int) t=defaultdict(list) begin=-1 for i in range(n): r,p=map(int,input().strip().split()) rs[i]=r # 第i个人自身的收益，从0开始 if p==0: begin=i else: t[p-2].append(i) # p-2的分发列表，加上i max_cur=-100000000000 def dfs(index): global max_cur cur=rs[index] current=0 if not t[index]: # 该节点没有分给任何人，即叶子节点 max_cur=max(cur,max_cur) return cur for i in t[index]: # 深度遍历i的所有子节点 up=dfs(i) current=max(up,current) max_cur=max(cur+current,max_cur) return cur+current dfs(begin) print(max_cur%1000000003)
附一个别人的全a：
作者：XW.Xiong
链接：https://www.nowcoder.com/discuss/464700?type=post&order=time&pos=&page=1&channel=1013&source_id=search_post
来源：牛客网
#笔试题目##猿辅导#链接：https://www.nowcoder.com/discuss/464700?type=post&order=time&pos=&page=1&channel=1013&source_id=search_post
来源：牛客网
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const long long MOD = 1e9+3;
long long val[MAXN];
vector<int> edges[MAXN];
long long dfs(int rt, long long& ans) {
long long ret = val[rt];
for(auto &v : edges[rt]) {
ret = max(ret, ret + dfs(v, ans));
// ret = (ret + MOD) % MOD;
}
ans = max(ans, ret);
return ret;
}
int main() {
//freopen("input-1.txt", "r", stdin);
int n, rt = -1;
cin >> n;
for(int i = 0; i < n; ++i) {
int fa;
cin >> val[i] >> fa;
if(fa == 0) rt = i;
else edges[fa - 2].push_back(i);
}
long long ans = -infl;
dfs(rt, ans);
cout << (ans + MOD) % MOD << endl;
return 0;
}
查看13道真题和解析