Luogu P2327 [SCOI2005]扫雷【递推/数学】By cellur925

推了好久啊。看来以后要多玩扫雷了qwq.

其实本题只有三种答案：0、1、2.

对于所有第一列，只要第一个数和第二个数确定后，其实整个数列就确定了，我们可以通过这个递推式得出

     sec[i-]=fir[i]+fir[i-]+fir[i-]

所以我们可以枚举每列的第1/2个数。

如果推到第n+1个数还存在，那么指定这种情况不成立。

Code

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define maxn 10090

 using namespace std;

 int n,ans;

 int fir[maxn],sec[maxn];

 bool check()

 {

     for(int i=;i<=n+;i++)

         fir[i]=sec[i-]-fir[i-]-fir[i-];

     if(fir[n+]) return false;

     return true;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%d",&sec[i]);

     for(int k=;k<=sec[];k++)

     {

         memset(fir,,sizeof(fir));

         fir[]=k;

         fir[]=sec[]-k;

         if(check()) ans++;

     }

     printf("%d",ans);

     return ;

 }

巴特西

Luogu P2327 [SCOI2005]扫雷【递推/数学】By cellur925

最新文章

热门文章