题解：P12291 [蓝桥杯 2024 国 Java A] 粉刷匠小蓝

· · 题解

题目传送门

思路

首先 1 是需要粉刷，0 是无需粉刷。按题意是构建一个序列，1 有几个，这个序列就有几个数，0 没有任何作用。

根据题目，题目说：那么它右侧（第 i+1 面墙∼第 n 面墙）蓝色的墙的个数必须是偶数（包括 0 个）。

这个序列是粉刷顺序，所以这个序列要满足：对于每个数 a_i，a_{1}\sim a_{i-1} 大于 a_i 的个数，必须是偶数个，不然序列不成立。

至此已经想到了 20 分的写法：全排列然后验证。

但想拿满分，就要考虑构造。

既然要满足要求，我们考虑从 1 开始填写只能先填写奇数相，那么正好前面有偶数相并且一定大于 1，满足要求。

例如 1 的个数有 5 个，T是可填写，F是不可填写。

T F T F T

填入最小数 1 后，这个数将永久不会影响后面的填写，因为他是最小的数，这等于将序列长度永久减 1。

以此类推，依次填入剩下的数。

求一共有多少种不同的合法序列。

那，有 n 个 1，1 产生的贡献是 \lceil \frac{n}{2} \rceil，2 产生的贡献是 \lceil \frac{n-1}{2} \rceil，i 产生的贡献是 \lceil \frac{n-i+1}{2} \rceil，由于是要求多少种不同的合法序列，就是求排列数量，所以求得是贡献积，可以用递推。 递推公式是：

f_0\gets1，f_1\gets1 ，f_2\gets1 f_i\gets f_{i-1}\cdot\lceil n/2 \rceil

由于 i 只用之前一项，所以不用定义数组，只用一个变量 ans 就行了。

Code

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
//#define int long long
using namespace std;
const int mod=1e9+7;//模数
int n;
signed main(void){
    IOS;
    cin>>n;
    int k=0;//1的个数
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        k+=x;//x只会为1或0。如果x为1，则k加1，如果为0，1的个数不会增加，所以不用写判断
    }
    int ans=1;//初始值k=0、k=1或k=2的值
    for(int i=3;i<=k;i++){
        ans=(1ll*ans*((i+1)/2))%mod;//记得 *1ll 不然会爆int，会WA
    }
    cout<<ans<<endl;//输出答案
    return 0;
}

闲话

我与QinYulang师出同门，他用的是看着用暴力跑出来的一到十的答案找规律，我用的是老师的思路改编了一下，我记得老师的思路有一大部分不一样。