7-1 100...07是不是素数？
每个数暴力 \(O(\sqrt{v})\) 找最小质因子即可，时间复杂度 \(O(n\cdot \sqrt{v})\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;int min_p(ll x){if(x % 2 == 0) return 2;for(int i=3; 1ll*i*i<=x; i+=2){if(x % i == 0) return i;}return x;
}void solve(){int n;cin >> n;ll cur = 10;for(int k=0; k<=n; k++){int p = min_p(cur + 7);if(p == cur+7){cout << cur+7 << " is prime!\n";}else{cout << cur+7 << " factor=" << p << '\n';}cur *= 10;}
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; // cin >> t;while(t--) solve();return 0;
}
7-2 President's Office
先找 c，找到 c 之后去找周围的字母，找到就 dfs 把整个区域都标记为 true，ans++。
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;vector<pii> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void solve(){int n, m; char c;cin >> n >> m >> c;vector<vector<char>> mat(n + 2, vector<char>(m + 2, '.'));for(int i=1; i<=n; i++){string s; cin >> s;for(int j=1; j<=m; j++){mat[i][j] = s[j-1];}}int ans = 0;vector<vector<bool>> vis(n + 2, vector<bool>(m + 2));auto dfs = [&](auto&& self, int x, int y) ->void {vis[x][y] = true;for(int i=0; i<4; i++){int dx = moves[i].first, dy = moves[i].second;int nx = dx + x, ny = dy + y;if(!vis[nx][ny] && mat[nx][ny] == mat[x][y]){self(self, nx, ny);}}};for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(mat[i][j] != c) continue;for(int k=0; k<4; k++){int dx = moves[k].first;int dy = moves[k].second;int x = dx + i, y = dy + j;if(!vis[x][y] && mat[x][y] != c && mat[x][y] != '.'){dfs(dfs, x, y);ans++;}}}}cout << ans << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; //cin >> t;while(t--) solve();return 0;
}
7-3 L-shapes
找到 * 就 dfs，维护连通块中每个 * 的坐标，然后根据坐标判断形状是否合法，一共有 4 种合法情况，之后判断有没有别的连通块相邻
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;vector<pii> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
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++){string s; cin >> s;for(int j=1; j<=m; j++){mat[i][j] = s[j-1];}}vector<vector<bool>> vis(n + 2, vector<bool>(m + 2));// dfs 时 , 用 set 收集连通块的点set<pii> st;auto dfs = [&](auto&& self, int x, int y) ->void {vis[x][y] = true;st.insert({x, y});for(int i=0; i<4; i++){int dx = moves[i].first, dy = moves[i].second;int nx = dx + x, ny = dy + y;if(!vis[nx][ny] && mat[nx][ny] == '*'){self(self, nx, ny);}}};bool ok = true;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(!vis[i][j] && mat[i][j] == '*'){dfs(dfs, i, j);if(st.size() >= 4) ok = false; // 只能是 3 个方块// 这里取出的是 x 最小的那个点int x = (*st.begin()).first;int y = (*st.begin()).second;// 若不是这 4 种情况, 则为 falseif((st.count({x+1, y}) && st.count({x+1, y+1})) || (st.count({x+1, y}) && st.count({x+1, y-1})) ||(st.count({x, y+1}) && st.count({x+1, y+1})) ||(st.count({x+1, y}) && st.count({x, y+1}))){}else ok = false;// 检查是否和别的 L 相邻for(auto it : st){int cx = it.first, cy = it.second;for(int k=0; k<8; k++){int dx = moves[k].first, dy = moves[k].second;int nx = dx + cx, ny = dy + cy;if(mat[nx][ny] == '*' && !st.count({nx, ny})) ok = false;}}st.clear();}}}cout << (ok? "YES":"NO") << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; cin >> t;while(t--) solve();return 0;
}
7-4 h0324. 走方格
每一步要么往右走，要么往下走，直接 dfs 暴搜即可
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;void solve(){int n, m;cin >> n >> m;ll ans = 0;auto dfs = [&](auto&&self, int x, int y) ->void {if(x>n || y>m) return;if(x == n && y == m){ans++;return; }self(self, x+1, y);self(self, x, y+1);};dfs(dfs, 0, 0);cout << ans << '\n';}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; //cin >> t;while(t--) solve();return 0;
}
7-5 h0193. 排列
( 样例是每个数字后都有空格，题目竟然没说 )
进行 n 轮，每次都从没选的点中选择一个点，用 track 记录路径，回溯
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;constexpr int inf = 0x3f3f3f3f;void solve(){int n;cin >> n;vector<bool> used(n + 1);vector<int> track;auto dfs = [&](auto&& self, int x) ->void {if(x == n){for(int i=0; i<n; i++){cout << track[i] << ' ';}cout << '\n';return;}for(int i=1; i<=n; i++){if(used[i]) continue;used[i] = true;track.push_back(i);self(self, x+1);used[i] = false;track.pop_back();}};dfs(dfs, 0);}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; //cin >> t;while(t--) solve();return 0;
}
推荐直接 next_permutation
void solve(){int n;cin >> n;vector<int> a(n + 1);iota(a.begin(), a.end(), 0); // 递增赋值 , a = {0, 1, 2, ...}do{for(int i=1; i<=n; i++){cout << a[i] << " ";}cout << '\n';}while(next_permutation(a.begin()+1, a.end()));
}
7-6 h0115. 算24
把 4 个数放进一个数组里，每次取出两个数进行 + - * / 操作，将结果放入。重复操作，仅剩一个数时即为结果。因为设计 double 运算，判相等时最好使用 abs(A-B) <= eps 而不是直接 A == B
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;constexpr double eps = 1e-6;bool ed = false;
void solve(){vector<double> a(4);for(int i = 0; i < 4; i++) cin >> a[i];if(a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0){ed = true;return;}bool ok = false;auto dfs = [&](auto&& self, vector<double>& v) -> void {if(ok) return;int n = v.size();if(n == 1){if(fabs(v[0] - 24.0) < eps) ok = true;return;}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(i == j) continue;vector<double> nxt;for(int k = 0; k < n; k++){if(k != i && k != j) nxt.push_back(v[k]);}double x = v[i], y = v[j];// +nxt.push_back(x + y);self(self, nxt);nxt.pop_back();// -nxt.push_back(x - y);self(self, nxt);nxt.pop_back();// *nxt.push_back(x * y);self(self, nxt);nxt.pop_back();// /if(fabs(y) > eps){nxt.push_back(x / y);self(self, nxt);nxt.pop_back();}}}};dfs(dfs, a);cout << (ok ? "YES" : "NO") << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);while(!ed){solve();}return 0;
}
7-7 生命游戏II
根据题意模拟即可
#include <bits/stdc++.h>
using namespace std;int k, n;
vector<vector<int>> cur, nxt;
vector<vector<bool>> vis;int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> k >> n;cur.assign(n+2, vector<int>(n+2, 0));nxt.assign(n+2, vector<int>(n+2, 0));for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {cin >> cur[i][j];}}while(k--) {for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {nxt[i][j] = 0; // 默认边界为0}}for(int i = 2; i < n; i++) {for(int j = 2; j < n; j++) {int live = 0;for(int dir = 0; dir < 8; dir++) {int ni = i + dx[dir], nj = j + dy[dir];live += cur[ni][nj];}if(cur[i][j] == 1) {nxt[i][j] = (live == 2 || live == 3);} else {nxt[i][j] = (live == 3);}}}swap(cur, nxt);}// DFS 统计八连通块大小int cnt = 0;auto dfs = [&](auto&&self, int x, int y) ->void {vis[x][y] = true;cnt++;for(int dir = 0; dir < 8; dir++) {int nx = x + dx[dir], ny = y + dy[dir];if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && !vis[nx][ny] && cur[nx][ny] == 1) {self(self, nx, ny);}}};// DFS 统计最大连通块vis.assign(n+2, vector<bool>(n+2, false));int ans = 0;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(cur[i][j] == 1 && !vis[i][j]) {cnt = 0;dfs(dfs, i, j);ans = max(ans, cnt);}}}cout << ans << "\n";return 0;
}
7-8 L-朋友圈
题意：给你一个无向图，找连通块的个数和最大的连通块大小
使用邻接表存边，gra[u] 是一个数组 {v0, v1, v2...}，表示 u 和 v0, v1, v2... 有边
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;void solve(){int n, m;cin >> n >> m;vector<vector<int>> gra(n);for(int i = 0; i < m; i++){int u, v;cin >> u >> v;gra[u].push_back(v);gra[v].push_back(u);}vector<int> vis(n, 0);int cnt = 0; // 朋友圈个数int mx = 0; // 最大朋友圈人数int sz = 0;auto dfs = [&](auto&& self, int u) ->void {vis[u] = 1;sz++;for(int v : gra[u]){ // 遍历 u 的每条边if(!vis[v]){self(self, v);}}};for(int i = 0; i < n; i++){if(!vis[i]){sz = 0;cnt++;dfs(dfs, i);mx = max(mx, sz);}}cout << cnt << ' ' << mx << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}7-9 回溯法的通用伪代码（以分书问题为例）
#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n, m;cin >> n >> m; // m = 4vector<vector<int>> like(n + 1, vector<int>(m + 1));vector<int> used(m + 1), ans(n + 1);bool found = false;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> like[i][j];}}auto dfs = [&](auto&& self, int x) -> void {if(found) return;if(x > n){found = true;return;}for(int j = 1; j <= m; j++){ // 枚举第 i 个人拿了哪本书if(!like[x][j]) continue;if(used[j]) continue;used[j] = 1;ans[x] = j;self(self, x + 1);used[j] = 0;if(found) return;}};dfs(dfs, 1);if(found){cout << '(';for(int i = 1; i <= n; i++){if(i > 1) cout << ", ";cout << ans[i];}cout << ')';}
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}
7-10 被n整除的n位数
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;void solve(){int n;ll a, b;cin >> n >> a >> b;vector<ll> ans;auto dfs = [&](auto&& self, int pos, ll val) -> void {if(pos > n){ans.push_back(val);return;}int lo = (pos == 1 ? 1 : 0);for(int d = lo; d <= 9; d++){ll nv = val * 10 + d;if(nv % pos == 0){self(self, pos + 1, nv);}}};dfs(dfs, 1, 0);sort(ans.begin(), ans.end());bool ok = false;for(ll x : ans){if(x >= a && x <= b){cout << x << '\n';ok = true;}}if(!ok) cout << "No Solution" << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while(t--) solve();return 0;
}