牛客小白月赛53 A~F

比赛链接：牛客小白月赛53

好久没有打小白月赛了，这回算半个四题首吧，E题怎么也写不出，代码又臭又长，结果是一个地方忽略掉了，第二天把F补了。经过上一次牛客练习赛，这回还是没有能升到1500...下次再来。

A.Raining（水题）

B.Kissing

打表发现其实就是$1+3+...+2n-1$，根据等差数列公式$\frac{(1+2n-1)\times n}{2}=n^2$，注意取模

C.Missing

这里wa了一发，一味的求快导致没看清题目，如果一个匹配的也没有就全部按字典序输出即可
前三题都太简单了不详细写了。

D.Breezing（DP）

题意

给你一个长度为$n$的数组$b_i$，你需要构造出拥有 最大的 可爱值的数组$a_i$，要求是对于每一个$i$都有$a_i\in [1,b_i]$。可爱值的定义是：相邻的两个差的绝对值之和。

8
11 45 14 19 1 9 8 10
a数组构造成1,45,1,19,1,9,1,10。

思路

乍一看样例是需要构造$1,b_2,1,b_4,...$或者是$b_1,1,b_3,1,...$这样最大值和最小值交替，但是这样的数据就不行：1 5 1 3 9，此时我需要下标为$1,3,4$都为最小的$1$，而其他的选最大的。

所以这是一个动态规划题而不是一个贪心题，开一个二维数组（或者两个一维数组）dp[i][2]，其中：
- dp[i][0] 表示前i个数，第i个数选最小的最大可爱值
- dp[i][1] 表示前i个数，第i个数选最大的最大可爱值

那么对于扫一遍，当前i的数据b[i]来看，我可以选择它为最大的$b_i$，也可能选择它的最小值$1$，而对于每一次选择，又可以从上一次的最大值和最小值来选，这里选第i个最大值为例：
- 在上一次为最小值(dp[i-1][0])的选：dp[i][1] = dp[i-1][0] + Abs(a[i]-1)
- 在上一次为最大值(dp[i-1][1])的选：dp[i][1] = dp[i-1][1] + Abs(a[i]-a[i-1])

所以状态转移方程就是二者取Max，而最小值同理

代码

int dp[N][2];
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=2;i<=n;i++)
    {
        dp[i][1] = dp[i-1][1] + Abs(a[i-1]-a[i]);
        dp[i][1] = Max(dp[i][1],dp[i-1][0]+Abs(a[i]-1));
        dp[i][0] = dp[i-1][1] + Abs(a[i-1]-1);
        dp[i][0] = Max(dp[i][0],dp[i-1][0]+Abs(1-1));//写两行是为了好看，思路清晰，一行有些挤6
    }
    cout<<Max(dp[n][0],dp[n][1]);
}

感谢灵神这周的训练，一眼秒这个题。

E.Calling（贪心）

题意

你有$a_i(1\leq i\leq 6)$个$i\times i$个正方形，然后有$n$个$6\times 6$的正方形板子需要去填，不能重叠，板子可以多，问是否能装得下那么多正方形。

思路

就贪心，从大到小，先装6，再装5,4。装5的时候需要拿1填，装4的时候需要拿2填，2不够了就去填1。3的时候也是一样的道理，太恶心了。原则：优先装大。

代码

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=6;i++)
        cin>>a[i];
    n-=a[6];
    n-=a[5];a[1]-=a[5]*11;
    n-=a[4];
    if (a[2]>=a[4]*5)
        a[2] -= a[4]*5;
    else
    {
        a[1] -= (a[4]*5-a[2])*4;
        a[2] = 0;
    }
    a[4] = a[5] = a[6] = 0;
    n -= a[3]/4;
    a[3] %= 4;
    if (a[3]==1)
    {
        n--;
        a[1]-=7;
        if (a[2]>=5) a[2] -= 5;
        else a[1] -= (5-a[2])*4, a[2] = 0;
    }
    else if (a[3]==2)
    {
        n--;
        a[1]-=6;
        if (a[2]>=3) a[2]-=3;
        else a[1] -= (3-a[2])*4, a[2] = 0;
    }
    else if (a[3]==3)
    {
        n--;
        a[1]-=5;
        if (a[2]>=1) a[2]-=1;
        else a[1] -= (1-a[2])*4, a[2] = 0;
    }
    n-=a[2]/9;
    a[2]%=9;
    if (a[2]>0)
    {
        n--;
        a[1] -= (9-a[2])*4;
        a[2] = 0;
    }
    if (a[1]>0) n -= (a[1]+35)/36;
    if (n>=0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

F.Freezing(状压DP)

这篇官方题解写的比较清楚，我用自己的话来重新写一遍
牛客小白月赛 53 赛后总结及题解

题意

给你一个字符串只包含h和o，o表示$1$，h表示$0$，有$n(1\leq n\leq 2\times 10^5)$个这个样的数$s_i$，字符串长度为$m(1\leq m\leq 15$)，你需要去选择一个顺序序列（指的是原来在后面的选出来不能到前面去）。比如原来是$1,2,3,4$，选出来$1,3$或者$2,3,4$都是合法的，不能选择$4,1$。需要满足条件：相邻两个的按位与必须为$0$，也就是每一位不能同时为$1$。问方案数。

思路

字符串长度为$m$最大只有$15$，所以首先想到状压DP，最开始想到的一个DP为令dp[i][j]表示考虑前i个数，以j结尾满足要求的子序列方案数。用$a_i$表示字符串转换过来的数，对于每次的dp[i][a[i]]都应该加上之前满足条件的值，也就是dp[i-1][k]这个k需要与a[i]按位与为$0$。这里的时间复杂度是$O(2^m)$，一共有$n$个数，所以总的时间复杂度是$O(n\times 2^m)$太大了。

这个dp肯定是正确的，就是按照题目意思模拟下来，但是时间复杂度太高，这里第一次学到了状压DP这种降时间复杂度的方法。

我将这里一共看成最大，把$m$拉满为$16$，令g[i][j][k]表示前i个数，结尾的数高$8$位为j，低$8$位与$k$按位与为$0$的子序列的方案数。

这样对于每一个数a[i]，我们取x = a[i]>>8, y = a[i]%255可以得到高$8$位和低$8$位。

首先对于k模拟高$8$位从$0$循环到$255$，如果k与x按位与为0，那么就加上g[i-1][k][y]，

为什么是g[i-1][k][y]？这里表示的是高$8$位为k的并且与y进行按位与为$0$的方案数。这样即与x按位与为0，又与y按位与为0，所以符合条件，需要加上到res。

这样就是这一个数字加上之后的贡献，那么需要考虑的就是如何更新g。

再一次让k模拟低$8$位，从$0$模拟到$255$，如果k与y按位与为0的话，说明符合我们的g[i][j][k]的定义，那么这个时候在g[i][x][k]加上之前所有的方案数res。以便后面使用。

为什么是g[i][x][k]？这个时候满足g的定义的，高$8$位为x，与k相与为$0$的方案数。

注意：这里的第三维从来就不是低$8$位，而是与低$8$相与为$0$的方案数。

但是问题又来了，这个时候的空间复杂度太大，可以看出，每次只与上一维有关，所以可以优化成一维。

代码

int dp[512][512];
inline void Case_Test()
{
    ll res=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a=0;
        cin>>s;
        ll tmp=1;
        for (int i=0;i<m;i++) 
            a = (a<<1)|(s[i]=='o');
        int x=a>>8;int y=a&255;
        for(int k=0;k<(1<<8);k++) if(!(k&x)) tmp=(tmp+dp[k][y])%mod;
        res=(res+tmp)%mod;
        for(int k=0;k<(1<<8);k++) if(!(k&y)) dp[x][k]=(dp[x][k]+tmp)%mod;
    }
    cout<<res<<endl;
}