题解：CF2061C Kevin and Puzzle

题意

t

组数据。

n

个人站成一排，第

i

个人会告诉你他的左边有

a_i

个说谎者。

每个人有两种身份，诚实者和说谎者，诚实者一定会说真话，说谎者可能会说真话，也可能会说假话。

说谎者之间不能相邻。

现在问你游戏一共有多少种不同的情况。答案对

998244353

取余。

思路

考虑动态规划，我们可以用一个数组

dp

来统计答案。其中

dp_{i,0/1}

用来统计第

i

个人是诚实者/说谎者产生的贡献。

继续考虑初始化，我们可以初始化第

1

个人的，因为他只有是诚实者或说谎者两种可能。如果他是诚实者，那么就是

1

种情况，也就是说真话，即

dp_{i,0}=1

，如果他是说谎者，那么就要判断他说的是不是真话，我们可以判断

a_i

是否为

0

，因为他左边已经没有人了。所以初始化为

dp_{i,1}=[a_1=0]

。

接下来考虑转移方程，如果第

i

个人是说谎者，那么第

i-1

个人绝对不可能是说谎者，即

dp_{i,0}\gets dp_{i-1,1}

。

如果第

i

个人不是说谎者，那么就需要继续考虑。

第 $i-1$ 个人是说谎者。那么第 $i-2$ 个就一定不是说谎者。这需要满足 $a_i-1=a_{i-2}$ ，因为他们之间夹了一个说谎者。即 $dp_{i,1}=dp_{i-1,0}$ 。
第 $i-1$ 个人是诚实者。那么就需要满足 $a_i=a_{i-1}$ ，因为他们都是诚实者，所以不可能有差别。即 $dp_{i,1}\gets dp_{i-1,1}$ 。

最终的答案为

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

。注意多测清空。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=2e5+7;
int n,a[N],dp[N][2],t;
int main()
{
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        dp[1][0]=1;
        if(a[1]==0)dp[1][1]=1;
        else dp[1][1]=0;
        for(int i=2;i<=n;i++){
            dp[i][0]=dp[i-1][1];
            dp[i][1]=0;
            if(a[i]==a[i-1])dp[i][1]=(dp[i][1]+dp[i-1][1])%mod;
			if(a[i]-1==a[i-2])dp[i][1]=(dp[i][1]+dp[i-1][0])%mod;
        }
        cout<<(dp[n][0]+dp[n][1])%mod<<endl;
    }
    return 0;
}

题解：CF2061C Kevin and Puzzle

文章操作

题意

思路

代码

相关推荐

评论

题解：CF2061C Kevin and Puzzle