4月10日 字节笔试题解

T1 简单模拟

思路一

我们只需考虑每块陆地周围的海洋个数。

思路二

如果陆地变成海洋之后可以再次影响陆地，那么这就是一道 BFS 标准题。给出AC代码：

#include <bits/stdc++.h>

using namespace std;

int m, n;

#define getx(x) (x / n)
#define gety(x) (x % n)
#define inBound(x, y) (x >= 0 && x < m && y >= 0 && y < n)

void solve() {
    cin >> m >> n;
    vector<string> g(m);
    for (int i = 0; i < m; ++i) {
        cin >> g[i];
    }
    queue<int> q;
    vector<vector<bool>> vis(m, vector<bool>(n));
    vector<vector<int>> power(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j) {
        if (g[i][j] == '0') {
            q.push(i*n+j);
            vis[i][j] = 1;
        }
    }
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto f = q.front(); q.pop();
        auto x = getx(f), y = gety(f);
//         cout << "front = " << x << ", " << y << endl;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            int no = nx * n + ny;
            if (inBound(nx, ny) && g[nx][ny] == '1' && power[nx][ny] < 2) {
                power[nx][ny]++;
                if (power[nx][ny] >= 2) {
                    g[nx][ny] = '0';
                }
            }
        }
    }
    for (int i = 0; i < m; ++i) cout << g[i] << endl;
}
int main() {
    int T = 0;
    cin >> T;
    while (T--) {
        solve();
    }


    return 0;
}

T2 贪心机器人

我们只需要维护一个机器人可以达到的最远距离即可。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> energy(n);
    for (int i = 0; i < n; ++i) {
        cin >> energy[i];
    }
    int farthest = 0;
    for (int i = 0; i < n; ++i) {
        if (farthest < i) break;
        int nxt = i + energy[i];
        if (nxt > farthest) farthest = nxt;
    }
    if (farthest >= n-1) cout << "TRUE" << endl;
    else cout << "FALSE" << endl;
    return 0;

}

T4 凑成卡组的最少购买次数

这道题需要一些必备知识：位运算操作集合，状态压缩dp，子集枚举

思路

由于我们最后只需要凑成一套卡组（0~9 十种卡），因此我们考虑在选择第 个商品时，已经有的卡组为 ，考虑第 个商品可以贡献的卡为 （, 均为集合），最后的卡组集合将会是：

这样，我们在考虑选择第 个商品时，枚举集合 , 并记录当前状态下的最少要选 个商品。怎么更新 呢？

由于我们选择了第 个商品，并且其能贡献的卡组为 , 因此我们可以在 中减去 的所有子集(包括自己），这些状态集合为 、..., ，那么转移方程将会是：

有了转移方程就可以轻松写出代码啦（已AC)，下面给出代码：

#include <bits/stdc++.h>

using namespace std;

#define all (1 << 10)
#define INF 0x3f3f3f3f
vector<string> cards;

int solve() {
    int m = cards.size();
    vector<int> f(all, INF), g(all, INF);
    g[0] = 0;
    for (int i = 1; i <= m; ++i) {
        auto& card = cards[i-1];
        int code = 0;
        for (auto c : card) {
            int idx = c - '0';
            code |= (1 << idx);
        }
        for (int j = 0; j < all; ++j) {
            f[j] = g[j];
            if ((j & code) != code) continue;
            // j 可以由 j ^ sub 转移得到
            int sub = code;
            while (sub) {
                f[j] = min(f[j], g[j^sub]+1);
                sub = (sub-1)&code;
            }
        }
        swap(f, g);
    }
    if (g[all-1] >= INF) return -1;
    else return g[all-1];
}

int main() {
    string s;

    while (cin >> s) {
        cards.push_back(s);
    }

    cout << solve() << endl;

    return 0;
}