牛客周赛37

A 雾之湖的冰精

a + b > 9? "No" : "Yes";

B 博丽神社的巫女

小红发现博丽神社门口有一个赛钱箱，里面有若干个巫女。每个巫女在收到不同数量的金币后会感到开心。小红希望尽可能多的巫女感到开心，同时保留尽可能多的金币。请帮忙计算她可以让多少个巫女开心，以及最多可以剩下多少金币。

void solve() {
    int n, x;cin >> n >> x;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    int cnt = 0, s = x;
    for (int i = 1;i <= n;i++) {
        if (x >= a[i]) {
            cnt++;
            s = min(s, x - a[i]);
        }
    }
    cout << cnt << " " << s << '\n';
}

C 红魔馆的馆主

现在，小红拿到了一个正整数，她想在这个正整数的结尾增加尽可能少的数字，使得该数字变成 495 的倍数。请你给出任意一个添加方案。

void solve() {
    ll x;cin >> x;
    if (x % 495 == 0) {
        cout << "-1\n";return;
    }
    int y = x % 495;
    for (ll i = 495;;i += 495) {
        string s = to_string(i), s2 = to_string(y);
        if (s.substr(0, s2.size()) == s2) {
            cout << s.substr(s2.size()) << "\n";return;
        }
    }
}

D 迷途之家的大贤者

小红一开始还没穿越多久就被大贤者小紫发现了，然后小紫友好地邀请小红来迷途之家做客。在那里他们玩了一个游戏：两人轮流操作字符串，小红希望最后生成的字符串尽可能大，而小紫希望尽可能小。他们不能删除整个字符串，只能操作子串。在最优策略下，最后生成的字符串是什么呢？

cout << max(s[0], s[s.size() - 1]) << '\n';

E 魔法之森的蘑菇

小红迷路了，在魔法森林里有一些会让人幻觉的毒蘑菇。森林用一个 $n$ 行 $m$ 列的矩阵表示。
小红不能转弯直到她遇到蘑菇。她可以选择向一个方向转弯或者继续直走，不能掉头。
现在她想知道，从 S 到 T 点的最短步数是多少？

请注意，小红初始的前进方向可以任意选择。

Solution

BFS

int dx[] = {1, -1,0,0};
int dy[] = {0, 0,-1,1};
char g[1010][1010];
int vis[1010][1010], dis[1010][1010][4];
void solve() {
    int n, m, xx, yy;cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            for (int k = 0;k < 4;k++)
                dis[i][j][k] = 1e9;
        }
    }
    queue<array<int, 3>> q;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> g[i][j];
            if (g[i][j] == 'S') {
                for (int k = 0;k < 4;k++) {
                    q.push({i,j,k});dis[i][j][k] = 0;
                }
            }
            if (g[i][j] == 'T') {
                xx = i, yy = j;
            }
        }
    }

    while (q.size()) {
        auto [x, y, z] = q.front();q.pop();
        if (g[x][y] == '.' || g[x][y] == 'T' || g[x][y] == 'S') {
            int cx = x + dx[z], cy = y + dy[z];
            if (cx < 1 || cx>n || cy < 1 || cy > m || g[cx][cy] == '#')continue;
            if (dis[cx][cy][z] > dis[x][y][z] + 1) {
                q.push({cx,cy,z});
                dis[cx][cy][z] = dis[x][y][z] + 1;
            }
        } else if (g[x][y] == '*') {
            for (int i = 0;i < 4;i++) {
                if ((i ^ z) == 1)continue;
                int cx = x + dx[i], cy = y + dy[i];
                if (cx < 1 || cx > n || cy<1 || cy>m || g[cx][cy] == '#')continue;
                if (dis[cx][cy][i] > dis[x][y][z] + 1) {
                    q.push({cx,cy,i});
                    dis[cx][cy][i] = dis[x][y][z] + 1;
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 0;i < 4;i++) {
        ans = min(ans, dis[xx][yy][i]);
    }
    if (ans == 1e9)ans = -1;
    cout << ans << '\n';
}

F 三途川的摆渡人

小红这天来到了三途川，发现这里有一个摆渡人，名字叫小町。
小町的职责是将一些灵魂运送到冥界。每个灵魂有一个特性，用整数表示。但小町非常喜欢偷懒，她只想运送尽可能少的灵魂然后摸鱼。
已知当船上所有灵魂特性的位与运算正好等于 0 时，船才可以开动。小町想让小红帮忙抛弃掉尽可能多的灵魂（但不能全抛弃），这样自己才能最大限度的偷懒。请你帮小红计算出可以抛弃的灵魂的最多数量。

Solution

状压DP

(待更 $\dots$)

void solve() {
    int n;cin >> n;
    array<int, 130> m = {};
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;m[x] = 1;
    }
    vector<array<int, 2>> dp(130, {n + 1,n + 1});
    for (int i = 0;i < 130;i++) {
        if (m[i]) {
            dp[i][1] = 1;
            for (int j = 0;j < 130;j++) {
                dp[i & j][1] = min(dp[i & j][1], dp[j][0] + 1);
            }
            for (int j = 0;j < 130;j++) {
                dp[j][0] = dp[j][1];
            }
        }
    }
    if (dp[0][0] > n) {
        cout << "-1\n";return;
    }
    cout << n - dp[0][0] << '\n';
}