1-1 小朱爱
签到题，按题意数一下即可，注意 \ 的输出要用 \\
#include<bits/stdc++.h>
using namespace std;void solve(){string str;getline(cin,str);int cnt=0;for(int i=0;i<str.size();i++){if(str[i]=='l'||str[i]=='I'){cnt++;}}for(int i=1;i<=cnt;i++){cout<<'\\';}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);int t=1;//cin >> t;while(t--){solve();}return 0;
}
1-2 括号完美匹配
签到，可以用 vector 模拟栈，遇到左括号放入，遇到右括号尝试匹配即可。注意最后栈为空才是真正匹配完
#include <bits/stdc++.h>
using namespace std;void solve(){int n; string s;cin >> s;vector<char> stk;for(auto c : s){if(c == '(' || c == '[') stk.push_back(c);else if(c == ')'){if(stk.empty() || stk.back() != '('){cout << "no" << '\n';return;}else stk.pop_back();}else if(c == ']'){if(stk.empty() || stk.back() != '['){cout << "no" << '\n';return;}else stk.pop_back();}}if(!stk.empty()){cout << "no" << '\n';return;}cout << "yes" << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; cin >> t;while(t--) solve();return 0;
}
1-3 跳一跳 (升级版)
求最小跳跃次数，考虑 BFS，用 mp 记录某值的所有下标。用 vis1[i] 标记 i 的最小到达时间，同时还需要用 vis2 标记某值是否用过第三种转送方式
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;constexpr int inf = 0x3f3f3f3f;void solve(){int n;cin >> n;vector<int> a(n);map<int, vector<int>> idx; // v , vector<int>for(int i = 0; i < n; i++) {cin >> a[i];idx[a[i]].push_back(i);}vector<int> vis1(n, inf);set<int> vis2; // xqueue<pii> q;q.push({0, 0});while(!q.empty()){auto[x, y] = q.front(); q.pop(); // c++ 17 语法 , 不能用可替换成 first , secondif(vis1[x] != inf) continue;vis1[x] = y;if(x == n-1) break;q.push({x+1, y+1}); // 1if(x) q.push({x-1, y+1}); // 2if(!vis2.count(a[x])){ // 3for(int i : idx[a[x]]){q.push({i, y+1});}vis2.insert(a[x]);}}cout << vis1[n-1] << '\n';}int main(){solve();
}
1-4 马走日
枚举马所有可以走的方式，BFS 暴搜即可
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;constexpr int inf = 0x3f3f3f3f;int dx[8] = {1,2,2,1,-1,-2,-2,-1};
int dy[8] = {2,1,-1,-2,2,1,-1,-2};struct Node{int x, y, step;
};void solve(){int n, m, sx, sy, tx, ty;cin >> n >> m >> sx >> sy >> tx >> ty;vector<vector<int>> vis(n, vector<int>(m, 0));queue<Node> q;q.push({sx, sy, 0});vis[sx][sy] = 1;int ans = inf;while(!q.empty()){auto [x, y, step] = q.front(); q.pop();if(x == tx && y == ty){ans = step;break;}for(int i = 0; i < 8; i++){ int nx = x + dx[i];int ny = y + dy[i];if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]){vis[nx][ny] = 1;q.push({nx, ny, step+1});}}}cout << ans << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;// cin >> t;while(t--) solve();return 0;
}
1-5 小红的大蘑菇
直接暴力把非安全区域标记出来，然后正常跑 BFS 即可
#include <bits/stdc++.h>
using namespace std;constexpr int INF = 0x3f3f3f3f;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};struct Node{int x, y, d;
};void solve(){int n, m;cin >> n >> m;vector<vector<char>> mat(n+2, vector<char>(m+2, '#'));for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin >> mat[i][j];}}vector<vector<int>> bad(n+2, vector<int>(m+2));/* 暴力标记不安全区域 */for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){if(mat[i][j] == '*'){for(int dx = -1; dx <= 1; dx++){for(int dy = -1; dy <= 1; dy++){if(abs(dx) + abs(dy) > 1) continue;bad[i+dx][j+dy] = 1;}}}if(mat[i][j] == '#'){for(int dx = -2; dx <= 2; dx++){for(int dy = -2; dy <= 2; dy++){if(i+dx < 0 || i+dx > n || j+dy < 0 || j + dy > m) continue;if(abs(dx) + abs(dy) > 2) continue;bad[i+dx][j+dy] = 1;}}}}}/* 起点 / 终点检查 */if(bad[1][1] || bad[n][m]){cout << -1 << '\n';return;}/* BFS 走安全空地 */vector<vector<bool>> vis(n+2, vector<bool>(m+2));queue<Node> q;q.push({1, 1, 0});vis[1][1] = true;while(!q.empty()){auto [x,y,d] = q.front(); q.pop();if(x == n && y == m){cout << d << '\n';return;}for(int k = 0;k < 4;k++){int nx = x + dx[k];int ny = y + dy[k];if(vis[nx][ny] || bad[nx][ny] || mat[nx][ny] != '.') continue;vis[nx][ny] = true;q.push({nx,ny,d+1});}}cout << -1 << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();
}
1-6 回家
例题原题，在讲课 pdf 里面
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;int n, m;
struct man{int x, y, hp;
};int bfs(auto& mat, int Sx, int Sy){queue<man> q;vector<vector<int>> vis(n+2, vector<int> (m+2, 0)); // 当 hp 大于原来, 则可以再走此格vector<pii> moves = {{-1,0},{1,0},{0,1},{0,-1}};q.push({Sx, Sy, 6});vis[Sx][Sy] = 6;int depth = 0; // 记录最短路径while(!q.empty()){int sz = q.size();for(int i=0; i<sz; i++){int cx = q.front().x;int cy = q.front().y;int chp = q.front().hp;q.pop();if(chp == 0) continue;if(mat[cx][cy] == 3) return depth; // 找到家直接 returnif(mat[cx][cy] == 4){ // 捡到 鼠标? 回满hpchp = 6;}for(auto& mo : moves){int nx = mo.first + cx;int ny = mo.second + cy;int nhp = chp - 1;if(nhp <= vis[nx][ny] || mat[nx][ny] == 0) continue;vis[nx][ny] = nhp;q.push({nx, ny, nhp});}}depth++;}return -1;
}int main(){int Sx, Sy;cin >> n >> m;vector<vector<int>> mat(n+2, vector<int>(m+2, 0));for(int r=1; r<=n; r++){for(int c=1; c<=m; c++){cin >> mat[r][c];if(mat[r][c] == 2){Sx = r;Sy = c;}}}int ans = bfs(mat, Sx, Sy);cout << ans << '\n';
}
1-7 Nightmare II
先跑一遍 npy 的 BFS，在跑一遍 erriyue 的 BFS，记录到某格的最短时间。或者说直接按时间模拟。可以计算曼哈顿距离，来计算鬼是否在某个时间扩散到某格
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};void solve() {int n, m;cin >> n >> m;vector<vector<char>> mat(n + 2, vector<char>(m + 2, 'X'));vector<vector<bool>> vis1(n + 2, vector<bool>(m + 2)), vis2 = vis1;for (int i = 1; i <= n; i++) {string row; cin >> row;for (int j = 1; j <= m; j++) {mat[i][j] = row[j - 1];}}queue<pii> q1, q2;vector<pii> ghosts;for(int i=1; i<=n; i++){for(int j=1; j<=m ;j++){if(mat[i][j] == 'M') q1.push({i, j}); // 男if(mat[i][j] == 'G') q2.push({i, j}); // 女if(mat[i][j] == 'Z') ghosts.push_back({i, j}); // 鬼}}// 检查某个点在 time 秒时是否安全// 鬼在 time 秒的覆盖半径是 2 * timeauto is_safe = [&](int x, int y, int time)->bool {for (auto z : ghosts) {if(abs(x - z.first) + abs(y - z.second) <= 2 * time){return false;}}return true;};// q: 当前人物的队列// steps: 这一秒可以走的步数 (Boy=3, Girl=1)// vis: 当前人物的访问数组int time = 0;auto bfs = [&](queue<pii> &q, int steps, vector<vector<bool>>& vis)->bool {for (int k = 0; k < steps; k++) {int sz = q.size(); // 当前层的节点数，保证只扩展一层，也就是一步一步走while (sz--) {int x = q.front().first, y = q.front().second;q.pop();if(!is_safe(x, y, time)){continue;}for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];if (!is_safe(nx, ny, time) || mat[nx][ny]=='X') continue;if (vis[nx][ny]) continue;vis[nx][ny] = true;if(vis1[nx][ny] && vis2[nx][ny]) return true; // 两人相遇q.push({nx, ny});}}}return false;};// 时间模拟// 只要还有人能动，就继续模拟while (!q1.empty() || !q2.empty()) {time++;// Erriyue 动 3 步if (bfs(q1, 3, vis1)) {cout << time << '\n';return;}// Girl 动 1 步if (bfs(q2, 1, vis2)) {cout << time << '\n';return;}}cout << -1 << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;if (!(cin >> t)) return 0;while (t--) solve();return 0;
}
1-8 连通块的权
裸 BFS，也可以直接 DFS
#include <bits/stdc++.h>
using namespace std;using ll = long long;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};void solve(){int n, m;cin >> n >> m;vector<vector<int>> mat(n+2, vector<int>(m+2));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> mat[i][j];}}vector<vector<bool>> vis(n+2, vector<bool>(m+2, false));ll ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(mat[i][j] == 0 || vis[i][j]) continue;ll sum = 0;queue<pair<int,int>> q;q.push({i, j});vis[i][j] = true;while(!q.empty()){auto [x, y] = q.front(); q.pop();sum += mat[x][y];for(int k = 0; k < 4; k++){int nx = x + dx[k];int ny = y + dy[k];if(vis[nx][ny] || mat[nx][ny] == 0) continue;vis[nx][ny] = true;q.push({nx, ny});}}ans = max(ans, sum);}}cout << ans << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T--) solve();
}
1-9 选数
暴搜即可，这道题 DFS，BFS 实现都行，本质没什么区别。每个位置选或不选，时间复杂度 \(O(2^n)\)
BFS 实现
#include <bits/stdc++.h>
using namespace std;using ll = long long;bool isprime(int x){if(x <= 1) return false;for(int i = 2; i * i <= x; i++)if(x % i == 0) return false;return true;
}struct Node{int cnt; // 已选元素数量int sum; // 当前和int pos; // 下一轮可以选择的起始下标
};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;vector<int> a(n);for(int i = 0; i < n; i++) cin >> a[i];ll ans = 0;queue<Node> q;q.push({0, 0, 0});while(!q.empty()){auto [cnt, sum, pos] = q.front(); q.pop();if(cnt == k){if(isprime(sum)) ans++;continue;}for(int i = pos; i < n; i++){q.push({cnt + 1, sum + a[i], i + 1});}}cout << ans << '\n';
}
DFS 实现
#include <iostream>
#include <cstdio>
using namespace std;
bool isprime(int a){if(a == 1) return false;for(int i = 2; i * i <= a; i++)if(a % i == 0)return false;return true;
}int n,k;
int a[25];
long long ans;void dfs(int m, int sum, int startx){if(m == k){if(isprime(sum))ans++;return ;}for(int i = startx; i < n; i++)dfs(m + 1, sum + a[i], i + 1);return ;
}int main(){scanf("%d%d",&n,&k);for(int i = 0; i < n; i++)scanf("%d",&a[i]);dfs(0, 0, 0);printf("%d\n",ans);return 0;
}
1-10 夺宝大赛
题解
#include<bits/stdc++.h>
using namespace std;#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef pair<int, int> pii;
const int N = 110, M = 5010;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};int n, m, q, sx, sy, g[N][N], d[N][N];
pii des[M];void bfs(){queue<pii> q;q.emplace(sx, sy);d[sx][sy] = 0;while(q.size()){auto [x, y] = q.front();q.pop();for(int k = 0; k < 4; k ++ ){int nx = x + dx[k], ny = y + dy[k];if(nx < 1 || ny < 1 || nx > n || ny > m) continue;if(!g[nx][ny] || ~d[nx][ny]) continue;q.emplace(nx, ny);d[nx][ny] = d[x][y] + 1;}}
}int main(){ios;cin >> n >> m;memset(d, -1, sizeof d);for(int i = 1; i <= n; i ++ )for(int j = 1; j <= m; j ++ ){cin >> g[i][j];if(g[i][j] == 2) sx = i, sy = j;}cin >> q;for(int i = 1, x, y; i <= q; i ++ ) cin >> x >> y, des[i] = {y, x};bfs();unordered_map<int, int> cnt; // 每个距离有多少个队伍for(int i = 1; i <= q; i ++ ){auto [x, y] = des[i];cnt[d[x][y]] ++ ;}int mn = 1e9, ans = -1;for(int i = 1; i <= q; i ++ ){auto [x, y] = des[i];if(d[x][y] == -1 || cnt[d[x][y]] > 1) continue;if(d[x][y] < mn) mn = d[x][y], ans = i;}if(ans == -1) cout << "No winner." << "\n";else cout << ans << ' ' << mn << "\n";return 0;
}