嗨～我是可拟雀，一个全栈开发工程师，毕业于某985大学，目前供职于bat某大厂核心部门后端。每天分享最新面经答案，希望在大环境不好的当下能帮到你，让你多积累面试经验。免费分享个人学习2个月速通大厂路线（请看认证标）

其他群友有补充Java等语言版本请私信我加上去

先对输入字符串进行处理，然后再使用二维前缀和去统计子区域中1的个数，然后再逐步遍历k大小的子区域进行判断即可。

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

const int N = 1000;
int n;
char str[N][N];
int m[N][N], s[N][N];

int ans[N];

int GetPreSub(int x1, int y1, int x2, int y2) {
    return s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> str[i];
    
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (str[i][j] == '1') {
                m[i + 1][j + 1] = 1;
            } else {
                m[i + 1][j + 1] = 0;
            }
        }
    }
    
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j  ++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + m[i][j];
        }
    }
    for (int i = 0; i < n; i ++) { 
        for (int j = 0; j < n; j ++) {
            for (int k = 0; k < n; k ++) {
                if(i + k >= n || j + k >= n) {
                    break;
                }
                int sub = GetPreSub(i, j, i + k, j + k);
                if (sub * 2 == (k + 1) * (k + 1)) {
                    ans[k] ++;
                }
            }
        }
    }


    for (int i = 0; i < n; i ++) cout << ans[i] << endl;
    return 0;
}

T2

最大最小理所应当的是当未知数分别取l和r时成立。

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    long long tot = 0; 
    int numa = 0; 

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        tot += a[i];
        if (a[i] == 0) numa++;
    }

    while (q--) { 
        int l, r;
        cin >> l >> r;
        cout << numa * (long long)l + tot << " " << numa * (long long)r + tot << "\n";
    }

    return 0;
}

T3

先扫描一遍原本有n个M和T，然后总数减一下，剩下m个，再看可以添加k个，返回n+min(m,k)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans = 0;
    int tot = 0;

    for(int i = 0; i < n; i++) {
        char c = s[i];
        if(c != 'M' && c != 'T') {
            tot++;
        }
    }

    if(k >= tot) {
        cout << n << "\n";
    } else {
        cout << n - tot + k << "\n";
    }

    return 0;
}

T4

我们可以使用并查集（Union-Find）数据结构。并查集是处理不相交集合合并及查询问题的一种有效数据结构，非常适合用于解决动态连通性问题。在这个场景中，每个人可以看作一个节点，朋友关系可以看作是节点间的边。当两个人淡忘了他们的朋友关系时，我们就移除这条边；查询两个人是否能通过朋友介绍互相认识，实际上就是查询这两个节点是否在同一个连通分量中。

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

// 并查集类
class UnionFind {
private:
    unordered_map<int, int> parent; // 存储每个节点的父节点
    unordered_map<int, int> rank;   // 存储每个根节点的秩（用于优化）

public:
    // 查找节点x的根节点
    int find(int x) {
        if (parent.find(x) == parent.end()) parent[x] = x, rank[x] = 0; // 如果节点未出现过，初始化
        if (x != parent[x]) parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    // 将节点x和节点y所在的集合合并
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // 按秩合并，保持树的平衡
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                if (rank[rootX] == rank[rootY]) rank[rootX]++;
            }
        }
    }

    // 检查节点x和节点y是否连通
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

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

    int n, m, q;
    cin >> n >> m >> q;
    UnionFind uf;

    // 处理初始的朋友关系
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        uf.unite(u, v);
    }

    // 处理事件
    for (int i = 0; i < q; ++i) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) {
            // 如果是淡忘关系事件，由于题目要求仅在查询中使用，并查集操作不涉及“删除”操作，因此忽略
        } else if (op == 2) {
            // 如果是查询事件，输出查询结果
            cout << (uf.connected(u, v) ? "Yes" : "No") << '\n';
        }
    }

    return 0;
}

T5

首先，想要得到末尾是0就必须有一对2和5，简单的数学知识。使用前缀和+双指针，可以优化到O(n)复杂度。

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

// 寻找有多少个2
long long getTwoNum(long long x) {
    long long ct = 0;
    while (x % 2 == 0) {
        ct++;
        x /= 2;
    }
    return ct;
}

// 寻找有多少个5
long long getFiveNum(long long x) {
    long long ct = 0;
    while (x % 5 == 0) {
        ct++;
        x /= 5;
    }
    return ct;
}

int main() {
    long long n, k;
    while (cin >> n >> k) {
        vector<long long> arrsTwoNum(n, 0), arrsFiveNum(n, 0);
        long long totTwoNum = 0, totFiveNum = 0;
        for (long long i = 0; i < n; ++i) {
            long long x;
            cin >> x;
            arrsTwoNum[i] = getTwoNum(x);
            arrsFiveNum[i] = getFiveNum(x);
            totTwoNum += arrsTwoNum[i];
            totFiveNum += arrsFiveNum[i];
        }
        if (totTwoNum < k || totFiveNum < k) {
            cout << 0 << endl;
            return 0;
        }
        long long rangeMaxTwoNum = totTwoNum - k; // 最大可用删除的2的数量
        long long rangeMaxFiveNum = totFiveNum - k; // 最大可用删除的5的数量
        long long ans = 0;
        // 前缀和，统计到i为止2和5的数量
        for (long long i = 1; i < n; ++i) {
            arrsTwoNum[i] += arrsTwoNum[i - 1];
            arrsFiveNum[i] += arrsFiveNum[i - 1];
        }
        long long j = 0; // 快指针
        while (j < n && arrsTwoNum[j] <= rangeMaxTwoNum && arrsFiveNum[j] <= rangeMaxFiveNum) {
            j++;
        }
        ans += j; // 每次快指针使得段内2和5超标，更新一次ans
        for (long long i = 0; i < n; i++) {
            while (j < n && arrsTwoNum[j] - arrsTwoNum[i] <= rangeMaxTwoNum && arrsFiveNum[j] - arrsFiveNum[i] <= rangeMaxFiveNum) {
                j++;
            }
            ans += (j - i - 1);
        }
        cout << ans << endl;
    }
    return 0;
}