题解 | #2024牛客寒假算法基础集训营4#

Link

A B C D E F G H J

A

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a, b, k;
    cin >> a >> b >> k;
    
    cout << (a >= k * b ? "good" : "bad") << '\n';

    return 0;
}

B

每堆最多操作 次。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        sum += x - 1;
    }

    cout << (sum % 2 ? "gui" : "sweet") << '\n';
     
    return 0;
}

C

模拟。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    
    x--, y--;
    
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int p, q;
    cin >> p >> q;
    vector<int> o(q), z(q);
    for (int i = 0; i < q; i++) {
        cin >> o[i] >> z[i];
        z[i]--;
    }
    
    while (p--) {
        for (int i = 0; i < q; i++) {
            if (o[i] == 1) {
                char x = a[z[i]][m - 1];
                for (int j = m - 1; j > 0; j--) {
                    a[z[i]][j] = a[z[i]][j - 1];
                }
                a[z[i]][0] = x;
            } else {
                char x = a[n - 1][z[i]];
                for (int j = n - 1; j > 0; j--) {
                    a[j][z[i]] = a[j - 1][z[i]];
                }
                a[0][z[i]] = x;
            }
        }
    }

    cout << a[x][y] << '\n';

    return 0;
}

D

加 ，减 ，和不变。

数组求和后考虑分成 个数，使 等于最小的数，那么对 根号下分解因子，记因子为 ，只需数 的个数。

，无法操作输出 。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
  
    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    
    int ans = 0;
    for (int i = 1; sum / i >= n; i++) {
        if (sum % i == 0) {
            ans++;
        }
    }

    cout << (n > 1 ? ans : 1) << '\n';

    return 0;
}

E

题目转化为该数组中最多能分出几个不相交的漂亮数组。

考虑贪心。

对于 找它的左边离他最近的 使 的和为 的倍数。

此时已经转化为一个非常经典的问题。

可以使用 维护。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int sum = 0, pre = -1, ans = 0;
    map<int, int> mp{{sum, -1}};
    for (int i = 0; i < n; i++) {
        sum = (sum + a[i]x) % k;
        if (mp.count(sum) && mp[sum] >= pre) {
            ans++;
            pre = i;
        }
        mp[sum] = i;        
    }

    cout << ans << '\n';

    return 0;
}

F

dp。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
constexpr int inf = 1E9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 1; i <= n; i++) {
        f[i] = max(f[i], f[i - 1]);
        vector<int> mn(6, inf), mx(6, -inf);
        for (int j = i; j <= n; j++) {
            for (int k = 5; k; k--) {
                for (int p : {mn[k - 1], mx[k - 1]}) {
                    if (abs(p) < inf) {
                        if (k % 2) {
                            p -= a[j];
                        } else {
                            p *= a[j];
                        }
                        mn[k] = min(mn[k], p);
                        mx[k] = max(mx[k], p);
                    }
                }
            }
            mn[0] = min(mn[0], a[j]);
            mx[0] = max(mx[0], a[j]);
            f[j] = max(f[j], f[i - 1] + mx[5]);
        }
    }
    
    cout << f[n] << '\n';

    return 0;
}

G

枚举三角形的最上面那个点，然后用一个前缀和来看下面是否有一条线。

这个循环大概是 。

秒完全没有问题。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector sum(n, vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sum[i][j + 1] = sum[i][j] + (a[i][j] == '*');
        }
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '*') {
                int c = i + 1, l = j - 1, r = j + 1;
                while (c < n && l >= 0 && r < m && a[c][l] == '*' && a[c][r] == '*') {
                    ans += (sum[c][r + 1] - sum[c][l] == r + 1 - l);
                    l--, r++, c++;
                }
            }
        }
    }

    cout << ans << '\n';
    
    return 0;
}

H

可以使用树状数组。

找三角形右下角那个点。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <class T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int n = 0) : n(n), a(n, T()) {}
    void modify(int i, T x) {
        for (i++; i <= n; i += i & -i) {
            a[i - 1] += x;
        }
    }
    T get(int i) {
        T res = T();
        for (; i > 0; i -= i & -i) {
            res += a[i - 1];
        }
        return res;
    }
    T sum(int l, int r) {
        return get(r) - get(l);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    vector l(n + 1, vector<int>(m + 2)), r(n + 1, vector<int>(m + 2));

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '*') {
                l[i + 1][j + 1] = l[i][j] + 1;
                r[i + 1][j + 1] = r[i][j + 2] + 1;
            }
        }
    }

    vector f(2, Fenwick<int>(m));

    i64 ans = 0;
    for (int i = 1; i < n; i++) {
        vector<int> pre(m + 1);
        for (int j = m - 1; j >= 0; j--) {
            if (a[i][j] == '*') {
                pre[j] = pre[j + 1] + 1;
            }
        }

        vector<vector<int>> del(m);
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '*') {
                ans += f[j % 2].sum(j - l[i + 1][j + 1] * 2, m);
                f[j % 2].modify(j, +1);

                del[min(j + pre[j] - 1, j + r[i + 1][j + 1] * 2 - 2)].push_back(j);
                for (auto k : del[j]) {
                    f[k % 2].modify(k, -1);
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

J

计算几何，叉乘判三点共线，状压 dp。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using Point = complex<i64>;

auto cross(const Point &a, const Point &b) {
    return imag(conj(a) * b);
}

bool onLine(Point &a, Point &b, Point &c) {
    return cross(b - a, c - a) == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;

        a[i] = Point(x, y);
    }

    vector c(n, vector<int>(n));
    vector<int> f(1 << n, n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                for (int k = 0; k < n; k++) {
                    if (onLine(a[k], a[i], a[j])) {
                        c[i][j] |= 1 << k;
                    }
                }
            } else {
                c[i][j] |= 1 << i;
            }
            f[c[i][j]] = 1;
        }
    }

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                for (int j = 0; j < n; j++) {
                    f[mask | c[i][j]] = min(f[mask | c[i][j]], f[mask] + 1);
                }
            }
        }
    }

    cout << f[(1 << n) - 1] << '\n';

    return 0;
}