2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了）

题目大意

给定 $n$ 个人从左到右站成一排。每个人的身份只有两种：诚实者或欺诈者。

• 诚实者一定说真话。

• 欺诈者可能说真话，也可能说假话。

• 第 $i$ 个人会报一个数 $a_i$，表示“自己左边有多少个欺诈者”。

• 额外保证：不存在两个相邻的欺诈者。

任务是统计：一共有多少种身份安排（每个人是诚实者或欺诈者）能够与所有人的发言同时不矛盾。结果对 998244353 取模输出。

输入为两行：

• 第一行是 $n$。

• 第二行是 $n$ 个整数 $a_i$。

输出为一行：满足条件的方案数（取模后）。

样例：

输入：
6
0 0 0 0 0 0

输出：
2

样例含义：6 个人都说自己左边有 0 个欺诈者。在“欺诈者不相邻”的前提下，能成立的身份安排共有 2 种。

思路讲解

// 0 shuo huang
for(int i=1;i<=N;++i){
    if(i==1){
        if(A[i]==0){
            dp[i][1]=1;
            dp[i][0]=1;
        }else{
            dp[i][0]=1;
        }
        continue;
    }
    // 说谎者只能从前面一个的诚实者转移过来
    // 因为不能连续两个都是说谎者
    dp[i][0]=dp[i-1][1];
    if(A[i]==A[i-1]){
      // 可以从诚实者转移过来的条件
        dp[i][1]+=dp[i-1][1];
        dp[i][1]%=mod;
    }
    if(A[i]==A[i-2]+1){
      // 可以从说谎者转移过来的条件
      // 之所以是这个，是因为如果前面一个是说谎者的话，那么再前面一个就是诚实者
        dp[i][1]+=dp[i-1][0];
        dp[i][1]%=mod;
    }
}

AC代码

AC

http://10.199.227.101/contest/1005/problem/L1-7/submission-detail/2146

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]\n";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()

using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;

void Solve(){
    ll N;
    cin>>N;
    vector<ll> A(N+2);
    for(int i=1;i<=N;++i){
        cin>>A[i];
    }
    vector<array<ll,2>> dp(N+2);
    // 0 shu huang
    for(int i=1;i<=N;++i){
        if(i==1){
            if(A[i]==0){
                dp[i][1]=1;
                dp[i][0]=1;
            }else{
                dp[i][0]=1;
            }
            continue;
        }
        dp[i][0]=dp[i-1][1];
        if(A[i]==A[i-1]){
            dp[i][1]+=dp[i-1][1];
            dp[i][1]%=mod;
        }
        if(A[i]==A[i-2]+1){
            dp[i][1]+=dp[i-1][0];
            dp[i][1]%=mod;
        }

    }
    ll ans=dp[N][0]+dp[N][1];
    ans%=mod;
    cout<<ans<<"\n";

    // mod
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    //	cin>>lT;
    //	while(lT--)
    Solve();
}
/*




 */

心路历程（WA，TLE，MLE……）