猿辅导 笔试 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行的两个数,表示这个人的奖券收益,和奖券来源。
奖券来源i表明这个人的奖券来自于第i行的这个人。0表示他是奖券的源头。如2表示奖券来源于输入第二行这个人。
输出示例: 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
来源:牛客网
#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;
}





#笔试题目##猿辅导#
全部评论

相关推荐

点赞 评论 收藏
转发
2 3 评论
分享
牛客网
牛客企业服务