竞赛讨论区 > 小白月赛 50 题解

小白月赛 50 题解

头像
鸡尾酒QAQ
发布于 2022-05-21 21:16:34 APP内打开
赞 16 | 收藏 3 | 回复1 | 浏览1505

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;
    }
}

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐