首页 > 试题广场 >

小猿的抽奖

[编程题]小猿的抽奖
  • 热度指数：400 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
猿辅导组织一次抽奖活动，奖券的发放方式是：某个同学拿到全部的奖券，然后自己留一张，其他的分发给他周边的同学；其他同学收到奖券后，自己留一张，再分发给周边还未收到过奖券的其他同学，以此类推，直到每个同学都收到一张奖券为止。
开奖时，每张奖券会得到一个奖励值，每个同学最终奖励值除了要包含自己奖券的奖励值外，还可以额外加上从经由自己发出去的奖券中选择出一部分奖券的奖励值。但是如果不选择某张奖券，那么经由持有这张没被选择奖券的同学发出去的所有奖券都不能再选了。比如A把BCD的奖券发给了B，B再把CD的奖券分发给了CD，A可以只选择自己的奖券，可以选择ABCD的奖券，也可以选择AB或ABC或ABD的奖券，但是不能只选择AC或者AD的奖券。
奖励值当然是越大越好，大家一定也想知道最终大奖是多少，请你帮大家算一下吧。

输入描述:
第一行输入N，表示N个同学，N <= 100000；
第二行到第N+1行输入两个整数A B，其中A表示某同学持有奖券的奖励值，-1e9 <= A <= 1e9，B表示该奖券是第B行的同学发给他的；
B=0表示他是第一个发奖券的同学。


输出描述:
输出整数M，为所有同学中获得的最大的奖励值除1000000003的模。
示例1

输入

3
2 0
1 2
-1 2

输出

3

说明


算法知识视频讲解
添加回答
励志要变胖的人头像 励志要变胖的人
解法1：拓扑排序，抽象为有向图，收到奖券的同学指向分发给他奖券的同学，也就是从底向上去计算 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n;
    cin>>n;
    vector<vector<ll>> e(n);
    vector<ll> money(n);
    vector<int> r(n,0);
    ll ans=0;
    for(int i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        money[i]=x;
        ans=max(ans,money[i]);
        if(y!=0){
            e[i].push_back(y-2);
            r[y-2]++;
        }
    }
    queue<int> q;
    for(int i=0;i<n;i++){
        if(r[i]==0)
            q.push(i);
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        //cout<<t<<" "<<money[t]<<endl;
        for(int i=0;i<e[t].size();i++){
            if(money[t]>0){
                money[e[t][i]]+=money[t];
                //money[e[t][i]]%=1000000003;
                ans=max(ans, money[e[t][i]]);
            }
            r[e[t][i]]--;
            if(r[e[t][i]]==0)
                q.push(e[t][i]);
        }
    }
    cout<<ans%1000000003;
}


发表于 2021-04-03 17:25:45 回复(1)
左职新手头像 左职新手
从第一个发奖券的开始进行dfs，递归函数返回当前节点对应同学所能获得的最大值，如果为负数，则返回0，由于在dfs过程中有可能产生最大值，所以需要使用BigInteger保存结果，如果使用取模之后的数，就会发生错误 
import java.util.Scanner;
import java.util.*;
import java.math.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static long mod = 1000000003L;
    static BigInteger ans = new BigInteger("0");
    // 从第一个发奖券的开始进行dfs
    // 不能隔着取
    // 中途有可能产生最大值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
            long[] reward = new long[n];
            int i, start = 0;
            for (i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
            for (i = 0; i < n; i++) {
                reward[i] = in.nextLong();
                int B = in.nextInt();
                if (B == 0) {
                    start = i;
                } else {
                    adj.get(B - 2).add(i);
                }
            }
            dfs(start, reward, adj);
            System.out.println(ans.mod(new BigInteger("1000000003")));
        }
    }

    static BigInteger dfs(int start, long[] reward, ArrayList<ArrayList<Integer>> adj) {
        BigInteger ansD = new BigInteger("0");
        if (adj.get(start).size() == 0) {
            return reward[start] < 0 ? new BigInteger("0") : new BigInteger(String.valueOf(reward[start]));
        }
        for (int i = 0; i < adj.get(start).size(); i++) {
            BigInteger tmp = dfs(adj.get(start).get(i), reward, adj);
            ansD = ansD.add(tmp);
        }
        if (reward[start] < 0 && ansD.add(new BigInteger(String.valueOf(reward[start]))).compareTo(new BigInteger("0")) < 0) {
            return new BigInteger("0");
        }
        ans = ans.max(ansD.add(new BigInteger(String.valueOf(reward[start])))); 
        return ansD.add(new BigInteger(String.valueOf(reward[start])));
    }
}
发表于 2022-12-19 17:26:29 回复(0)
wonderson头像 wonderson
树形dp，只通过了一半，待完善 
import java.util.*;

public class Main {
        public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();

                        
            Map<Integer, Node> map = new HashMap<>();
            Map<Node, Integer> parent = new HashMap<>();
            Node root = null;

            for (int i = 2; i < 2 + n; i++) {
                Node node = new Node(sc.nextLong());
                int p = sc.nextInt();
                if (p == 0) {
                    root = node;
                } else {
                    parent.put(node, p);
                }
                map.put(i, node);
            }
            sc.close();

            for (Node cur : parent.keySet()) {
                int pIdx = parent.get(cur);
                Node p = map.get(pIdx);
                p.addChild(cur);
            }

            long res = dfs(root);

            System.out.println(res);
        }

        private static final long MOD = 1000000003;

        private static long dfs(Node root) {
            if (root == null) {
                return 0L;
            }
            long sum = root.val;
            for (Node child : root.nexts) {
                long tmp;
                if ((tmp = dfs(child)) > 0) {
                    sum = (sum + tmp) % MOD;
                }
            }
            return sum;
        }

        static class Node {
            private List<Node> nexts;
            private long val;

            public Node(long val) {
                this.val = val;
                this.nexts = new ArrayList<>();
            }

            public void addChild(Node node) {
                nexts.add(node);
            }
        }

    }

发表于 2022-03-26 11:37:18 回复(0)
牛客624048537号头像 牛客624048537号
只通过了一半的测试用例，一个需要注意的地方是并不一定是第二行的B为0
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int m;
unordered_map<int,vector<int>>mp;
int dfs(vector<int>& value,int i){
    int result=value[i-2]%1000000003;
    for(auto p:mp[i]){
        int res=dfs(value,p)%1000000003;
       // cout<<res<<endl;
        result=max(result,result%1000000003+res)%1000000003;
    }
    m=max(m,result)%1000000003;
    return result;
}
int main(){
    int n;
    cin>>n;
    vector<int>value(n);
    int num;
    vector<int>f;
    for(int i=2;i<n+2;++i){
        cin>>value[i-2]>>num;
        if(num==0)
            f.push_back(i);
        mp[num].push_back(i);
        //cout<<value[i-2]<<" ";
    }
    m=value[0];
    for(int i=0;i<f.size();++i)
    dfs(value,f[i]);
    cout<<m<<endl;
    return 0;
    
}

发表于 2021-07-31 16:59:12 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 2021 数据库工程师 信息技术岗 测试开发工程师 猿辅导 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
4条回答 2080浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号