2022牛客寒假算法基础集训营1 - 题解

2022牛客寒假算法基础集训营1 - 题解 A . 九小时九个人九扇门 算法分析

dp 0/1 背包 升级版

我们可以注意到一点就是 : 一个数的数字根等于这个数对 9 取模的结果（特别地，取模得 0则数字根为9）

                  

                   

 为这个数模  的结果

 为数字根 证毕!!!

利用这个结论我们就可以方便对问题的求解了

状态表示

 表示从前  个数中取得数之和对  取模为  的方案数

状态转移

很简单就能想到就是第  个数取或者不取这两种情况

1. 取的情况

2. 不取的情况 

答案表示

用  表示即可,特别的需要注意九号门的答案是,(因为  初始状态不取的时候取模也是  此处多取了一种方案,将其去除 )

AC code

#include
using namespace std;
typedef long long LL;

const int mod = 998244353;
LL f[100000 + 10][10];
LL a[100000 + 10];

int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        int x;scanf("%d",&x);
        x %= 9;
        a[i] = x;
    }
    f[0][0] = 1;
    //f[i][j] : 表示前 i 个数求和 % 9 后得 j 的方案数
    for(int i = 1;i <= n;i ++)
     for(int j = 0;j <= 8;j ++)
      {
          f[i][(j + a[i]) % 9] = (f[i][(j + a[i]) % 9] + f[i - 1][j]) % mod;
          f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
      }
    
    for(int i = 1;i <= 8;i ++)
    printf("%d ",f[n][i]);
    printf("%d",f[n][0] - 1);
    return 0;
}

B.炸鸡块君与FIFA22

算法分析

ST表 (倍增),概念还是很好理解的,有必要掌握一下

起始分数在  的意义下相同,若  后的数是一样的,那么在经历了同一段的区间上的贡献是一样的,因此这是一个存在重复贡献的问题,可以用 ST 表解决。

用   表示初始分数  为 ,从  号位置开始,长度为的这段区间上的贡献。

 那么就是经典的倍增过程,本题就需要多注意求完上一个一半的区间后的,下一个区间的初始分数会发生变化的,即下列式子的后半段

void init()
{
    for(int j = 0;j < M;j ++)
     for(int i = 1;i + (1 << j) - 1 <= n;i ++)
      for(int k = 0;k < 3;k ++)
       if(!j)//初始化
       {
           if(s[i] == 'W') f[k][i][j] = 1;
           else if(s[i] == 'L') 
           {
               if(k != 0) f[k][i][j] = -1;
           }
       }
       else 
       {
           f[k][i][j] = f[k][i][j - 1] + f[(k + f[k][i][j - 1] + 3)% 3][i + (1 << (j - 1))][j - 1];
       }
}

询问的话,也是老的套路,在这个区间上倍增,能取到的把他加上就完事了。

 维护当前的位置,然后依靠  不断倍增,然后注意跳到每个位置后分数会改变就行

int query(int l,int r,int score)
{
    int pos = l;
    while(pos <= r)
    {
        int j = 0;
        while(pos + (1 << j) - 1 <= r) j ++;
        j --;
        score += f[(score + 3) % 3][pos][j];
        pos += (1 << j);
    }
    return score; 
}

AC code

#include 
#include 
#include 
#include 

using namespace std;
int n,q;
const int N = 2e5 + 10,M = 20;

char s[N];
int f[3][N][M];//f[k][i][j]:分数 % 3 为 k,在以 i 为起始位置,长度为 (1 << j) 的区间上的得分情况

void init()
{
    for(int j = 0;j < M;j ++)
     for(int i = 1;i + (1 << j) - 1 <= n;i ++)
      for(int k = 0;k < 3;k ++)
       if(!j)//初始化
       {
           if(s[i] == 'W') f[k][i][j] = 1;
           else if(s[i] == 'L') 
           {
               if(k != 0) f[k][i][j] = -1;
           }
       }
       else 
       {
           f[k][i][j] = f[k][i][j - 1] + f[(k + f[k][i][j - 1] + 3)% 3][i + (1 << (j - 1))][j - 1];
       }
}

int query(int l,int r,int score)
{
    int pos = l;
    while(pos <= r)
    {
        int j = 0;
        while(pos + (1 << j) - 1 <= r) j ++;
        j --;
        score += f[(score + 3) % 3][pos][j];
        pos += (1 << j);
    }
    return score; 
}
int main()
{
    cin >> n >> q;
    scanf("%s",s + 1);
    init();
    while(q --)
    {
        int l,r,sc;
        cin >> l >> r >> sc;
        printf("%dn",query(l,r,sc));
    }
    return 0;
}

F.中位数切分 算法分析

        一个区间内的中位数能够大于等于  说明,这个区间内大于等于  的数的个数(在这里记作) 一定比小于  的数的个数(在这里记作 () 多 。那么也就是说只要= 1" src="https://latex.codecogs.com/gif.latex?cnt1-%20cnt2%20%3E%3D%201" /> 就是可以满足条件的。那么为了尽可能多的划分区间,肯定是希望刚好为  的时候就将其划分。那么每一个区间将会消耗一份,那么最终划分的区间总数就会是      

AC code

#include 
#include 
#include 

using namespace std;
void solve()
{
    int n,m;
    cin >> n >> m;
    int cnt1 = 0,cnt2 = 0;
    for(int i = 1;i <= n;i ++)
    {
        int x;
        cin >> x;
        if(x >= m) cnt1 ++;
        else cnt2 ++;
    }
    if(cnt1 - cnt2 >= 1) printf("%dn",cnt1 - cnt2);
    else puts("-1");
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    solve();
    
    return 0;
}

G.ACM is all you need 算法分析

我们可以注意到这个函数, 只有在  的时候变换成才会对答案有影响,因此我们只需要讨论  的值,和  的取值即可。

a[i - 1],a[i] > a[i + 1]" src="https://latex.codecogs.com/gif.latex?2.a%5Bi%5D%20%3E%20a%5Bi%20-%201%5D%2Ca%5Bi%5D%20%3E%20a%5Bi%20+%201%5D" />

a[i - 1],a[i + 1] > a[i]" src="https://latex.codecogs.com/gif.latex?3.a%5Bi%5D%20%3E%20a%5Bi%20-%201%5D%2Ca%5Bi%20+%201%5D%20%3E%20a%5Bi%5D" />

讨论  的取值在何时才会改变当前状况,对答案产生贡献

具体的讨论公式已经呈现在代码的注释中。

最后取答案,就是在区间上取答案的办法,遇到左右端点加减贡献即可

AC code

#include
using namespace std;
const int N = 1e5 + 10;


void solve()
{
    int a[N];
    map mp;//存不同的 b 值可以使原函数去除多少 local minimum
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    int res = 0;//原本存在多少个 local minimum
    for(int i = 2;i <= n - 1;i ++)
    {
        if(a[i] < a[i - 1] && a[i] < a[i + 1])
        {
            res ++;
            int x = min(a[i - 1],a[i + 1]);
            // 2b - a[i] >= x    b >= (a[i] + x) /2  那么以(a[i] + x) / 2 为左端点 以后的区间 贡献 + 1
            mp[(a[i] + x + 1)/2] ++;
        }
        else if(a[i] > a[i - 1] && a[i] > a[i + 1])
        {
            int x = max(a[i - 1],a[i + 1]);
            //  |x - b| > |a[i] - b| => b > (a[i] + x) /2
            // 以 b 为左端点的贡献都要减 1
            mp[(a[i] + x)/2 + 1] --;
        }
        else if(a[i] > a[i - 1] && a[i] < a[i + 1])
        {
            // |b - a[i - 1]| > |a[i] - b| 时会构成局部最小 左端点开始 贡献 --
            mp[(a[i] + a[i - 1])/2 + 1] --;
            // |b - a[i]| > |a[i + 1] - b| 时不再构成局部最小 右端点结尾 贡献 ++
            mp[(a[i] + a[i + 1] + 1) / 2] ++;
        }
        else if(a[i] < a[i - 1] && a[i] > a[i + 1])
        {
            // |b - a[i + 1]| > |a[i] - b| 时会构成局部最小 左端点开始 贡献 --
            mp[(a[i] + a[i + 1])/2 + 1] --;
            // |b - a[i]| > |a[i - 1] - b| 时不再构成局部最小 右端点结尾 贡献 ++
            mp[(a[i] + a[i - 1] + 1)/2] ++;
        }
    }
    int ans = 0,tmp = 0;
    for(auto it : mp)
    {
        tmp += it.second;
        ans = max(ans,tmp);
    }
    printf("%dn",res - ans);
    return ;
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    solve();
    return 0;
}

H.牛牛看云 算法分析

 的数据范围限制了我们暴力求解的做法,同时我们也注意到了,这提示了我们在值域上进行暴力就可以了,暴力枚举上所有数字,两两搭配,

枚举到不同的数字  ,那么同样的数值就要计算,次

枚举到不同的数字 ,那么同样的数值就要计算,,因为只考虑了取两个不同的情况,但是本题自身是允许被取到的因此再补上  即可。

 

AC code

#include
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;

LL a[N],num[1005];

int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i],num[a[i]] ++;
    LL ans = 0;
    for(int i = 0;i <= 1000;i ++)
     for(int j = i;j <= 1000;j ++)
      {
          LL res;
          if(i == j) res = num[i] + (num[i] * (num[i] - 1) / 2);
          else res = num[i] * num[j];
          ans = ans + res * (LL)abs(i + j - 1000);
      }
    printf("%lldn",ans);
    return 0;
}

K.冒险公社 算法分析

一个简单但是比较麻烦的线性dp

状态表示

用  表示在前  个岛屿中,第  个岛屿颜色为 ,第  个岛屿颜色为 ,第  个岛屿颜色为  时,最多有多少个绿岛

状态转移

本文用的是,        

 肯定是从  转移过来的

 for(int now = 4;now <= n;now ++)
     for(int i = 1;i <= 3;i ++)//假设出i,j,k三个岛颜色的所有情况
      for(int j = 1;j <= 3;j ++)
       for(int k = 1;k <= 3;k ++)
       {
           int r = 0,g = 0,b = 0;//统计红绿黑颜色情况
           if(i == 1) r ++;if(i == 2) g ++;if(i == 3) b ++;
           if(j == 1) r ++;if(j == 2) g ++;if(j == 3) b ++;
           if(k == 1) r ++;if(k == 2) g ++;if(k == 3) b ++;
           
           for(int l = 1;l <= 3;l ++)
           {
               if(dp[now - 1][j][k][l] == - 1) continue;//不存在合法方案直接跳过
               if(g > r && s[now] == 'G') dp[now][i][j][k] = max(dp[now][i][j][k],dp[now - 1][j][k][l] + (i == 2));
               if(g == r && s[now] == 'B') dp[now][i][j][k] = max(dp[now][i][j][k],dp[now - 1][j][k][l] + (i == 2));
               if(g < r && s[now] == 'R') dp[now][i][j][k] = max(dp[now][i][j][k],dp[now - 1][j][k][l] + (i == 2)); 
           }
       }

 表示当前枚举到了第  个岛屿,考虑以  结尾的三个岛屿的情况和以 结尾的三个岛屿的情况,暴力判断其是否满足条件即可

限制条件就是

1.  岛是绿色的时,以 为结尾的三个岛屿中,绿色的岛屿数量一定要大于红色岛屿数量

2.  岛是红色的时,以 为结尾的三个岛屿中,红色的岛屿数量一定要大于绿色岛屿数量

3.  岛是黑色的时,以 为结尾的三个岛屿中,绿色的岛屿数量一定要等于红色岛屿数量

 

AC code

#include
using namespace std;
const int N = 1e5 + 10;
int dp[N][4][4][4];
char s[N];
// R 1      G 2         B 3
int main()
{
    
    int n;
    cin >> n;
    scanf("%s",s+1);
    memset(dp,-1,sizeof dp);
    
    //初始化前三个的岛的状态
    for(int i = 1;i <= 3;i ++)
     for(int j = 1;j <= 3;j ++)
      for(int k = 1;k <= 3;k ++)
      {
          int r = 0,g = 0,b = 0;
          if(i == 1) r ++;if(i == 2) g ++;if(i == 3) b ++;
          if(j == 1) r ++;if(j == 2) g ++;if(j == 3) b ++;
          if(k == 1) r ++;if(k == 2) g ++;if(k == 3) b ++;
          if(g > r && s[3] == 'G') dp[3][i][j][k] = g;
          if(g == r && s[3] == 'B') dp[3][i][j][k] = g;
          if(g < r && s[3] == 'R') dp[3][i][j][k] = g;
      }
      
     
    
    for(int now = 4;now <= n;now ++)
     for(int i = 1;i <= 3;i ++)//假设出i,j,k三个岛颜色的所有情况
      for(int j = 1;j <= 3;j ++)
       for(int k = 1;k <= 3;k ++)
       {
           int r = 0,g = 0,b = 0;//统计红绿黑颜色情况
           if(i == 1) r ++;if(i == 2) g ++;if(i == 3) b ++;
           if(j == 1) r ++;if(j == 2) g ++;if(j == 3) b ++;
           if(k == 1) r ++;if(k == 2) g ++;if(k == 3) b ++;
           
           for(int l = 1;l <= 3;l ++)
           {
               if(dp[now - 1][j][k][l] == - 1) continue;//不存在合法方案直接跳过
               if(g > r && s[now] == 'G') dp[now][i][j][k] = max(dp[now][i][j][k],dp[now - 1][j][k][l] + (i == 2));
               if(g == r && s[now] == 'B') dp[now][i][j][k] = max(dp[now][i][j][k],dp[now - 1][j][k][l] + (i == 2));
               if(g < r && s[now] == 'R') dp[now][i][j][k] = max(dp[now][i][j][k],dp[now - 1][j][k][l] + (i == 2)); 
           }
       }

    int res = - 1;
    for(int i = 1;i <= 3;i ++)
     for(int j = 1;j <= 3;j ++)
      for(int k = 1;k <= 3;k ++)
       res = max(res,dp[n][i][j][k]);
    printf("%dn",res);
    return 0;
}