牛客练习赛86

牛客练习赛86

A - 取因数

int main() {
    int n;
    cin >> n;
 
    if (n & 1)
        cout << "Bob";
    else
        cout << "Alice";
    return 0;
}

B- A + B

  • \(k = 0\), 直接输出 \(0~99\)
  • \(k = 1\), \(A + B = C, A \neq B\), 内外两次循环\(0-9\), \(10 * 10 = 100\)
  • \(k = 2\), 发两个加数组成的字符串为\(AAA\), 枚举A \(1-100\) 即可构成100个
#include <bits/stdc++.h>
using namespace std;

int get(int n) {
    int k = 01;
    while (n)
        k *= 10, n /= 10;
    return k;
}

int main() {
    int n, k;
    cin >> k >> n;

    if (k == 0)
        for (int i = 0; i < n; ++i)
            cout << i << '\n';
    else if (k == 1)
        for (int i = 0; n; ++i)
            for (int j = 0; j <= 9 && n; ++j, --n)
                cout << i << j << i + j << '\n';
    else
        for (int i = 1; n; ++i, --n)
            cout << i << i << i << i * 2 + i * get(i) << '\n';
    return 0;
}

C - 取钱

肯定是面值小的取的越多越好, 且小于下一个面值, 在来个二分查找即可

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int n, q;
    cin >> n;
 
    vector<long long> a(n);
    for (auto &i : a) cin >> i;
 
    vector<long long> sum(n), cnt(n);
    for (int i = 1; i < n; ++i) {
        sum[i] = sum[i - 1] + (a[i] - sum[i - 1] - 1) / a[i - 1] * a[i - 1];
        cnt[i] = cnt[i - 1] + (a[i] - sum[i - 1] - 1) / a[i - 1];
    }
 
    for (cin >> q; q; --q) {
        long long m, ans = 0;
        cin >> m;
 
        int k = upper_bound(sum.begin(), sum.end(), m) - sum.begin() - 1;
        if (k)
            cout << sum[k] + (m - sum[k]) / a[k] * a[k] << ' ' <<
                cnt[k] + (m - sum[k]) / a[k] << '\n';
        else
            cout << m << ' '<< m << '\n';
    }
    return 0;
}

D - 反转序列

首先要注意到, 反转序列, 只改变区间两端相邻的数

所以一次反转至多增加2个,

也就是\(A, A, ..., B, B\) 变为 \(A, B, ..., A, B\)

否则就增加一个

\(A, A, ..., C, B\) 变为 \(A, C, ..., A, B\)

\(A, A, ..., A, B\) 变为 \(A, C, ..., A, B\)

这种情况并没没有增加, 但我们还是让答案增加了 1, 后面说怎么减去

所以变成了, 统计有多少对相邻的数相同, 记为\(cnt_i\)

每次反转, 让\(cnt_i, cnt_j\) 各减1, 答案加2, (贪心, 每次\(i\)取\(cnt\)最多的, \(j\)取\(cnt\)最少的, 这样能加很多个2)

不够的时候, 就\(cnt_i\) 减1, 答案加1 (注意这里多算了)

设序列中出现最多的那个数出现了\(x\)次, 则

当\(x < \left \lceil \frac{n}{2} \right \rceil\), 最多有\(mx = 2 * (n - x)\)对

否则, 有\(mx = n - 1\)对

最后我们将统计的答案和\(mx\)取个\(min\), 就把多算的舍去了

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    int val[2] = { -5, -5 }, ans = -1, mx = 0;
    vector<int> sum(n, 0), ap(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> val[i & 1];
        ++ap[--val[i & 1]];
 
        if (ap[mx] < ap[val[i & 1]])
            mx = val[i & 1];
 
        if (val[i & 1] == val[i & 1 ^ 1])
            ++sum[val[i & 1]];
        else
            ++ans;
    }
 
    multiset<int> cnt;
    for (int i = 0; i < n; ++i)
        if (sum[i])
            cnt.insert(sum[i]);
 
    while (k && cnt.size() > 1) {
        int x = *cnt.begin(), y = *cnt.rbegin();
        --x, --y, ans += 2, --k;
        cnt.erase(cnt.begin());
        cnt.erase(--cnt.end());
        if (x)
            cnt.insert(x);
        if (y)
            cnt.insert(y);
    }
 
    if (k && !cnt.empty())
        ans += min(k, *cnt.begin());
 
    cout << min(min(ans, n - 1), n - ap[mx] << 1);
    return 0;
}
上一篇:第86题:分隔链表


下一篇:Leetcode 86 分割链表