P1030 · OFFICIAL SOLUTION

P1030 鹧鸪天官方题解

Gioush OJ · P1030 鹧鸪天

鹧鸪天

【题意简述】

设第 $i$ 盏灯的状态为 $b_i\in\{0,1\}$ ，并令边界外的 $b_0=b_{n+1}=0$ 。给定

a_i=b_{i-1}+b_i+b_{i+1},

求共有多少个状态序列满足全部条件。

【Hint】

只需要枚举第一盏灯的状态，之后每个位置都会被上一条等式唯一推出。

【提示】

固定 $b_0=0$ 并枚举 $b_1$ 后，由 $a_{i-1}=b_{i-2}+b_{i-1}+b_i$ 可以依次推出 $b_i$ 。

【解法】

令 $b_0=b_{n+1}=0$ ，枚举 $b_1\in\{0,1\}$ 。对 $i=2,3,\dots,n$ ，递推

b_i=a_{i-1}-b_{i-2}-b_{i-1}.

若某次推出的 $b_i$ 不在 $\{0,1\}$ 中，则该枚举无效。最后还需要检查右端边界：

a_n=b_{n-1}+b_n.

两个初始状态至多产生两个候选方案，统计其中合法的方案数即可。

【边界检查】

固定 $b_0=0$ 已经处理了左端边界；枚举 $b_1$ 后，递推时每个 $b_i$ 都被唯一确定，若不在 $\{0,1\}$ 中立刻舍弃。最后检查 $a_n=b_{n-1}+b_n$ ，等价于验证右端边界 $b_{n+1}=0$ 。

【复杂度】

只有两种初值。每次枚举线性递推，时间复杂度为 $\mathcal{O}(n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/234Name:skycall.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 20001011using namespace std;12int Line[MAXN],n,Ans=0;13int Dp[MAXN];14bool Tag=1;15void Solve(){16    Ans=0;Tag=1;17    scanf("%d",&n);18    for(int i=1;i<=n;i++){19        scanf("%d",&Line[i]);20    }21    Dp[0]=0;Dp[1]=0;22    for(int i=2;i<=n;i++){23        if(Line[i-1]-Dp[i-1]-Dp[i-2]>1||Line[i-1]-Dp[i-1]-Dp[i-2]<0) {Tag=0; break;}24        else if(Line[i-1]-Dp[i-1]-Dp[i-2]==1){25            Dp[i]=1;26        }27        else if(Line[i-1]-Dp[i-1]-Dp[i-2]==0){28            Dp[i]=0;29        }30    }31    if(Line[n]!=Dp[n-1]+Dp[n]) Tag=0;32    if(Tag) Ans++;33    Dp[0]=0;Dp[1]=1; Tag=1;34    for(int i=2;i<=n;i++){35        if(Line[i-1]-Dp[i-1]-Dp[i-2]>1||Line[i-1]-Dp[i-1]-Dp[i-2]<0) {Tag=0; break;}36        else if(Line[i-1]-Dp[i-1]-Dp[i-2]==1){37            Dp[i]=1;38        }39        else if(Line[i-1]-Dp[i-1]-Dp[i-2]==0){40            Dp[i]=0;41        }42    }43    if(Line[n]!=Dp[n-1]+Dp[n]) Tag=0;44    if(Tag) Ans++;45    printf("%d\n",Ans);46    return;47}48int main(){49    int c,T;50    freopen("skycall.in","r",stdin);51    freopen("skycall.out","w",stdout);52    scanf("%d%d",&c,&T);53    while(T-->0) Solve();54    return 0;55}