题解 | #牛客周赛 Round 39#

小红不想做炸鸡块粉丝粉丝题

https://ac.nowcoder.com/acm/contest/78904/A

前言：

题解主要参考于
- bilibili牛客官方视频讲解 ——这次由苯环哥讲题
- _Vector_的题解

A - 小红不想做炸鸡块粉丝粉丝题

跳过

B - 小红不想做鸽巢原理

思路：

首先做到 sum % k求出之后必定剩下的数量
然后，按照颜色的数量，从大到小贪心查找即可
若符合，则数量+1，否则，忽略。
详情请见代码部分

以下是代码部分

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e5 + 10;
int a[N];

int main()
{
    int n, k;
    cin >> n >> k;
    ll sum = 0;
  //输入，并求和
    for(int i = 1; i <= n; i ++)
        cin >> a[i], sum += a[i];
  //从小到大排序
    sort(a + 1, a + n + 1);
  //求剩余小球的数量
    ll temp = sum % (ll)k;
  //统计可以剩下的颜色数量
    int ans = 0;
  //按照每种颜色的数量，从大到小遍历
    for(int i = n; i >= 1; i --)
    {
        if(temp <= 0) break;
      //如果符合要求，就更新剩余的小球数量
        temp -= a[i];
      //统计可以剩余的小球颜色种类
        ans ++;
    }
    cout << ans << '\n';

    return 0;
}

C&D - 小红不想做完全背包

注意事项：

测试数据已经更新。
赛时的AC代码，部分错误

思路：

BFS广度优先搜索
把每一个可以到达的余数抽象为地图上的一个个点
然后用BFS遍历最短路径，路径即为所需最少的个数
输出点0的最短路径是多少

以下是代码部分，代码来源——_Vector_

#include<bits/stdc++.h>
using namespace std;

const int N = 2e3 + 10;
int mp[N];
bool vis[N];

int main()
{
    int n, p;
    cin >> n >> p;
    queue<pair<int, int> > q;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        //把点放进去，并标记为已有
        //mp[] == 1 代表地图上此结点存在
        //vis[] == 1 代表此结点已有最短路径，且数值为1
        if (mp[x % p] == 0)
        {
          //放入结点（x % p）,初始路径为1
            q.emplace(x % p, 1);
          //标记为已经走过
            vis[x % p] = true;
          //标记为地图上存在这个结点
            mp[x % p] = 1;
        }
    }
    //BFS广度优先搜索
    while(!q.empty())
    {
        int pos = q.front().first;
        int num = q.front().second;
        //如果在余数为0的时候已经存在数，则跳出
        if(!pos)
        {
            cout << num;
            return 0;
        }
        //如果此地图没有被走过vis[] == false，且存在向这下一步的结点mp[] == 1
        for(int i = 0; i < p; i ++)
            if(mp[i] == 1 && vis[(pos + i) % p] == 0)
            {
                //标记为已经走过
                vis[(pos + i) % p] = true;
                q.emplace((pos + i) % p, num + 1);
            }
        //队首出队
        q.pop();
    }

    return 0;
}

E - 小红不想做莫比乌斯反演杜教筛求因子和的前缀和

思路：

n m p都必须为正整数
规定：n为长。 m为宽。 p为高。
观察即可得出面积公式
x = n * m + (n + m) * 2 * p
由这两个，就可以O(1)求出p, 再进行判断即可

以下是代码部分

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, m, p, x;
    cin >> n >> m >> p >> x;
  //ans 记录合法数量
    int ans = 0;
  //穷举n和m
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
          //此时fugai代表了侧面覆盖黄油的面积
          //fugai = (i + j) * p * 2
            int fugai = x - i * j;
          //面积小于0， 不合法
            if(fugai <= 0) continue;
            int p_2 = (i + j) * 2;
          //不能整除（i + j） % 2， 代表p不是整数，不合法
            if(fugai % p_2 != 0) continue;
          //代表p == 0, 不合法
            if(fugai / p_2 == 0) continue;
          //求可能的p的值
            int v_p = fugai / (i + j) / 2;
          //如果v_p合法，则ans ++
            if(v_p >= 1 && v_p <= p) ans ++;
        }
  //输出合法值
    cout << ans << '\n';

    return 0;
}

F - 小红不想做模拟题

思路:

手搓线段树
来bilibili牛客竞赛观看视频，跟着苯环哥哥学习Lazy线段树

以下是代码部分，代码参考来源——bilibili牛客官方视频讲解

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5 + 10;

int n, q, a[N], b[N];

// 苯环哥的带懒标记的线段树
typedef struct Node{
    //a1：为a[]为1的个数
    //b1：为b[]为1的个数
    //c ：为a[] b[]同时为1的个数
    int l, r, a1, b1, c;

    //两个懒标记
    //一个用于 A[]字符串
    //一个用于 B[]字符串
    int lazy1, lazy2;
}Node;
//线段树空间开四倍，具体可以看 [OI Wiki](https://oi-wiki.org/ds/seg/)网站上的解释
Node Tr[N<<2];

//更新父节点Tr[u]
//用左右 两个 子结点 更新 父结点
void push_up(int u)
{
    //u结点      u的左子节点     u的右子节点
    //更新a1
    Tr[u].a1 = (Tr[u << 1].a1 + Tr[u << 1 | 1].a1);
    //更新b1
    Tr[u].b1 = (Tr[u << 1].b1 + Tr[u << 1 | 1].b1);
    //更新c
    Tr[u].c  = (Tr[u << 1].c  + Tr[u << 1 | 1].c );
}

//线段树的建立
void build(int u, int l, int r)
{
    //当递归到树的叶子时，也就是[l, r]的区间只有一个元素时，赋值
    if(l == r)
        Tr[u] = {l, r, a[l], b[l], a[l] & b[l]};
    else
    {
        Tr[u] = {l, r};
        int mid = (l + r) >> 1;
        //递归左分支
        build(u << 1, l, mid);
        //递归右分支
        build(u << 1 | 1, mid + 1, r);
        //记得更新Tr[u]结点的值
        push_up(u);
    }
}

//懒标记下放——更新
//用父节点更新左右两个子节点
void push_down(int u)
{
    //修改A[]的懒标记
    if(Tr[u].lazy1)
    {
        int lazy = Tr[u].lazy1;
        Tr[u << 1].a1 = (Tr[u << 1].r - Tr[u << 1].l + 1);
        Tr[u << 1].c  = Tr[u << 1].b1;
        Tr[u << 1 | 1].a1 = (Tr[u << 1 | 1].r - Tr[u << 1 | 1].l + 1);
        Tr[u << 1 | 1].c  = Tr[u << 1 | 1].b1;
        Tr[u << 1].lazy1 = 1;
        Tr[u << 1 | 1].lazy1 = 1;
        Tr[u].lazy1 = 0;
    }
    //修改B[]的懒标记
    if(Tr[u].lazy2)
    {
        int lazy = Tr[u].lazy2;
        Tr[u << 1].b1 = (Tr[u << 1].r - Tr[u << 1].l + 1);
        Tr[u << 1].c  = Tr[u << 1].a1;
        Tr[u << 1 | 1].b1 = (Tr[u << 1 | 1].r - Tr[u << 1 | 1].l + 1);
        Tr[u << 1 | 1].c  = Tr[u << 1 | 1].a1;
        Tr[u << 1].lazy2 = 1;
        Tr[u << 1 | 1].lazy2 = 1;
        Tr[u].lazy2 = 0;
    }
}

//线段树的修改
//op == 1, 则修改A[], 否则修改B[]
void modify(int u, int l, int r, int op)
{
    //如果当前结点的区间完全包含于被修改区间
    if(Tr[u].l >= l && Tr[u].r <= r)
    {
        //修改后，1的个数恰好等于区间长度
        if(op == 1)
        {
            Tr[u].a1 = Tr[u].r - Tr[u].l + 1;
            //A[]都变为1后，A&B就是B中为1的个数了
            Tr[u].c  = Tr[u].b1;
            //懒标记
            Tr[u].lazy1 = 1;
        }
        else
        {
            Tr[u].b1 = Tr[u].r - Tr[u].l + 1;
            Tr[u].c  = Tr[u].a1;
            Tr[u].lazy2 = 1;
        }
        return ;
    }
    //懒标记下放
    push_down(u);
    //一般情况
    int mid = (Tr[u].l + Tr[u].r) >> 1;
    //涉及到左分支
    if(l <= mid) modify(u << 1, l, r, op);
    //涉及到右分支
    if(r >  mid) modify(u << 1 | 1, l, r, op);
    //每次更新结点Tr[u]的状况
    push_up(u);
}

//线段树的区间查询
//int ask_interval(int v,int a,int b)//区间查询[a,b]
//{
//    if(tree[v].l>=a&&tree[v].r<=b)
//    {
//        return tree[v].w;
//    }
//
//    if(tree[v].lazy!=0) downadd(v);
//    //if(tree[v].lazy!=-1) downupdate(v);//区间改值用-1
//
//    int sum=0;
//    int mid=(tree[v].l+tree[v].r)/2;
//    if(a<=mid) sum+=ask_interval(v*2,a,b);
//    if(b>mid) sum+=ask_interval(v*2+1,a,b);
//
//    return sum;
//}

int main ()
{
    string A, B;
    cin >> n >> A >> B >> q;
    int ans = 0;
    //字符串转为数组，存储的对应的a[] b[]中
    for(int i = 0; i < n; i ++)
    {
        a[i + 1] = A[i] - '0';
        b[i + 1] = B[i] - '0';
    }
    //建线段树
    build(1, 1, n);
    while(q --)
    {
        char op;
        int l, r;
        cin >> op >> l >> r;
        int x = int(op - 'A') + 1;
        modify(1, l, r, x);
        cout << Tr[1].c << '\n';
    }

    return 0;
}

G - 小红不想做平衡树

思路：

建议直接观看——bilibili牛客官方视频讲解
首先，原本就是升序的连续区间，设其长度为n
- 易得它的好数数量为(n + n - 1 + n - 2 + …… + 2 + 1)。
- 一段降序的连续区间，设其好数组数量为sum, 长度为len
- 则其本身可以组成的好数组数量为(len - 1) * len / 2 + len
- 其中len * (lne - 1) / 2实际上是在这段区间范围内，任取两个端点组合，求出组合数
- +len为每个好数组的长度为1时的数量之和
对于降序区段，它可以和升序区间组合出更多好数组。共有三种组合方式
1. 只和前段的升序区间组合
  - 要求：降序区间的所有元素均大于前段升序区间
2. 只和后段的升序区间组合
  - 要求：降序区间的所有元素均小于后段升序区间
3. 可以和后段或者前段的升序区间组合
  - 同时满足1&2的要求

之后就可以得出，具体的线段翻转要求的讲解，可以观看牛客视频

以下是代码部分——bilibili牛客官方视频讲解

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;

int n, a[N];
ll pre[N], suf[N], ans;

void calc(int l, int r)
{
    for(int i = l; i <= r; i ++)
    {
        //此降序区段大于左边的升序区段的最大值
        if(a[i] <= a[l - 1] || l == 1) break;
            //加上它本身全都组成的好数组数量
            //好数组数量为 (n + n-1 + n-2 + …… + 2 + 1)
        else ans += l - pre[l];
    }
    //因为所选取的端点的问题，减去多算的一组
    ans -= l - pre[l];
    for(int i = r; i >= l; i --)
    {
        //此降序区段小于左边的升序区段的最大值
        if(a[i] >= a[r + 1] || r == n) break;
            //加上它本身全都组成的好数组数量
            //好数组数量为 (n + n-1 + n-2 + …… + 2 + 1)
        else ans += suf[r] - r;
    }
    //因为所选取的端点的问题，减去多算的一组
    ans -= suf[r] - r;

    int len = r - l + 1;
    //C(2, len),len的点中，任取两个端点的组合数
    ans += (len - 1) * len / 2;
    //如果降序数组与前后均可相连
    //则可以选取的不同端点数为此乘积
    if(l > 1 && r < n && a[r] > a[l - 1] && a[r + 1] > a[l])
        ans += (suf[r] - r) * (l - pre[l]);
}

int main ()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        //升序
        if(i > 1 && a[i] > a[i - 1])
            pre[i] = pre[i - 1];//pre[i]代表升序区段的左断点
        else
            pre[i] = i;
        //一段连续的升序区间，设它的长度为n
        //好数组数量为 (n + n-1 + n-2 + …… + 2 + 1)
        //求出了原本升序区间的所有好数组的数量得出的好数数量
        //以及所有长度为1的好数组的和
        ans += i - pre[i] + 1;
    }
    for(int i = n; i; i --)
    {
        //升序
        if(i < n && a[i] < a[i + 1])
            suf[i] = suf[i + 1];//suf[i]代表升序区段的右断点
        else suf[i] = i;
    }
    //双指针
    for(int i = 1; i < n; i ++)
    {
        int j = i;
        //获得最大降序区间
        while(j < n && a[j] > a[j + 1]) j ++;
        if(j > i) calc(i, j);
        //更新i值
        i = j;
    }
    cout << ans << '\n';

    return 0;
}

牛客周赛题解便于查看文章被收录于专栏

方便本人自己查看复习知识点。