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'。
求从左上角到右下角的最少步数。可以从上下左右四个方向走，但是不能从'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;
} 
