小白月赛 50 题解

A. 跳跃

从第二个数字开始，判断每一个数字是否至少是前一个数字的 倍，或者前一个数字是否至少是当前数字的 倍。要注意问题的转换，如果使用 int 读入，则尽量不要使用除法（因为除法默认整除，会向下取整，使得本题细节更多）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int main(){
    int n, sum = 0, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 2; i <= n; i++){
        if(a[i] > a[i-1] * k){
            sum++;
        }else if(a[i] * k < a[i-1]){
            sum++;
        }
    }
    cout << sum << endl;
} 

B. 减法和除法

由于减法和除法都是将数字变小，而我们的目标就是将数字变得尽可能地小，所以我们可以去判断到底哪一种操作会使得数字变得更小，来使用对应的运算符。

#include <iostream>
using namespace std;
int main(){
    int n, x, ans = 0;
    cin >> n >> x;    
    while(n > 0){
        n = min(n / 2, n - x);
        ans++;
    }
    cout << ans << endl;
}

C. 减法和求余

本题有三种情况

1. 所有数字均为 0，无需进行任何操作，操作次数为 0。
2. 所有数字的最大公约数大于等于 2，这时可以令 为所有数字的最大公约数，然后进行求余操作，使得所有数字全部变为 0，操作次数为 1。或者所有数字均为 1，此时可以通过一次操作 2 来将所有数字变为 0。
3. 将所有数字全部对 2 进行求余，此时所有数字要么是 0，要么是 1，将所有 1 进行减一操作变为 0，操作次数为 2。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, a, cnt01 = 0, gcd = 0, cnt0 = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a;
        gcd = __gcd(gcd, a);
        if(a == 1){
            cnt01++;
        }
        if(a == 0){
            cnt01++;
            cnt0++;
        }
    }
    if(cnt0 == n){
        cout << 0 << endl;
    }else if(cnt01 == n || gcd > 1){
        cout << 1 << endl;
    }else{
        cout << 2 << endl;
    }
}

D. 生日

考虑在第 天过生日的人产生的快乐值对答案的贡献。在第 天过生日的人只可能有三个人，即 、、，我们只需要讨论这三个人的过生日选择（即他们选择是否在第 天过生日），就可以知道第 天能够产生多少快乐值了。将这个值乘以 就可以得到第 天的贡献了。因为每个人有两种选择，已经确定了三个人，那么剩余人随便选择的方案数就是

要注意讨论 和 不存在的情况。

本题也可以不使用快速幂，而是预处理好 次方对 取模后的结果。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
ll mod = 1e9 + 7;
int a[maxn], mi[maxn];
int main(){
    ll n, ans = 0;
    cin >> n;
    mi[0] = 1;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        mi[i] = mi[i-1] * 2 % mod;
    }
    for(int i = 1; i <= n; i++){
        ll now = 0;
        if(i * 2 <= n){
            now += a[i] ^ a[i*2];    
        }
        if(i * 2 + 1 <= n){
            now += a[i] ^ a[i*2+1];
            now += a[i] ^ a[i*2+1] ^ a[i*2];
            now += a[i*2] ^ a[i*2+1];
            ans += now * mi[n-3];
        }else{
            ans += now * mi[n-2];
        }
        ans %= mod;
    }
    cout << ans << endl;
} 

E. 工艺品

本题有三种情况

1. 自己制作工艺品的速度比加工半成品的速度快。此时所有工艺品全部自己做。
2. 自己制作工艺品的速度比加工半成品的速度慢，此时应当优先满足加工半成品的需求。我们可以算出最多能够加工多少半成品，然后剩余时间全部自己制作工艺品。最多能够加工半成品的数量由制作速度较慢的人来决定（即 和 的较大值），我们可以再分两种情况讨论 的较大值来算出答案。

#include <iostream>
using namespace std;
int main(){
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    if(a < c){
        cout << n / a;
    }else{
        int now = min((n - c) / b, (n - b) / c); // 表示制作 now 件半成品，数量由较慢的人来决定
        cout << now + (n - now * c) / a; // 制作 now 件半成品之后，剩余时间自己加工
    }
}

F. 数位和

先考虑不带修改的情况：

对于某一个数字而言，假设它的个位为 ，此时我们去求除了个位之外的数字的数位和，可以获得一个值 ，我们将 得到 ，可以发现，这个 一定是一个一位数。如果我们想要让这个数字的数位和被 10 整除，那么个位 需要满足的条件就是 ，由于 是个位数，所以我们可以解得唯一的一个 。也就是说，从零开始，每十个数字有且仅有一个数字的数位和是 10 的倍数。

所以答案一定与 有关。

我们发现 27 和 28 对应的答案分别是 1 和 2（即 有一个数字的数位和是十的倍数，而 有两个），但是 和 的结果都是 2。（此处的除法是整除），也就是说有的时候我们除以十可以获得正确答案，有的时候会多算一个，需要减掉。判断是否需要减掉的方法和上面的证明过程类似，即获得除了个位之外的数位和，然后解得唯一的 ，看看给定的数字的个位和 的关系，如果大于等于 ，则不会多算，否则说明多算了一个，需要减掉。

带修改之后的做法相似，只需要预处理出 的结果，就可以算出单点修改对答案的影响了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
long long po[maxn];
int main(){
    string s;
    int q;
    cin >> s >> q;
    long long sum = 0, now = 0, mod = 1e9 + 7, len = s.size();
    for(int i = 0; i < len - 1; i++){
        int nn = s[i] - '0';
        sum += nn;
        now = (now * 10 + nn) % mod;
    }
    po[0] = 1;
    for(int i = 1; i < len; i++){
        po[i] = po[i-1] * 10 % mod;
    }
    int need = (10 - sum % 10) % 10;
    bool flag = false;
    if(s[len-1] - '0' < need){
        flag = true;
    }
    cout << (now - flag + mod) % mod << endl;
    int a, b;
    while(q--){
        cin >> a >> b;
        int wei = len - a, last = s[a-1] - '0';
        wei--;
        if(wei != -1){
            now -= last * po[wei] % mod - b * po[wei] % mod;
            now = (now % mod + mod) % mod;
            sum = sum - last + b;
        }
        need = (10 - sum % 10) % 10;
        a--;
        s[a] = '0' + b;
        if(s[len-1] - '0' < need){
            flag = true;
        }else{
            flag = false;
        }
        cout << (now - flag + mod) % mod << endl;
    }
}