首页 > 试题广场 >

蚂蚁森林之王

[编程题]蚂蚁森林之王

热度指数：1986 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

很久很久以前，在蚂蚁森林里住着 $\mathit n$ 只小动物，编号从 $\text 1$ 到 $\mathit n$ 。编号越小的动物能力值越大。现在他们想投票选出一只小动物当森林之王，对于每只小动物来说，如果他有崇拜的对象，那么他可能投票选择自己，或与自己崇拜的对象投相同票；如果他没有崇拜的对象，那么他投票只可能选择自己。
每只小动物只会崇拜能力值比自己大的小动物。
记者小强拜访了这 $\mathit n$ 只小动物，了解到每只小动物是否有崇拜的对象以及具体是谁。现在他想知道每个人能得到的最高票数是多少。

输入描述:

第一行一个正整数  ，代表小动物的数量。
第二行  个以空格分隔的正整数  ，代表每只小动物崇拜的小动物。 
若 ，则代表第  只小动物没有崇拜的对象。
 。
保证 。

输出描述:

共  行，第  行代表第  只小动物可能得到的最多票数。

示例1

输入

4
0 1 1 1

输出

说明

如果第  只小动物均和第一只投一样的票，则第一只小动物可以获得四票。

算法知识视频讲解

pein531

一个数组存储每个小动物的崇拜对象，另一个数组存储每个小动物的最高票数。初始化每个小动物的票数为1（至少可以自己投给自己），由于每个小动物只会崇拜能力值更大的（编号更小），所以从后往前遍历，有崇拜对象就把身上所有的票都投给崇拜对象，如果从前往后遍历的话，在遍历到某个小动物时，崇拜它的小动物（编号更大）还未投票，它无法将自己所有可能的选票全部投给自己崇拜的对象。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strParams = br.readLine().trim().split(" ");
        int[] worshipId = new int[n + 1];
        int[] tickets = new int[n + 1];
        Arrays.fill(tickets, 1);
        for(int i = 0; i < n; i++) worshipId[i + 1] = Integer.parseInt(strParams[i]);
        for(int i = n; i >= 1; i--)
            tickets[worshipId[i]] += tickets[i];   // 有崇拜对象，假设把自己身上所有的票都投给崇拜对象
        for(int i = 1; i <= n; i++)
            System.out.println(tickets[i]);
    }
}

scala版

import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val n = StdIn.readInt
        val strArr = StdIn.readLine.split(" ")
        val worshipId = Array.ofDim[Int](n + 1)
        val tickets = Array.ofDim[Int](n + 1)
        for(i <- 0 to n - 1) worshipId(i + 1) = strArr(i).toInt;
        for(i <- n to 1 by -1){
            tickets(i) += 1                         // 自己有一票
            tickets(worshipId(i)) += tickets(i)     // 把所有的票给自己的偶像
        }
        for(i <- 1 to n) println(tickets(i))
    }
}

编辑于 2021-08-26 15:30:46 回复(2)

墨羽魂韶

把每个小动物看作有向图的一个节点, 只能够由低能力的指向高能力的, 那么从能力值最低的开始遍历将可以遍历到所有小动物, 只需要再遍历的过程中记录相应次数即可

#include <iostream>
#include <vector>
using namespace std;
#define int long long

void dfs(int u, vector<vector<int> > &edg, vector<int> & siz) {
    siz[u] = 1;
    for(const int &t : edg[u]) {
        dfs(t, edg, siz);
        siz[u] += siz[t];
    }
}

signed main() {
    int n; cin >> n; vector<int> fa(n);
    vector<vector<int> > edg(n);
    for(int i = 0; i < n; ++ i) {
        cin >> fa[i];
        -- fa[i];
        if(fa[i] != -1) edg[fa[i]].push_back(i);
    }
    vector<int> siz(n, 0);
    for(int i = 0; i < n; ++ i) {
        if(fa[i] == -1) dfs(i, edg, siz);
    }
    for(int i = 0; i < n; ++ i) cout << siz[i] << endl;
}

发表于 2022-03-13 08:12:49 回复(0)

桔桔桔桔桔子

N = int(input())
idols = list(map(int, input().split()))
dp = [1]*N
for k in range(N-1, -1, -1):
    if idols[k] != 0:
        dp[idols[k] - 1] += dp[k]
for vote in dp:
    print(vote)

发表于 2021-08-16 14:58:53 回复(0)

Java

momo_gogogo

题意绝了，“或与自己崇拜的对象投相同票”，应该理解成把别人投给我的票全部投给我的偶像……我以为是偶像投啥我投啥🤣🤣🤣🤣

发表于 2022-08-14 20:59:44 回复(2)

Kaitokuroba7

n = int(input())
nums = list(map(int, input().split()))
length = len(nums)
dic = {}

for i in range(length - 1, -1, -1):
    id = i + 1
    if id in dic:
        dic[id] += 1
    else:
        dic[id] = 1
    if nums[i] != 0:
        if nums[i] in dic:
            dic[nums[i]] = dic[nums[i]] + dic[id]
        else:
            dic[nums[i]] = dic[id]

for k in sorted(dic):
    print(dic[k])

发表于 2022-03-22 15:49:40 回复(0)

牛客90541827号

建树做的，转化成求每棵子树的大小，可惜最后一个用例栈溢出了，估计是退化成链表了

import java.util.*;

public class Main{
    static int[]size;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        List<List<Integer>>graph=new ArrayList<>(n+1);
        graph.add(null);
        for(int i=0;i<n;i++)graph.add(new ArrayList<>());
        Set<Integer>set=new HashSet<>();
        for(int i=0;i<n;i++){
            int target=in.nextInt();
            int cur=i+1;
            if(target>0){
                graph.get(cur).add(target);
                graph.get(target).add(cur);
            }else{
                set.add(cur);
            }
        }
        size=new int[n+1];
        for (Integer root : set) {
            dfs(graph,root,-1);
        }
        for(int i=1;i<=n;i++){
            System.out.println(size[i]);
        }
    }
    private static int dfs(List<List<Integer>>graph,int root,int parent){
        int ret=0;
        for (Integer child : graph.get(root)) {
            if(child==parent)continue;
            ret+=dfs(graph,child,root);
        }
        size[root]=ret+1;
        return ret+1;
    }
}

编辑于 2021-09-10 20:54:58 回复(0)

天真的程序员

#include<iostream>
#include<vector>

using namespace std;
void func(){
    int n;
    cin>>n;
    vector<int> A(n+1);
    vector<int> num(n+1,1);
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    for(int i=n;i>=1;i--){
       num[A[i]] += num[i];
    }
    for(int i=1;i<=n;i++){
        cout<<num[i]<<endl;
    }
}
int main(){
    func();
    return 0;
}

发表于 2021-06-17 10:42:26 回复(0)

鲁班之道

#include <bits/stdc++.h>

using namespace std;

int main(void)

{

int n;

cin >> n;

vector<int> arr(n + 1);

vector<int> map(n + 1, 1); // Everyone gets one ticket at least.

for (int i = 1; i <= n; ++i)

{

int tmp;

cin >> tmp;

arr[i] = tmp;

}

for (int i = n; i > 0; --i) // from end to start

{

if (arr[i] > 0)

{

// send ticket to idol.

map[arr[i]] += map[i];

}

for (int i = 1; i <= n; ++i)

cout << map[i] << endl;

return 0;

}

发表于 2021-05-16 20:08:39 回复(0)

Python

O_n2

每个人可以把收到的票投给自己，也可以把自己身上所有的票都寄给崇拜对象。而且，只能崇拜编号比自己小的。

def compute(A, n):
    ticket = [1 for _ in range(n)]
    for i in range(n-1, -1, -1):
        if A[i] > 0:
            ticket[A[i]-1] += ticket[i]
    return ticket

编辑于 2021-04-29 14:58:58 回复(0)