3.9 美团笔试

24年第一次笔试...

T1, 模拟

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

int main() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int current = 0;
    for (auto c : s) {
        if (c == 'M' || c == 'T') current++;
    }
    int res = min(int(s.length()), current+k);
    cout << res << endl;
    return 0;
}

T2，模拟

注意数据范围，使用long

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, q; cin >> n >> q;
    long tmp, zeroCnt = 0, nonZeroSum = 0;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        if (tmp == 0) {
            zeroCnt++;
        } else {
            nonZeroSum += tmp;
        }
    }
    while (q--) {
        long l, r;
        cin >> l >> r;
        cout << nonZeroSum + zeroCnt*l << ' ' << nonZeroSum+zeroCnt*r << endl;
    }
    return 0;
}

T3，二维前缀和

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n; cin >> n;
    vector<string> mat(n);
    for (int i = 0; i < n; i++) cin >> mat[i];
    int pre[205][205]{};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pre[i+1][j+1] =  pre[i+1][j] + pre[i][j+1] - pre[i][j] + (mat[i][j]=='1');
        }
    }
    for (int len = 1; len <= n; len++) {
        if (len % 2 == 1) {
            cout << 0 << endl;
            continue;
        }
        int current = 0, target = len*len/2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int endI = i+len-1,  endJ =j+len-1;
                if (endI > n-1 || endJ > n-1) continue;
                int val = pre[endI+1][endJ+1] - pre[endI+1][j] - pre[i][endJ+1] + pre[i][j];
                if (val == target) current++;
            }
        }
        cout << current << endl;
    }
    return 0;
}

T4，前缀和 + 滑动窗口

(注意数据范围, 使用long)

思路：

• 给出的数字都是不为0的，最终乘积的0 一定是由素因子 2, 5构成的， 因此主要关心区间内2、5的数量
• 要求删除区间后0的数量应该大于等于k，即删除区间后剩下的数中 素因子2、5的数量必须同时大于等于k

滑动窗口： 枚举以i开始的可以删除的子串数量，for循环内部while结束后, i-j对应的子串是不符合条件的，但i到 [i+1、i+2、 ... j-1]都是满足条件的。

复杂度 O(n)

#include<bits/stdc++.h>

using namespace std;

const int MaxN = 1e5+5;
int main() {
    int n, k; cin >> n >> k;
    int arr[n];
    long pre2[MaxN]{}, pre5[MaxN]{};
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        int cntFactor2 = 0, cntFactor5 = 0;
        for (int x = arr[i]; x % 2 == 0; x /= 2) cntFactor2++;
        for (int x = arr[i]; x % 5 == 0; x /= 5) cntFactor5++;
        pre2[i+1] += pre2[i] + cntFactor2;
        pre5[i+1] += pre5[i] + cntFactor5;
    }

    long res = 0, zeroCnt = min(pre2[n], pre5[n]);
    for (int i = 0, j = 0; i < n; i++) {
        while (j < n) {
            int range2 = pre2[j+1] - pre2[i];
            int range5 = pre5[j+1] - pre5[i];
            int remain2 = pre2[n] - range2;
            int remain5 = pre5[n] - range5;
            if (min(remain2, remain5) < k) break;
            j++;
        }
        res += max(j-i, 0);
    }
    cout << res << endl;
    return 0;
}

T5, 并查集、离散化、逆向思维

笔试时想到了并查集，但没写出来，写了个dfs，超时～

笔试后参考@Y丶bs大佬的思路使用并查集实现了下。 ref: https://www.nowcoder.com/discuss/596124837462978560

并查集写法

#include <bits/stdc++.h>

using namespace std;
const int MaxN = 4e5+5;
int fa[MaxN];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    int faX = find(x);
    int faY = find(y);
    if (faX != faY) {
        fa[faX] = faY;
    }
}

int main() {
    iota(fa, fa+MaxN, 0);   // 初始化fa数组
    unordered_set<int> points;  // 记录所有点, 离散化使用
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> edges;
    for (int i = 0; i < m; i++) {
        int a, b;  cin >> a >> b;

        points.insert(a);
        points.insert(b);
        edges.push_back({a, b});
    }

    unordered_map<int, unordered_set<int>> delEdgeMap;
    vector<vector<int>> ops; 
    while (q--) {
        int op, u, v; cin >> op >> u >> v;

        points.insert(u);
        points.insert(v);
        ops.push_back({op, u, v});
        if (op == 1) {
            delEdgeMap[u].insert(v);
            delEdgeMap[v].insert(u);
        } 
    }

    int idx = 0;    // 离散化初始idx
    unordered_map<int, int> val2Idx;
    for (auto u : points) val2Idx[u] = idx++;

    // 建立并查集、不使用删除的边
    for (auto &e : edges) {
        int u = e[0], v = e[1]; 
        if (delEdgeMap.count(u) && delEdgeMap[u].count(v)) {
            continue;
        }

        merge(val2Idx[u], val2Idx[v]);
    }

    vector<bool> result;
    reverse(ops.begin(), ops.end());  // 反向遍历
    for (auto &item : ops) {
        int op = item[0], u = item[1], v = item[2];
        int idxU = val2Idx[u], idxV = val2Idx[v];
        if (op == 1) {  // 加边操作
            merge(idxU, idxV);
            continue;
        }

        if (find(idxU) == find(idxV)) {
            result.push_back(true);
        } else {
            result.push_back(false);
        }
    }
    for (int i = result.size()-1; i >= 0; i--) {
        if (result[i]) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }

    return 0;
}

暴力dfs解法(超时...)

#include <bits/stdc++.h>

using namespace std;
int n, m, q;
unordered_map<int, unordered_map<int, bool>> g;

bool dfs(int u, int parent, int target) {
    if (u == target) {
        return true;
    }
    for (auto &[v, ok] : g[u]) {
        if (v != parent && ok && dfs(v, u, target)){
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        g[a][b] = true;
        g[b][a] = true;
    }
    while (q--) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) {
            g[u][v] = false;
            g[v][u] = false;
            continue;
        } 
        if (dfs(u, -1, v)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}