题解：CF1147A Hide and Seek

· · 题解

怎么还有能写题解的远古橙题？赶紧来水认真写一篇。

题目大意：

共有 n 个格子，你可以在最开始时将一枚棋子放入任意一个格子中。给定 k 次询问，每次询问前你可以把棋子移动到相邻的格子，但总共只能移动一次。问共有多少种合法的方案使得每次询问时棋子都不在询问的格子内（只有移动时间不同时不算新方案）。

思路：

从格子 i 开始，最终移动到格子 j 的方案合法，当且仅当 |i-j| \le 1 且 x_i 最后一次出现时间小于 x_j 第一次出现时间（应该很好想吧）。

时间复杂度 O(n)，空间复杂度 O(n)。

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,k,a[N],b[N],c[N];
signed main(){
//  freopen("ex.in","r",stdin);
//  freopen("ex.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    fill(b,b+n+1,1e12);
    c[0]=c[n+1]=1e18;
    for(int i=1;i<=k;i++){
        cin>>a[i];
        b[a[i]]=min(b[a[i]],i);
        c[a[i]]=max(c[a[i]],i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=-1;j<=1;j++){
            if(b[i]>c[i+j]){
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}