T3

T3：

题目名称：下棋

时间限制：$1000ms$.

空间限制：$128MiB$

题意分析

这道题让我们求棋盘上有多少颗棋子，规则是这样的：

1.一共，输入$n$次，每次输入$a_i$，表示棋子下在$(1,a_i)$下棋

2.如果$(1,a_i)$位置已经有棋子，则要将棋下在$(1,a_{i+1})$的位置上

3.若$(1,a_{i+1})$也有棋子，则不执行任何操作

关键思路

这道题我们可以用一个vis数组记录位置是否有棋子，如果$vis_{a_i}$为真，则尝试$a_{i+1}$位置，如果$vis_{a_{i+1}}$也为真，则跳过。如果找到没有棋子的位置，就将这个点标记为true，最后循环遍历vis数组，查找值为true的元素个数

$Code$:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int ans = 0;//记录答案
    int arr[300000] = {};//每个棋子
    bool vis[300000] = {};//标记是否有棋子
    int n,m;
    cin >> n >> m;//输入
    for (int i = 1;i <= n;i ++){
        cin >> arr[i];//输入棋子位置
        if(vis[arr[i]]){//如果位置上已经有棋子
            if(vis[arr[i]+1]){//检测下一个位置
                continue;//如果也有棋子，则跳过
            }else{
                vis[arr[i]+1] = true;//标记这个位置
            }
        }else{
        	vis[arr[i]] = true;//标记当前位置
        }
    }
    for (int i = 1;i <= m;i ++){
        if(vis[i]){
            ans ++;//如果有棋子，记录
        }
    }
    cout << ans ;//输出
    return 0;
}