猿辅导 笔试 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; }