CF886C.Petya and Catacombs
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A very brave explorer Petya once decided to explore Paris catacombs. Since Petya is not really experienced, his exploration is just walking through the catacombs.
Catacombs consist of several rooms and bidirectional passages between some pairs of them. Some passages can connect a room to itself and since the passages are built on different depths they do not intersect each other. Every minute Petya arbitrary chooses a passage from the room he is currently in and then reaches the room on the other end of the passage in exactly one minute. When he enters a room at minute i, he makes a note in his logbook with number t__i:
- If Petya has visited this room before, he writes down the minute he was in this room last time;
- Otherwise, Petya writes down an arbitrary non-negative integer strictly less than current minute i.
Initially, Petya was in one of the rooms at minute 0, he didn't write down number _t_0.
At some point during his wandering Petya got tired, threw out his logbook and went home. Vasya found his logbook and now he is curious: what is the minimum possible number of rooms in Paris catacombs according to Petya's logbook?
一位非常勇敢的探险家彼得亚曾决定探索巴黎的地下墓穴。由于彼得亚实际上并没有太多经验,他的探索活动仅仅是在地下墓穴中随意走动。
地下墓穴由若干房间以及某些房间对之间的双向通道组成。部分通道可能连接一个房间到它自身;并且由于这些通道建于不同深度,它们彼此互不相交。每一分钟,彼得亚都会从他当前所在的房间中任意选择一条通道,并恰好用一分钟到达该通道另一端的房间。当他于第 i 分钟进入某个房间时,他会在自己的日志本上记下一个数字 ti:
- 如果彼得亚此前曾访问过这个房间,则他写下他上一次访问该房间的分钟数;
- 否则(即这是他第一次访问该房间),彼得亚写下任意一个严格小于当前分钟数 i 的非负整数。
初始时刻(第 0 分钟),彼得亚位于其中一个房间,但他没有记录 t0。
在漫无目的的游荡过程中,彼得亚最终感到疲惫,扔掉了日志本,回家去了。瓦夏捡到了这本日志本,现在他很好奇:根据彼得亚的日志本,巴黎地下墓穴最少可能包含多少个房间?
输入格式
The first line contains a single integer n (1 ≤ n ≤ 2·105) — then number of notes in Petya's logbook.
The second line contains n non-negative integers _t_1, _t_2, ..., t__n (0 ≤ t__i < i) — notes in the logbook.
第一行包含一个整数 n(1≤n≤2⋅105)—— 表示 Petya 日志中记录的笔记数量。
第二行包含 n 个非负整数 t1, t2, …, tn(0≤ti<i)—— 表示日志中的笔记。
输出格式
In the only line print a single integer — the minimum possible number of rooms in Paris catacombs.
在唯一的一行中输出一个整数——巴黎地下墓穴可能的最少房间数。
输入输出样例
输入#1
2 0 0
输出#1
2
输入#2
5 0 1 0 1 3
输出#2
3
说明/提示
In the first sample, sequence of rooms Petya visited could be, for example 1 → 1 → 2, 1 → 2 → 1 or 1 → 2 → 3. The minimum possible number of rooms is 2.
In the second sample, the sequence could be 1 → 2 → 3 → 1 → 2 → 1.
在第一个样例中,Petya 访问的房间序列可以是,例如 1→1→2、1→2→1 或 1→2→3。房间数的最小可能值为 2。
在第二个样例中,序列可以是 1→2→3→1→2→1。
输入解题思路,AI测评打分。不知道怎么写?