9.13 百度笔试编程题题解

// 先占个坑，等笔试时间结束发。

1.  第一题没什么好说的，暴力枚举就行了。

小红拿到了一个字符串，她想知道有多少个 "baidu" 型子串，即第1，4个字母是辅音，其他字母是元音，且各字母均不相同。

#include <bits/stdc++.h>

using namespace std;
bool isVow(char c) {
    switch(c) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
        return true;
    }
    return false;
}
int main() {
    string s; cin >> s;
    const int n = s.length();

    int ans = 0;
    for (int i = 0; i < n-4; i++) {
        bool allDifferent = true;
        for (int j = i; j <= i+4; j++) {
            for (int k = j+1; k <= i+4; k++) {
                if (s[j] == s[k]) {
                    allDifferent = false;
                    break;
                }
            }
            if (!allDifferent) break;
        }
        if (allDifferent)
            ans += !isVow(s[i]) && isVow(s[i+1]) && isVow(s[i+2]) && !isVow(s[i+3]) && isVow(s[i+4]);
    }
    cout << ans << endl;
    return 0;
}

2.     给定一个01串，每次可以选择两个连续的数字取反（0变1， 1变0）。
能否在有限的操作次数内使所有字符相同

贪心。任意相邻的偶数个0或1，我们可以直接将其反转。而对于奇数个，我们可以反转到只剩下1个0或1。那么最终就只剩下形如 ...1.....1....1...（’.'为任意个0）或者...0...0.....0...0...（’.'为任意个1）的串。因为我们只能反转相邻的两个字符，所以我们要把这些1或者0变换到相邻的位置。假设两个1中间有n个0，即100...001，那么我们可以将最右边的两个字符反转，得到100...010，此时两个1中间有n-1个0，相当于把最右边的1往左移了一位。在经过n次反转移位之后，可以得到1100...00，再反转一次就得到全为0的串。（两个0中间有n个1的情况类似）。这说明了能够成功变换与字符0和字符1的位置无关，只与它们的数量有关。即如果给定串***有偶数个0，我们最终可以变换成全为1的串；如果有偶数个1，我们最终可以变换成全为0的串。

#include <iostream>

using namespace std;

bool ac(string &s) {
    int cnt = 0;
    for (char c : s) {
        cnt += c == '1';
    }
    return !(cnt&1) || !((s.length()-cnt)&1);
}
int main() {
    int q; cin >> q;
    while (q--) {
        string s;
        cin >> s;
        cout << (ac(s) ? "Yes" : "No") << endl;
    }
    return 0;
}

3. 就是BFS模板题加了个限制条件...

给定一个字符矩阵，矩阵仅由'r','e','d'组成。
求从左上角到右下角的最少步数。可以从上下左右四个方向走，但是不能从'r'->'d', 'e'->'r','d'->'e'。

#include <bits/stdc++.h>

using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<string> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    if (n == 1 && m == 1) {
        cout << 0 << endl;
        return 0;
    }
    vector<vector<bool>> vis(n, vector<bool>(m));
    vis[0][0] = true;
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    int step = 0;
    const int dx[]{-1, 0, 1, 0}, dy[]{0, -1, 0, 1};
    auto canGo = [] (char from, char to) -> bool {
        if (from == 'r' && to == 'd') return false;
        if (from == 'e' && to == 'r') return false;
        if (from == 'd' && to == 'e') return false;
        return true;
    };
    while (!q.empty()) {
        step ++;
        int sz = q.size();
        while (sz--) {
            auto p = q.front(); q.pop();
            int x = p.first, y = p.second;
            for (int i = 0; i < 4; i++) {
                int nx = x+dx[i], ny = y+dy[i];
                if (nx == n-1 && ny == m-1 && canGo(v[x][y], v[ny][ny])) {
                    cout << step << endl;
                    return 0;
                }
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && canGo(v[x][y], v[nx][ny])) {
                    vis[nx][ny] = true;
                    q.emplace(nx, ny);
                }
            }
        }
    }
    cout << -1 << endl;
    return 0;
}