题解归档 - cf362B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf362B
• 本地来源：problems/cf362B/idea.md
• 题目链接：https://codeforces.com/contest/362/problem/B
• 原始标题：cf362B — Petya and Staircases

思路

cf362B — Petya and Staircases

题意

$n$ 级台阶，每次可跳 1/2/3 级；部分台阶脏不能踩。必须从 1 到 $n$，且 1 与 $n$ 若脏则不可行。

做法

排序脏台阶后：

1. 若 1 或 $n$ 脏 → NO
2. 若存在三个连续脏台阶 $d,d+1,d+2$ → NO（在 $d-1$ 处三步都会落在脏块内）
3. 否则 → YES（其余脏点均可被 1/2/3 步跳过）

验证

样例 + Python 暴力对拍 5000 组（Kali 离线时本地脚本验证）。

代码

来源：problems/cf362B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:47:36
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=3005;
ll a[maxn+5],n,m,i,pd;
int main(){
    cin>>n>>m;
    pd=1;
    for(i=1;i<=m;i++)
        cin>>a[i];
    if(m>0){
        sort(a+1,a+m+1);
        if(a[1]==1 or a[m]==n)
            pd=0;
        for(i=1;i+2<=mandpd;i++)
            if(a[i+1]==a[i]+1 and a[i+2]==a[i]+2)
                pd=0;
    }
    cout<<(pd?"YES":"NO")<<"\n";
    return 0;
}