牛客小白月赛108题解

A.小S按按钮

$\hspace{15pt}$ 小 S 想要忘记一切，可是她已身无分文。一天晚上她做了个梦，梦里她只需要按按钮，钱就会自动到账。

$\hspace{15pt}$ 一开始小 S 没有钱。当小 S 第奇数次（ $1,3,5,\cdots$ ）次按按钮时，她可以得到 $1$ 元；第偶数次（ $2,4,6,\cdots$ ）次按按钮时，她可以得到 $x$ 元。
$\hspace{15pt}$ 她想知道，最少需要按几次按钮，才可以赚到 $y$ 元钱或更多。
$\hspace{15pt}$ 本题有多组独立的询问，请你对每组询问的 $x,y$ 分别求出结果。

直接把奇数次和偶数次捆绑起来，整除再求余即可

特判 $y==1$ 和 $x==0,y>0$ 的情况

// C++

void solve(){
    int x , y;
    cin >> x >> y;
    // 两个特殊情况
    if(y == 1){
        cout << 1 << endl;
        return;
    }
    if(x == 0 && y > 0){
        cout << y * 2 - 1 << endl;
        return;
    }
    // 屎山求答案
    int ans = y / (x + 1) * 2;
    y = y % (x + 1);
    if(y <= 0){
        cout << ans << endl;
        return;
    }
    y --;
    ans ++;
    if(y <= 0){
        cout << ans << endl;
        return;
    }
    y -= x;
    ans ++;
    if(y <= 0){
        cout << ans << endl;
        return;
    }
}

B.小R排数字

$\hspace{15pt}$ 小 R 是一只小猫。有一天她得到了一个正整数 $n$ ，且 $n$ 在十进制表示下没有 $0$ （不考虑前导零）。
$\hspace{15pt}$ 小 R 太顽皮了，以至于她将这个正整数 $n$ 的数位重新排列为一个数（也可以不做排列，这样这个数依旧是 $n$ ）。
$\hspace{15pt}$ 现在小 R 的主人 T 想问问你，小 R 重组的数字是否有可能是 $4$ 的倍数。
$\hspace{15pt}$ 本题有多组询问，你需要对每个询问都求出相应的结果。

要想成为4的倍数，只要满足最后两位是4的倍数即可

因为最多就9种数字，直接记录每种数字出现的次数，暴力排列组合即可

// C++

void solve(){
    string s;
    cin >> s;
    int num = 0;
    int l = s.size();
    vector<int> dig(10);// 记录每种数字出现的次数
    // 如果本来就是4的倍数，直接输出YES
    for(int i = 0;i < l;i ++){
        num = num * 10 + s[i] - '0';
        dig[s[i] - '0'] ++;
    }
    if(num % 4 == 0){
        cout << "YES" << endl;
        return;
    }
    // 81次循环以内暴力排列组合
    for(int i = 1;i < 10;i ++){
        if(dig[i] <= 0) continue;
        dig[i] --;// 暂时-1
        for(int j = 1;j < 10;j ++){
            if(dig[j] <= 0) continue;
            if((i * 10 + j) % 4 == 0){
                cout << "YES" << endl;
                return;
            }
        }
        dig[i] ++;// 恢复出现次数
    }
    // 没有找到，输出NO
    cout << "NO" << endl;
}

C.小T数星星

$\hspace{15pt}$ 小 T 和她的朋友小 U 在看天文台看星星。

$\hspace{15pt}$ 天上有 $n$ 颗星星，第 $i$ 颗星星的亮度为 $a_i$ 。现在小 T 想把这些星星分组。
$\hspace{15pt}$ 具体地，她每次可以选取若干颗还未分组的星星（任意选取，不需要连续），如果它们满足：
$\hspace{23pt}\bullet\,$ 记一共选取了 $m$ 颗星星，它们的亮度分别是 $c_1,c_2,...,c_m$ ；
$\hspace{23pt}\bullet\,$ $c_1 \oplus c_2 \oplus \cdots \oplus c_m \neq 0$ ；
$\hspace{23pt}\bullet\,$ $\operatorname{lcm}(c_1,c_2,\cdots,c_m) (c_1 \oplus c_2 \oplus \cdots \oplus c_m) = 2 \times \min(c_1,c_2,\cdots,c_m)$ ；
$\hspace{15pt}$ 那么小 T 就可以将这些星星分为一组。
$\hspace{15pt}$ 小 T 想要让每颗星星都被分到某一组里，请问她最少需要分多少组？
$\hspace{15pt}$ 本题有多组数据，你需要对每组数据都求出对应的结果。
$\hspace{15pt}$ 在本题中， $\min$ 指最小数，例如 $\min(4,6,8)=4$ ； $\text{lcm}$ 指最小公倍数，例如 $\text{lcm}(2,3,4)=12$ ； $\oplus$ 表示按位异或运算。
$\hspace{15pt}$ 如果您需要更多最小公倍数相关的知识，请参考 OI-Wiki：最小公倍数 ；如果您需要更多位运算相关的知识，请参考 OI-Wiki：与、或、异或 。

很显然 $\operatorname{lcm}(c_1,c_2,\cdots,c_m)$ 一定是 $\min(c_1,c_2,\cdots,c_m)$ 的正整数倍，即记 $\operatorname{lcm}(c_1,c_2,\cdots,c_m)=L$ , $\min(c_1,c_2,\cdots,c_m)=M$ , $L$ 最小的可能性是 $M$ ,第二小的可能性就是 $2*M$

由于正整数异或结果一定非负,所以L的值不能比上面两种可能性更大

又因为 $c_1 \oplus c_2 \oplus \cdots \oplus c_m \neq 0$

所以L只能等于M,即选取的星星中亮度都一样，而且数量为奇数

那么只需要记录每一种亮度的星星的数量，奇数分为1组，偶数分为两组即可

// C++

void solve(){
    int n;
    cin >> n;
    map<int , int> c;// 存储每一种颜色的星星出现的次数
    for(int i = 0;i < n;i ++){
        int tmp;
        cin >> tmp;
        c[tmp] ++;
    }
    int ans = 0;
    // 遍历每一种亮度
    for(auto it : c){
        // 偶数分两组，奇数分一组
        if(it.second % 2 == 0) ans += 2;
        else ans ++;
    }
    cout << ans << endl;
}

D.小A弹吉他

$\hspace{15pt}$ 小 A 不想成为不被需要的人，所以她决定要努力练习吉他。但是她现在被一个作业题卡着了，为了珍惜练习时间，她现在向你求助。

$\hspace{15pt}$ 对于给定的正整数 $m$ ，小 A 需要选一个正整数 $n$ ，并构造一个长度为 $n$ 的正整数序列 $\{a_1,a_2,\dots,a_n\}$ 使得它们的和等于 $m$ 。
$\hspace{15pt}$ 小 A 想知道，对于所有可能的构造，令 $t_i$ 表示 $a_1,a_2,\dots,a_n$ 中等于 $i$ 的元素个数，最大的 $\operatorname{mex}\big\{t_1,t_2,\dots,t_{114^{514}}\big\}$ 是多少。请你求出这个值。
$\hspace{15pt}$ 本题有多组数据，请你对每组数据的 $m$ 都求出相应的结果。
$\hspace{15pt}$ 整数序列的 $\operatorname{mex}$ 定义为没有出现在序列中的最小非负整数。例如 $\operatorname{mex} \{1,2,3 \} =0$ 、 $\operatorname{mex} \{0,2,5\} =1$ 。

很显然0必然是出现过的，即任何一个数都可以选择不出现，这表示我们选择正整数可以是任意的

构造序列很麻烦，我们应该考虑二分答案

对于一个可能的答案 $x$ ，我们必然可以构造出一个 $1*a_1 2*a_2 … (x-1)a_{x-1}=m$ 满足所有的a_i都是互不相同的正整数，这样序列的 $mex$ 值才会是 $x$

上面的式子最小值为 $1*(x-1) 2*(x-2) … (x-1)*1$ ,很明显比这个值大的任何值都可以通过改变 $a_i$ 凑出来

化简这个式子：

原式=\sum^x_{i=1}i(x-i)=\frac{x(x 1)(x-1)}{6}

只有对于某个答案 $x$ ，计算 $\frac{x(x 1)(x-1)}{6}$ 的值，只要不大于m就是一个可能行的答案

由于题目中m的数据范围在 $[1,1e18]$ ,二分答案的过程中很容易爆 $long long$ ,所以要对答案范围设置一个合理的上界

这里设置 $m=1e18$ 时的答案1818182

// C++

const int N = 1818182;// 设置一个不会溢出的上界
int check(int x , int n){
    int res = x * (x + 1) * (x - 1) / 6;
    return res <= n;
}
void solve(){
    int n;
    cin >> n;
    int l = 0 , r = N + 1;
    int ans = 0;
    // 二分求答案
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid , n)){
            ans = max(ans , mid);
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << endl;
}

E.小M种树

$\hspace{15pt}$ 小 M 出身于贵族学校，擅长园艺。除了会给黄瓜浇水，她还会给一棵树上色。

$\hspace{15pt}$ 这棵树的形态与图论中描述的有根树相同，是以 $1$ 为根节点的 $n$ 个节点、 $n-1$ 条边的简单连通图。
$\hspace{15pt}$ 一开始，树上每个节点染上了红色或蓝色。定义以节点 $i$ 为根的子树的差异 $D(i)$ 为该子树中红色点数与蓝色点数的差的绝对值；而一棵树的不平均程度，等于 $\sum\limits_{i=1}^n D(i)$ 。
$\hspace{15pt}$ 现在小 M 有机会，可以修改其中一个节点的颜色（原来是红色就染成蓝色，反之同理）。小 M 想问你，有哪些修改的方案，可以让这棵树的不平均程度相比修改前更小。
$\hspace{15pt}$ 本题有多组数据，你需要对每组数据都求出对应的答案。

alt 很显然一个节点的差异只和他的子树有关

那么当一个节点的颜色发生改变时，只有他到根节点的链上的节点的差异会发生改变，所以我们可以计算出每一个节点的颜色发生改变时对不平均程度的贡献： alt 当节点 $x$ 由蓝转红时，对于他到根节点的链上的所有节点的子树的红色点数量 $C_r$ 和蓝色点数量 $C_b$ :

$C_b-C_r>=2$ 时, $D-2$
$C_b-C_r=1$ 时， $D$ 不变
$C_B-C_r\leq 0$ 时， $D 2$
由红转蓝同理

因此只要在一次深度优先搜索的过程中，通过求子树和的方式计算出每个节点的子树的红蓝节点个数，再在第二次深度优先搜索的过程中，通过树上前缀和的方式计算出每个节点颜色改变后的贡献即可

// C++

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    vector<int> color(n + 1);
    vector<int> g[n + 1];
    for(int i = 1;i <= n;i ++){
        if(s[i] == 'B') color[i] = 1;
        if(s[i] == 'R') color[i] = 0;
    }
    // 建边
    for(int i = 0;i < n - 1;i ++){
        int a , b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    vector<int> B(n + 1) , R(n + 1);// 存储子树中蓝色点的数量和红色点的数量
    vector<int> res(n + 1);// 判断是否可以降低不平均度
    vector<int> b(n + 1) , r(n + 1);// 最终贡献
    // dfs求子树红蓝节点个数
    function<void(int , int)> dfs = [&](int p , int fa){
        B[p] += (s[p] == 'B');
        R[p] += (s[p] == 'R');// 算上节点本身
        for(int nxt : g[p]){
            if(nxt == fa) continue;
            dfs(nxt , p);
            B[p] += B[nxt];
            R[p] += R[nxt];// 子树和
        }
    };
    dfs(1 , 0);
    // 第二次bfs求最终贡献
    function<void(int , int)> dfs2 = [&](int p , int fa){
        // 分类讨论计算贡献
        if(B[p] > R[p]) {
            if(B[p] - R[p] >= 2) r[p] -= 2;
            b[p] += 2;
        }
        else if(B[p] < R[p]) {
            if(R[p] - B[p] >= 2) b[p] -= 2;
            r[p] += 2;
        }
        else {
            r[p] += 2;
            b[p] += 2;
        }
        // 根据当前节点颜色计算结果
        if(s[p] == 'R'){
            res[p] = (b[p] < 0);
        }
        else{
            res[p] = (r[p] < 0);
        }
        for(int nxt : g[p]){
            if(nxt == fa) continue;
            b[nxt] = b[p];
            r[nxt] = r[p];
            dfs2(nxt , p);
        }
    };
    dfs2(1 , 0);
    for(int i = 1;i <= n;i ++){
        cout << res[i];
    }
    cout << endl;
}

F.小H算数

$\hspace{15pt}$ 小 H 是哪个角色？小 H 自己也不知道，但小 H 已经学会弹标题以 H 开头的一首歌了，望周知。

$\hspace{15pt}$ 小 H 有一个由 $n$ 个正整数组成的序列 $\{a_1,a_2,...,a_n\}$ ，对于其全部的区间 $[i,j] \left(1 \le i<j \le n\right)$ ，定义函数 $c(i,j)$ 和 $d(i,j)$ 如下：
$\hspace{15pt}$ 下面是函数 $c$ 的定义：
$\hspace{23pt}\bullet\,$ 若 $a_i=a_j$ ，则 $c(i,j)$ 等于区间中比两端（即 $a_i$ ）大的元素个数；
$\hspace{23pt}\bullet\,$ 若 $a_i \neq a_j$ ，则 $c(i,j) = 0$ 。
$\hspace{15pt}$ 下面是函数 $d$ 的定义：
$\hspace{23pt}\bullet\,$ 若区间长度（即 $j-i 1$ ）是奇数，则 $d(i,j)=1$ ；
$\hspace{23pt}\bullet\,$ 若区间长度（即 $j-i 1$ ）是偶数，则 $d(i,j)=2$ 。
$\hspace{15pt}$ 你需要帮小 H 求出序列 $a$ 中所有区间的 $c(i,j) \times d(i,j)$ 之和。

由于 $a_i\neq a_j$ 时 $c(i , j)=0$ ，所以我们只需要考虑两段元素相等的区间

我们可以存储每一种数出现的位置，从大到小查询每一种元素，用树状数组进行区间计数即可

// C++

#define lowbit(x) ((x) & (-x))
struct mit{
    vector<int> MIT;
    int l;
    mit(int n){
        init(n);
    } 
    void init(int n){
        l = n;
        MIT.resize(l + 1);
    }
    // 插入数据
    void add(int p , int a){
        while(p <= l){
            MIT[p] += a;
            p += lowbit(p);
        }
    }
    // 区间求和
    int sum(int p){
        int ans = 0;
        while(p){
            ans += MIT[p];
            p -= lowbit(p);
        }
        return ans;
    }
    // 查询区间和(利用前缀和)
    int query(int l , int r){
        return sum(r) - sum(l - 1);
    }
};
void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> pos[n + 1];
    set<int , greater<int>> st;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        pos[a[i]].pb(i);
        st.insert(a[i]);
    }
    mit MIT(n + 1);
    int ans = 0 , c[2] , ct[2];
    for(int it : st){
        int pre = -1;// pre用于存储上一个左界
        c[0] = 0 , c[1] = 0 , ct[0] = 0 , ct[1] = 0;// c用于存储区间计数，ct用于辅助构造
        for(int y : pos[it]){
            if(pre != -1){
                // 奇偶位对应的ct标记为+1
                ct[pre & 1] ++;
                c[pre & 1] += MIT.query(pre + 1 , y) * ct[pre & 1];
                c[pre & 1 ^ 1] += MIT.query(pre + 1 , y) * ct[pre & 1 ^ 1];
                ans += c[y & 1] + c[y & 1 ^ 1] * 2;
            }
            MIT.add(y , 1);// y在区间的计数+1
            pre = y;// 更新pre
        }
    }
    cout << ans << endl;
}

总结

这次小白月赛显然比上次周赛要简单()，所有题目都很常规，只要有一定基础+读题不出错都能写得比较轻松

A题就是常规的整除+求余，有一些很变态的特殊情况，把他们全部排除即可

B题考验小学数学功底，暴力枚举的规模实在太小，水题

C题考验读题，对异或操作足够了解就能很快发现题目的要求

D题考察二分，注意点在于求和公式的化简和防止溢出

E题是一道比较经典的dfs+dp问题，弄清楚贡献就没什么问题

F题是很典的树状数组计数问题，没学到会比较难写

题解 | #小白月赛108详解#