牛客周赛 Round 4 题解

A. 游游的字符串构造

用 you 构造字符串，当 3 * k > n 时，构造不出来，否则构造 k 个 you 和 n - 3 * k 个 you 中任意字母即可。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    if (3 * k > n) {
        cout << -1 << endl;
        return 0;
    }
    string s = "you";
    for (int i = 0; i < k; i++) {
        cout << s;
    }
    for (int i = 0; i < n - 3 * k; i++) {
        cout << 'o';
    }
    cout << endl;
    return 0;
}

B. 游游的整数拆分

题目链接：B. 游游的整数拆分

显然，当 a * b 为 3 的倍数时，a 和 b 中至少有一个数为 3 的倍数，因此统计 $[1, n)$ 中 3 的倍数的个数 ans 即可。

当 n 为 3 的倍数时，a 和 b 同为 3 的倍数时，a 和 b 互换会导致重复统计，因此答案为 ans。
当 n 不为 3 的倍数时，a 和 b 不会同为 3 的倍数，因此 a 和 b 还可互换，因此答案为 ans * 2。

根据数据范围，考虑使用 long long 类型。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ll n;
    cin >> n;
    ll ans = (n - 1) / 3;
    if (n % 3) {
        ans *= 2;
    }
    cout << ans << endl;
    return 0;
}

C. 游游的整数操作

题目链接：C. 游游的整数操作

题目共有两种操作：

输入 1 x，代表所有数加 x。
输入 2 x，代表所有数减 x，同时将所有的负数变成 0。

可以看出，操作 1 无论什么时候进行，对答案的影响都是 + n * x，而操作 2 则只有在没有数被减成负数时对答案的影响才是 - n * x。因此设置变量 add 来记录上述的两种影响，同时设置变量 fu 来记录操作 2 在有数被减成负数时的影响。

先将所有数减去最小值，使得数组刚好都非负，减去的值记为 mi，累加到 add 上。
当执行操作 1 时 add += x。
当执行操作 2 时，先用 add 抵除影响，多余的则转化为 fu。
最后将所有数减去 fu，并将负数变成 0，求和再加上 add * n 即为答案。

根据数据范围，考虑使用 long long 类型。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MOD 1000000007
#define N 100005

int main() {
    ll n, k;
    cin >> n >> k;
    ll a[N];
    ll mi = 1e9;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mi = min(mi, a[i]);
    }
    ll add = mi;
    ll fu = 0;
    for (int i = 0; i < k; i++) {
        ll op, x;
        cin >> op >> x;
        if (op == 1) {
            add += x;
        } else if (op == 2) {
            if (x <= add) {
                add -= x;
            } else {
                fu += x - add;
                add = 0;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        a[i] = max(a[i] - mi - fu, 0ll);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
        ans %= MOD;
    }
    ans += add % MOD * n % MOD;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}

D. 游游的因子计算

题目链接：D. 游游的因子计算

一个数 $n$ 的因子应满足 $n \in [1, \sqrt{n}]$ ，因此枚举统计一个数的因子的时间复杂度为 $O(\sqrt{n})$ 。对于 ${a \times b} \in [1,10^{18}]$ ，直接枚举显然会超时。

因此我们枚举统计 $a$ 的因子，再枚举统计 $b$ 的因子，将 $a$ 的因子和 $b$ 的因子两两相乘，即为 $a \times b$ 的因子，最后去重即可。

根据数据范围，考虑使用 long long 类型。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ll a, b;
    cin >> a >> b;
    vector<ll> ya, yb;
    for (ll i = 1; i <= sqrt(a); i++) {
        if (a % i == 0) {
            ya.push_back(i);
            if (i != a / i) {
                ya.push_back(a / i);
            }
        }
    }
    for (ll i = 1; i <= sqrt(b); i++) {
        if (b % i == 0) {
            yb.push_back(i);
            if (i != b / i) {
                yb.push_back(b / i);
            }
        }
    }
    set<ll> ans;
    for (auto i : ya) {
        for (auto j : yb) {
            ans.insert(i * j);
        }
    }
    cout << ans.size() << endl;
    for (auto i : ans) {
        cout << i << " ";
    }
    return 0;
}

E. 小红的战争棋盘

题目链接：E. 小红的战争棋盘

大型模拟题不讲。

需要一个 n * m 的数组来记录棋盘，然后用 map 来记录各个势力的各种状态，按照要求模拟即可。