牛客小白月赛84 解题报告

题目链接

https://ac.nowcoder.com/acm/contest/72041#question

A题

解题思路

签到

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 10;

void solve() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    if (x <= y && n - m + x >= y) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B题

解题思路

题目大意：给定x = gcd(a, b)和y = lcm(a, b)，请找出一对符合要求的a和b，如果有多种可能，找出a最小的那一对，如果a最小的还是有多种答案，那么找出b最小的那一对，找不出符合要求的答案则输出-1。

思路：首先很显然，lcm(a, b) % gcd(a, b)一定等于0，所以如果题目给出的gcd(a, b)大于了lcm(a, b)，或者lcm(a, b) % gcd(a, b)不为0，不用怀疑，直接-1。因为题目要求我们尽可能找更小的a以及更小的b，那么很显然我们a最小只能是gcd(a, b)，不能更小了，，怎么都不可能有a比gcd(a, b)更小的吧，然后显然最小的b就是lcm(a, b)，此题完。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 10;

void solve() {
    int x, y;
    cin >> x >> y;
    if (y % x != 0 || x > y) {
        cout << -1 << endl;
        return;
    }
    
    // lcm(a, b) = a * b / gcd(a, b);
    // y = a * b / x;
    cout << x << " " << y << endl;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C题

解题思路

题目大意：给一个长度为n的数组a，然后你需要构造出一个长度同样为n的数组b，要求数组b的第i位和数组a的第i位数值差值小于等于k，并且数组b必须满足所有相邻的两个元素都是非降序的。

思路：显而易见的一点是，我们如果要满足这两个条件，那么我们数组的起点要尽可能的小，并且每次b[i]要尽可能取的更小。那么我们b[1]就取a[1] - k，然后往后的b[i]，我们可取的下界l = a[i - 1] - k，上界r = a[i - 1] + k，有以下三种情况：

1、如果b[i - 1] > r，那么这组数据无解，终止循环；

2、如果l >= b[i - 1]，则b[i] = l；

3、如果b[i - 1] >= l并且b[i - 1] <= r，则b[i] = b[i - 1]。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];
int n, k;

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    b[1] = a[1] - k;
    bool flag = false;
    for (int i = 2; i <= n; i++) {
        int l = a[i] - k;
        int r = a[i] + k;
        if (r < b[i - 1]) {
            flag = true;
            break;
        }
        if (l >= b[i - 1]) {
            b[i] = l;
        }
        else {
            b[i] = b[i - 1];
        }
    }
    if (flag) {
        cout << "No\n";
    }
    else {
        cout << "Yes\n";
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D题

解题思路

题目大意：
给定一个只有0和1的字符串s，然后进行q次独立的询问，每次询问翻转一个区间[l, r]，请问每次翻转之后s的连续1子串有多少个。

思路：使用类似于前缀和的方法来维护，sum[i]表示字符串s[1, j]这段区间内连续的1的段数。当我们翻转了[l, r]这段区间之后，其实只有区间端点处会对答案产生影响。对整个答案的变化有以下四种情况需要考虑：

1、如果s[l - 1] == ‘1’ && s[l] == ‘1’ && s[r] == ‘0’，贡献 + 1；

2、如果s[r + 1] == ‘1’ && s[r] == ‘1’ && s[l] == ‘0’，贡献 + 1；

3、如果s[l - 1] == ‘1’ && s[l] == ‘0’ && s[r] == ‘1’，贡献 - 1；

4、如果s[r + 1] == ‘1’ && s[r] == ‘0’ && s[l] == ‘1’，贡献 - 1。

最终答案为sum[n] + 翻转后对答案的贡献值。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f;
using namespace std;
const int maxn = 2e6 + 10;
int n, q;
int sum[maxn];

void solve() {
    string s;
    cin >> n >> q;
    cin >> s;
    s = " " + s;
    //cout << s.size() - 1<<endl;
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1];
        if (s[i - 1] != '1' && s[i] == '1')
            sum[i]++;
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = sum[n];
        if (s[l - 1] == '1' && s[l] == '1'&& s[r] == '0') {
            ans++;
        }
        if (s[r + 1] == '1' && s[r] == '1' && s[l] == '0') {
            ans++;
        }
        if (s[l - 1] == '1' && s[l] == '0' && s[r] == '1') {
            ans--;
        }
        if (s[r + 1] == '1' && s[r] == '0' && s[l] == '1') {
            ans--;
        }
        cout << ans << endl;
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}