Codeforces 931D Peculiar apple-tree（dfs+思维)

小咪咪 2021-10-01 07:14 196阅读 0赞

题目链接：[http://codeforces.com/contest/931/problem/D][http_codeforces.com_contest_931_problem_D]

题目大意：给你一颗树，每个节点都会长苹果，然后每一秒钟，苹果往下滚一个。两个两个会抵消苹果。问最后在根节点能收到多少个苹果。

解题思路：昨天是我想复杂了，其实就是统计下每层的苹果数，若是奇数则答案+1。因为最终这些苹果都会滚落汇聚到根节点，所以在滚落过程中肯定会碰撞并相消无论苹果是怎么分布的。

代码：

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<vector>
     5 #include<algorithm>
     6 using namespace std;
     7 const int N=1e5+5;
     8 
     9 int dep_num[N];
    10 vector<int>v[N];
    11 
    12 void dfs(int u,int dep){
    13     dep_num[dep]++;
    14     for(int i=0;i<v[u].size();i++){
    15         int t=v[u][i];
    16         dfs(t,dep+1);
    17     }
    18 }
    19 
    20 int main(){
    21     int n;
    22     scanf("%d",&n);
    23     for(int i=2;i<=n;i++){
    24         int fa;
    25         scanf("%d",&fa);
    26         v[fa].push_back(i);
    27     }
    28     dfs(1,1);
    29     int ans=0;
    30     for(int i=0;i<N;i++){
    31         ans+=dep_num[i]%2;
    32     }
    33     printf("%d\n",ans);
    34     return 0;
    35 }

转载于:https://www.cnblogs.com/fu3638/p/8509580.html

[http_codeforces.com_contest_931_problem_D]: http://codeforces.com/contest/931/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关 CodeForces 55D-Beautiful numbers【数位DP+思维】

题目链接：[https://codeforces.com/problemset/problem/55/D][https_codeforces.com_problemset_pr

布满荆棘的人生/ 2023年08月17日 17:37/ 0 赞/ 151 阅读

相关 CodeForces 55D

题意略。思路：本题可以说是醉翁之意不在酒了。要解开本题有几个关键点： 1.意识到数X = An An-1 An-2 An-3 .... A2 A1能被\{An,An-

深碍√TFBOYSˉ_/ 2023年08月17日 16:37/ 0 赞/ 152 阅读

相关 CodeForces1214D

[CodeForces1214D][] 这个题据我所知有两种比较优秀的做法. 第一种是\\(DP\\)统计每个点的路径数,然后找出必经点,再从必经点开始\\(bfs\\

柔光的暖阳◎/ 2023年06月02日 11:58/ 0 赞/ 48 阅读

相关 CodeForces1208D

CodeForces1208D 也是挺吓人的一道题,我一开始以为给的是每个数字前比它小的数字有几个,然后我就苦苦看不懂样例... 然后我冷静了一下,重新分析,读题,发现

浅浅的花香味﹌/ 2023年06月02日 11:56/ 0 赞/ 52 阅读

相关 Codeforces 496D

题意 -------------------- 进行若干场比赛，每次比赛两人对决，赢的人得到1分，输的人不得分，先得到t分的人获胜，开始下场比赛，某个人率先赢下s场比赛

你的名字/ 2022年07月16日 14:15/ 0 赞/ 139 阅读

相关 codeforces 1058E (思维)

[传送][Link 1] 题意：给n个数，每个数的二进制1都可以随意的换位置，问区间异或为0的有多少个思路：该问题可以转化为他的充要条件： 1.区间1的个数为偶数 2

迈不过友情╰/ 2022年05月10日 12:56/ 0 赞/ 215 阅读

相关 CodeForces - 1087D

CodeForces - 1087D https://vjudge.net/problem/2115151/origin 2\和/叶子结点的个数 includ

红太狼/ 2021年10月30日 01:36/ 0 赞/ 245 阅读

相关 Codeforces 931D Peculiar apple-tree（dfs+思维)

题目链接：[http://codeforces.com/contest/931/problem/D][http_codeforces.com_contest_931_probl

小咪咪/ 2021年10月01日 07:14/ 0 赞/ 197 阅读

相关 [Codeforces]871D Paths

　　失踪OJ回归。　　毕竟这样的数论没做过几道，碰上一些具体的应用还是无所适从啊。小C还是借助这题大致摸索一下莫比乌斯函数吧。 Description 　　有

本是古典何须时尚/ 2021年09月29日 09:06/ 0 赞/ 316 阅读

相关 CodeForces 1213A 【思维】题解

目录 1.0题目 2.0代码 1.0题目 zls有n个薯条，第i个薯条的位置在xi,一些薯条可能放在相同的位

快来打我*/ 2021年07月24日 18:53/ 0 赞/ 391 阅读