T3:
> 题目名称:下棋
>
> 时间限制:1000ms1000ms1000ms.
>
> 空间限制:128MiB128MiB128MiB
题意分析
这道题让我们求棋盘上有多少颗棋子,规则是这样的:
1.一共,输入nnn次,每次输入aia_iai ,表示棋子下在(1,ai)(1,a_i)(1,ai )下棋
2.如果(1,ai)(1,a_i)(1,ai )位置已经有棋子,则要将棋下在(1,ai+1)(1,a_{i+1})(1,ai+1 )的位置上
3.若(1,ai+1)(1,a_{i+1})(1,ai+1 )也有棋子,则不执行任何操作
关键思路
这道题我们可以用一个vis数组记录位置是否有棋子,如果visaivis_{a_i}visai 为真,则尝试ai+1a_{i+1}ai+1 位置,如果visai+1vis_{a_{i+1}}visai+1 也为真,则跳过。如果找到没有棋子的位置,就将这个点标记为true,最后循环遍历vis数组,查找值为true的元素个数
CodeCodeCode: