牛客周赛39

A 小红不想做炸鸡块粉丝粉丝题

void solve() {
    int a[6] = {};
    cin >> a[0];
    int cnt = 0;
    for (int i = 1;i < 6;i++)cin >> a[i], cnt += a[i];
    if (a[0] < cnt / 30) cout << "Yes\n";
	else cout << "No\n";
}

B 小红不想做鸽巢原理

小红有 $n$ 种不同颜色的小球，第 $i$ 种颜色的小球有 $a_i$ 个，放在同一个盒子中。

小红每次任意取出 $k$ 个小球并丢弃，直到盒子中剩余的球数小于 $k$ 个为止。

小红希望最终盒子里的小球颜色种类尽可能少，你能帮小红求出颜色的种类数量吗？

从前往后遍历，若刚好抵消，则这时的颜色可以是 0 个，否则是当前颜色，每当前进一步就加一个颜色

#define int long long
void solve() {
    int n, k;cin >> n >> k;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());

    int cnt = 0, ans = 0;
    for (int i = 1;i <= n;i++) {
        cnt += a[i];
        ans++;
        if (cnt >= k) {
            if (cnt % k == 0) {
                ans = 0;
            } else {
                ans = 1;
            }
            cnt -= k;
        }

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

C/D 小红不想做完全背包

完全背包是一个经典问题，但小红完全不会完全背包，所以她不想做完全背包。

现在小红得到了一个长得很像完全背包的题目，她希望你帮她解决一下。

给定一个背包，有 $n$ 种物品，每种物品的价值为 $a_i$，有无穷多个。小红有一个无穷大的背包，她希望往里面放若干个物品，从而最终所有物品的价值之和为 $p$ 的倍数。

至少要放多少物品？（注意：不能不放物品）

• Easy:$p=3$
• Hard: $1\le p\le 2000$

Solution

Easy

void solve() {
    int n, p;cin >> n >> p;
    int a[3] = {};
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;a[x % 3]++;
    }
    if (a[0]) cout << "1\n";
    else if (a[1] && a[2]) cout << "2\n";
    else cout << "3\n";return;
}

Hard

DP (待更 $\dots$)/广搜？39->C&D

void solve() {
    int n, p;cin >> n >> p;
    vector<int> f(p, p), a(n + 1);

    for (int i = 1;i <= n;i++) {
        cin >> a[i];a[i] %= p;f[a[i]] = 1;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j < p;j++) {
            f[(a[i] + j) % p] = min(f[(a[i] + j) % p], f[j] + 1);
        }
    }
    cout << f[0] << '\n';
}

E 小红不想做莫比乌斯反演杜教筛求因子和的前缀和

小紅來到了一家蛋糕店，蛋糕店中售賣了若干種不同的長方體蛋糕，具體來說，蛋糕店中售賣若干種形狀為橫向長度不大於 $n$，縱向長度不大於 $m$，高度不大於 $p$ 個單位的蛋糕。每個蛋糕的表面要裹上奶油，也就是說，除了底面以外，其餘 5 個面都需要裹奶油。我們不妨定義：奶油消耗量為暴露在空氣中的 5 個面的面積之和。

我們定義兩種蛋糕是不同的，當且僅當兩個蛋糕的橫向或者縱向長度或高度不同。即分別定義蛋糕橫向的長度為 $i$，縱向的長度為 $j$，高度為 $k$，則可以用三元組 $(i,j,k)$ 表示蛋糕種類的唯一性。

現在小紅希望你求出，共有多少種不同的奶油消耗量為 $x$ 的蛋糕？

知道了长和宽，又知道了消耗量 $x$，则这时的高度 $k$ 也能够计算出来，只需要看 $k$ 是否满足相应要求即可。

void solve() {
    int n, m, p, x;cin >> n >> m >> p >> x;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            int k = (x - i * j) / (2 * (i + j));
            if (k <= p && k >= 1 && (x - i * j) % (2 * (i + j)) == 0) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

F 小红不想做模拟题

给你两个长度大小为 $n$ 的 01 串 A, B（指字符串的字符都为'0'和'1'）。
现在小红有若干次操作，每次选择一个 01 串的一个区间，将区间内所有字符都变成全 1。
每次操作后，小红希望你求出两个字符串有多少个位置的对应字符都是 1。用数学语言来说，即求你能帮帮她吗？

Solution

线段树
(待更 $\dots$)

constexpr ll N = 1e5 + 10;
struct Node {
    ll sum[2], ans;
    ll tag[2];
}tr[N << 2];
ll n, q;
string s[2];

void pushup(ll p) {
    tr[p].ans = tr[lc].ans + tr[rc].ans;
    for (ll k : {0, 1})
        tr[p].sum[k] = tr[lc].sum[k] + tr[rc].sum[k];
}

void pushnow(ll p, ll l, ll r, ll ty) {
    tr[p].ans = tr[p].sum[ty ^ 1];
    tr[p].sum[ty] = r - l + 1;
    tr[p].tag[ty] = 1;
}

void pushdown(ll p, ll l, ll r) {
    for (ll ty : {0, 1})
        if (tr[p].tag[ty]) {
            pushnow(lc, l, mid, ty);
            pushnow(rc, mid + 1, r, ty);
            tr[p].tag[ty] = 0;
        }
}

void build(ll p, ll l, ll r) {
    if (l == r) {
        for (ll k : {0, 1})
            tr[p].sum[k] = s[k][l];
        tr[p].ans = s[0][l] & s[1][l];
        return;
    }
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(p);
}

void update(ll p, ll l, ll r, ll ql, ll qr, ll ty) {
    if (ql <= l && r <= qr) {
        pushnow(p, l, r, ty);
        return;
    }
    pushdown(p, l, r);
    if (ql <= mid)	update(lc, l, mid, ql, qr, ty);
    if (qr > mid)	update(rc, mid + 1, r, ql, qr, ty);
    pushup(p);
}

void solve() {
    cin >> n;
    for (ll k : {0, 1}) {
        cin >> s[k];s[k] = " " + s[k];
        for (ll i = 1;i <= n;++i)
            s[k][i] -= '0';
    }
    build(1, 1, n);
    cin >> q;

    while (q--) {
        ll l, r;
        char op;
        cin >> op >> l >> r;
        update(1, 1, n, l, r, op == 'B');
        cout << tr[1].ans << '\n';
    }
}

G 小红不想做平衡树

小红定义一个数组为“好数组”，当且仅当这个数组可以恰好翻转一个区间后变成升序。例如：$[1,4,3,2,7]$是好数组。

现在小红拿到了一个排列，她想知道这个排列有多少连续子数组是好数组？

Solution

(待更 $\dots$)