2024牛客寒假算法基础集训营6

A 宇宙的终结

如果一个数满足：该数等于恰好三个不同素数的乘积，那么它就是宇宙的终极答案之一。
小红希望你找到 $[l, r] (1 \leq l, r \leq 100)$ 区间内的一个终极答案，你能帮帮她吗？

$: {2, 3, 5, 7, 11, 13}$

只有几个数在 $100$ 以内满足三个不同素数相乘

void solve() {
    int l, r;cin >> l >> r;
    for (int i = l; i <= r;i++) {
        if (i == 30 || i == 42 || i == 66 || i == 78 || i == 70) {
            cout << i << '\n';
        }
    }
    cout << "-1\n";
}

D 友谊的套路

在 BO5（五局三胜制）游戏中，最激动人心的战局莫过于让二追三——即某支队伍先输了两局，然后接下来取得三连胜反败为胜。
现在小红队和小紫队正在进行一场 BO5 的对战，已知小红队每一局获胜的概率为 $p$ ，请问最终这场对战出现让二追三的概率是多少？

分为小红让二追三和被让二追三
double ans = (1 - p) * (1 - p) * p * p * p + (1 - p) * (1 - p) * (1 - p) * p * p;

E 未来的预言

在淘汰制游戏中，有一个比较常用的机制：BO 机制。一般 BO 后面接一个奇数 $x$ ，代表比赛的总局数，两个队伍谁的胜局先超过 $x$ 的一半，谁就获胜了。例如，"BO 3"代表三局两胜，"BO 5"代表五局三胜，以此类推。
现在给定游戏规则为 BOx，以及红队和紫队两个队伍接下来若干局的的胜负情况（不一定比完，因为有可能没比完就结束了）。现在请你判断比赛得出胜负的时候，一共进行了多少局。

void solve() {
    string a;cin >> a;
    a.erase(a.begin());
    a.erase(a.begin());
    int n = stoi(a);

    string t;cin >> t;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0;i < t.size();i++) {
        if (t[i] == 'R')cnt1++;
        else cnt2++;
        if (cnt1 > n / 2) {
            cout << "kou!\n";cout << i + 1 << '\n';return;
        }
        if (cnt2 > n / 2) {
            cout << "yukari!\n";cout << i + 1 << '\n';return;
        }
    }
    cout << "to be continued.\n";
    cout << t.size() << '\n';
}

C 心绪的解剖

看 $n (1 \leq n \leq 10^{9})$ 是否能分解为三个斐波那契数之和。能，给出这三个数，不能输出 -1 -1

注意开 ll

直接暴力的话就会超时，用 map 存起来就行

#define int long long
vector<int> f(50);
unordered_map<int, array<int, 3>> a;
void solve() {
    int x;cin >> x;
    if (a.count(x)) {
        auto [i, j, k] = a[x];
        cout << f[i] << " " << f[j] << " " << f[k] << '\n';return;
    }
    cout << "-1\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    f[0] = 0;f[1] = 1;
    for (int i = 2;i <= 45;i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    for (int i = 0;i <= 45;i++) {
        for (int j = i;j <= 45;j++) {
            for (int k = j;k <= 45;k++) {
                a[f[i] + f[j] + f[k]] = {i,j,k};
            }
        }
    }
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
}

B 爱恨的纠葛

给定两个长度为 $n (1 \leq n \leq 10^{5})$ 的数组 $a, b$ ，现只能对 $a$ 数组进行打乱，使得满足 $b$ 和对打乱后的数组 $a$ $min ∣ a_{i} - b_{i} ∣$ 尽可能的小。

只要找到使得 $min ∣ a_{i} - b_{j} ∣$ 最小的 $i, j$ 两个下标, 对 $a$ 数组交换这两个下标，然后这时的 $min ∣ a_{j} - b_{j} ∣$ 即达到最小

void solve() {
    int n;cin >> n;vector<int> a(n), b(n);
    for (int i = 0;i < n;i++)cin >> a[i];
    for (int i = 0;i < n;i++)cin >> b[i];
    sort(a.begin(), a.end());

    int ans = abs(a[0] - b[0]), xx = 0, yy = 0;
    for (int i = 0;i < n;i++) {
        int x = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        if (x == n)x = n - 1;
        if (abs(a[x] - b[i]) < ans) {
            ans = abs(a[x] - b[i]);
            xx = x, yy = i;
        }
        if (x >= 1 && abs(a[x - 1] - b[i]) < ans) {
            ans = abs(a[x - 1] - b[i]);
            xx = x - 1, yy = i;
        }
    }
    swap(a[xx], a[yy]);
    for (int i = 0;i < n;i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
}

I 时空的交织

给定一个 $n \times m$ 的矩阵，有两个长度分别为 $n, m$ 的数组 $a, b$ 决定，这个矩阵第 $i$ 行第 $j$ 列为 $a_{i} \times b_{j}$

求在所有子矩阵中选择一个子矩阵该矩阵所有元素和的最大值

Solution

若选择的是 $(r_{i}, r_{j}) \to (c_{i}, r_{j})$

求 $\sum_{i = r_{i}}^{r_{j}} \sum_{j = c_{i}}^{c_{j}} a_{i} \times a_{j} = \sum_{i = r_{i}}^{r_{j}} a_{i} \times \sum_{j = c_{i}}^{c_{j}} a_{j}$

可转化为求a 数组的一个非空连续子数组和乘上b 数组的一个非空连续子数组和的最大值。

对于数组，可以先分别计算连续子数组能到的最大与负的最多的数，这些值可能参与答案的计算

先遍历数组，在连续区间中能到的正负数的最大值

对于一些特殊情况，最大值的变量不会变化，一直保持 $0$

如果数组最大值都是小于 0 的，则 $maxa$ 就取数组中最大的元素
如果数组最小值都是大于 0 的，则 $mina$ 取数组中最小的元素

则答案是 $max {maxa \times maxb, mina \times maxb, maxa \times minb, mina \times minb}$

注意开ll

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0;i < n;i++)cin >> a[i];
    for (int i = 0;i < m;i++)cin >> b[i];
    int maxa = -INT_MAX, currmaxa = 0, mina = INT_MAX, currmina = 0;
    for (int i = 0;i < n;i++) {
        currmaxa += a[i];
        currmina += a[i];
        if (currmaxa < 0)currmaxa = 0;
        if (currmina > 0)currmina = 0;
        maxa = max(maxa, currmaxa);
        mina = min(mina, currmina);
    }
    int maxb = -INT_MAX, currmaxb = 0, minb = INT_MAX, currminb = 0;
    for (int i = 0;i < m;i++) {
        currmaxb += b[i];
        currminb += b[i];
        if (currmaxb < 0)currmaxb = 0;
        if (currminb > 0)currminb = 0;
        maxb = max(maxb, currmaxb);
        minb = min(minb, currminb);
    }

    currmaxa = *(max_element(a.begin(), a.end()));
    currmina = *(min_element(a.begin(), a.end()));

    if (currmaxa <= 0)maxa = min(maxa, currmaxa);
    if (currmina >= 0)mina = max(mina, currmina);

    currmaxb = *(max_element(b.begin(), b.end()));
    currminb = *(min_element(b.begin(), b.end()));

    if (currmaxb <= 0)maxb = min(maxb, currmaxb);
    if (currminb >= 0)minb = max(minb, currminb);

    cout << max({mina * minb,maxa * maxb,maxa * minb,mina * maxb}) << '\n';
}

J 绝妙的平衡

小红拿到了一棵有根树，其中有一些节点被染成了红色。树的根节点是 1 号节点。

小红希望你给每个节点的权值赋值为 1 或者 2，需要满足每个红色节点的子树节点权值之和为 3 的倍数。

请你给出任意一个赋值方案。若无解输出 -1

Solution

DFS/贪心

若存在某个红色节点是叶子节点，则无解。否则一定有解

(待更 $\dots$ )

F 命运的抉择

给定一个数组 $a$ ，和两个空数组 $b, c$ ，将 $a$ 中所有元素加入 $b, c$ 中且满足： $b, c \neq N U L L$ 且对 $b, c$ 数组中所有元素 $gcd (b_{i}, c_{j}) = 1$ ，给出一个添加方案，若无解输出 -1

Solution

并查集

若数组中两个数有相同的素因子，则必定分到一起，看最后是几个并查集，若是一个，则无解，否则有解

(待更 $\dots$ )

G 人生的起落

定义 v-三元组： $(x, y, z) : x = z \cap x > y$

要求构造一个长度为 $n$ 的数组 $a$ ,使得数组总和为 $S$ 且恰好有 $k$ 个长度为 $3$ 的连续子数组是 v-三元组

Solution

构造

K 错综的统一

给定一个仅由 r e d 三种字母组成的 $n \times m$ 矩阵。

小红定义一个矩形区域是美丽的，当且仅当：在该矩形区域中，任意横向或者纵向取一个长度大于 1 的连续子串时，该字符串都不是回文的。
现在小红有若干次询问，每次给定一个矩形区域，问最少修改多少字符（字符只能修改为 r e d），可以使得该区域为“美丽的”？

H 纷乱的红线

小红拿到了一个圆，以及平面上有 $n$ 个点（保证没有三点共线）。现在小红将随机取 3 个点画一个三角形，她想知道这个三角形和圆的交点数量的期望是多少？