牛客刷题-2

1.小美的平衡矩阵

1.

小美的平衡矩阵

小美拿到了一个$n*n$的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个$i*i$的完美矩形区域。你需要回答$1\leq i \leq n$的所有答案。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入一个正整数，代表矩阵大小。
接下来的行，每行输入一个长度为的 01 串，用来表示矩阵。

输出描述：

输出行，第行输出的完美矩形区域的数量。

示例1

输入例子：

4
1010
0101
1100
0011

输出例子：

0
7
0
1

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> preSum(n, vector<int>(n+1));
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++) {
            preSum[i][j+1] = preSum[i][j] + (s[j] - '0');
        }
    }
    for(int window = 1; window <= n; window++) {
        if(window & 1) {
            cout << "0\n";
            continue;
        }
        int perfect = 0;
        for(int j = 0; j <= n - window; j++) {
            int sum = 0;
            for(int i = 0; i < window; i++) {
                sum += preSum[i][window + j] - preSum[i][j];
            }
            if(sum * 2 == window * window) {
                perfect++;
            }
            for(int i = window; i < n; i++) {
                sum -= preSum[i - window][window + j] - preSum[i - window][j];
                sum += preSum[i][window + j] - preSum[i][j];
                if(sum * 2 == window * window) {
                    perfect++;
                }
            }
        }
        cout << perfect << "\n";
    }
}

2.小美的数组询问

2.

小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间$[l,r]$范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
共有$q$次询问。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入两个正整数，代表数组大小和询问次数。
第二行输入个整数，其中如果输入的为 0，那么说明是未知的。
接下来的行，每行输入两个正整数 ，代表一次询问。

输出描述：

输出行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

示例1

输入例子：

3 2
1 0 3
1 2
4 4

输出例子：

5 6
8 8

例子说明：

只有第二个元素是未知的。
第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。
第二次询问，显然数组的元素和必然为 8。

#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    long long sum = 0;
    long long zeroCnt = 0;
    for(int i = 0; i < n; i++) {
        int ai;
        cin >> ai;
        zeroCnt += (ai == 0 ? 1 : 0);
        sum += ai;
    }
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << sum + zeroCnt*l << " " << sum + zeroCnt*r << "\n";
    }
}

3.小美的 MT

3.

小美的 MT

MT 是美团的缩写，因此小美很喜欢这两个字母。
现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作$k$次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个'M'和'T'字符？

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入两个正整数，代表字符串长度和操作次数。
第二行输入一个长度为的、仅由大写字母组成的字符串。

输出描述：

输出操作结束后最多共有多少个'M'和'T'字符。

示例1

输入例子：

5 2
MTUAN

输出例子：

4

例子说明：

修改第三个和第五个字符，形成的字符串为 MTTAM，这样共有 4 个'M'和'T'。

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int cnt = 0;
    cin.get();
    for(int i = 0; i < n; i++) {
        char c = cin.get();
        if(c != 'M' && c != 'T') cnt++;
    }
    cout <<  n - cnt + min(k, cnt) << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

4. 小美的朋友关系

#include <bits/stdc++.h>
using namespace std;

class UnionSet {
    vector<int> array;
    public:
    UnionSet(vector<set<int>> graph, int n): array(n) {
        iota(array.begin(), array.end(), 0);
        for(int u = 0; u < n; u++) {
            for(int v : graph[u]) {
                Union(u, v);
            }
        }
    }
    UnionSet(const vector<set<int>>& graph): UnionSet(graph, graph.size()) {}
    UnionSet(int n): array(n) {
        iota(array.begin(), array.end(), 0);
    }
    int Find(int u) {
        return u == array[u] ? u : (array[u] = Find(array[u]));
    }
    void Union(int u, int v) {
        array[Find(u)] = Find(v);
    }
    bool Query(int u, int v) {
        return Find(u) == Find(v);
    }
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<set<int>> graph(n);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        graph[u].insert(v);
        graph[v].insert(u);
    }
    vector<tuple<int, int, int>> ops;
    for(int i = 0; i < q; i++) {
        int op, u, v;
        cin >> op >> u >> v;
        u--;
        v--;
        ops.emplace_back(op, u, v);
        if(op == 1) {
            graph[u].erase(v);
            graph[v].erase(u);
        }
    }
    UnionSet unionSet(graph, n);
    vector<int> ans;
    for(auto ite = ops.rbegin(); ite != ops.rend(); ite++) {
        auto [op, u, v] = *ite;
        if(op == 1) {
            unionSet.Union(u, v);
        } else if(op == 2) {
            ans.push_back(unionSet.Query(u, v));
        }
    }
    for(auto ite = ans.rbegin(); ite != ans.rend(); ite++) {
        cout << (*ite ? "Yes\n" : "No\n");
    }
    return 0;
}

• 反向并查集，倒着计算答案
• 先把要删除的关系全部删除，然后倒序将删除的关系还原

5 小美的区间删除

5.

小美的区间删除

小美拿到了一个大小为$n$的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有$k$个 0。小美想知道，一共有多少种不同的删除方案？

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入两个正整数。
第二行输入个正整数，代表小美拿到的数组。

输出描述：

一个整数，代表删除的方案数。

示例1

输入例子：

5 2
2 5 3 4 20

输出例子：

4

例子说明：

第一个方案，删除[3]。
第二个方案，删除[4]。
第三个方案，删除[3,4]。
第四个方案，删除[2]。

#include <bits/stdc++.h>
using namespace std;

int cntOfFact(long long n, long long fact) {
    int cnt = 0;
    long long facts[32] = {0};
    int base = 0;
    facts[0] = fact;
    while(facts[base] < n) {
        base++;
        facts[base] = facts[base-1] * facts[base-1];
    }
    for(; base >= 0; base--) {
        if(n / facts[base] > 0 && n % facts[base] == 0) {
            cnt += 1 << base;
            n /= facts[base];
        }
    }
    return cnt;
}
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    vector<int> cntOf2(n+1), cntOf5(n+1);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        cntOf2[i+1] = cntOfFact(arr[i], 2) + cntOf2[i];
        cntOf5[i+1] = cntOfFact(arr[i], 5) + cntOf5[i];
    }
    int canDelete2 = cntOf2[n] - k;
    int canDelete5 = cntOf5[n] - k;
    int start = 0;
    long long ans = 0;
    for(int end = 1; end <= n; end++) {
        while(start < end && (cntOf2[end] - cntOf2[start] > canDelete2 || cntOf5[end] - cntOf5[start] > canDelete5)) {
            start++;
        }

        ans += end - start;
    }
    cout << ans << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")