题解：CF2061C Kevin and Puzzle

可以发现样例解释出现红蓝双色，~~一眼dp~~。

发现题目很套路，可以设

dp_{i,0/1}

代表在前

i - 1

个人已经确定的情况下，第

i

个人说真话（

0

）或者假话（

1

）。

可以发现，当这个人说假话的时候，前一个人一定说真话，后一个人也是，但由于递推，只考虑前，可得：

dp_{i,1} = dp_{i - 1,0}

那当这一个人说真话的时候，前一个人可能说真话也可能说假话，但是如果是说假话，大前个人一定说真话（因为相邻两个人不同时说假话），可得：

dp_{i,0} = \begin{cases} dp_{i - 1,0} & \text{if } a_i = a_{i - 1}\\ dp_{i - 1,1} & \text{if } a_i = a_{i - 2} + 1\\ \end{cases}

由于第

n

个人有可能说真话也有可能说假话，所以答案为

dp_{n,0} + dp_{n,1}

对

10^9+7

取模的结果。

注意随时取模。

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[200010][2],a[200010];
signed main(){
    int t;
    cin >> t;
    while(t--){
        memset(dp,0,sizeof dp);
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++) cin >> a[i];
        dp[1][1] = 1;
        if(a[1]) dp[1][0] = 0;
        else dp[1][0] = 1;
        for(int i = 2;i <= n;i++){
            dp[i][1] = dp[i - 1][0];
            if(a[i] == a[i - 1]) dp[i][0] = dp[i - 1][0];
            if(a[i] == a[i - 2] + 1) dp[i][0] += dp[i - 1][1];
            dp[i][1] %= 998244353;
            dp[i][0] %= 998244353;
        }
        cout << (dp[n][0] + dp[n][1]) % 998244353 << '\n';
    }
}

题解：CF2061C Kevin and Puzzle

文章操作

相关推荐

评论

题解：CF2061C Kevin and Puzzle