请不要原封不动的抄袭代码，尽量理解后自己写或者使用AI洗一下代码，本人代码很有特征。
第5关：素数环问题
把1到20这重新排列，使得排列后的序列A满足：
任意相邻两个数之和是素数
不存在满足条件1的序列B使得：A和B的前 $k$（$0 \le k \le 19$）项相同且B的第 $k+1$ 项比A的第 $k+1$ 项小。(即按字典序排列的第一项)
考虑直接暴力，使用next_permutation直接按照字典序枚举所有可能的结果，这样子时间复杂度 $O(n!)$，尽管给了20s依然难以通过
C++//Author: Alencryenfo
//Date: 2025-10-18 16:47:19
#include
#include
#include
#include
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair
int contain[] = {2,3,5,7,11,13,17,19,23,29,31,37};
bool check(const auto &a) {
for (int i = 0;i<19;i++) {
bool f = false;
for (int x:contain) {
if (a[i]+a[i+1] == x) {
f= true;
break;
}
}
if (f == false) return false;
}
return true;
}
void solve(){
vector
iota(a.begin(), a.end(), 1);
while (!check(a)) {
next_permutation(a.begin(), a.end());
}
for (int x: a) {
cout< if (x!=a[19])cout<<" "; } } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; T = 1; while(T--){ solve(); } return 0; } 考虑优化，可以通过一个时间复杂度为 $O(n^2)$ 的两两匹配将所有的相邻对的和统计出来，然后在将和为素数的两个数之间连边，这样就构成一个图，最后从1出发搜索字典序最小的哈密顿路径， 这样可以大幅减少时间。 哈密顿路径（Hamiltonian Path） 是指一条经过图中每一个顶点且仅经过一次的路径，如果这条路径的起点和终点还相连，形成了一个闭环（即首尾相接），则称为哈密顿回路（Hamiltonian Cycle）。 把顶点设为 $1..2m$，若两数和为素数则连边。由于奇数+偶数才可能得到奇素数（和=2 的情形用不到），图是二分图，路径必须奇偶交替。 我们从固定起点（如 1，奇数侧）做 DFS，并且每步在候选里按升序尝试，第一次找到就返回。 用“计数法”给出一个紧的最坏上界： 一条满足奇偶交替的长度 $2m$ 的排列，可以看成在“奇数位”放 $m$ 个奇数，在“偶数位”放 $m$ 个偶数： 起点固定为某个奇数（如 1），剩余奇数的排列数为 $(m-1)!$； 所有偶数的排列数为 $m!$； 因为我们只在“奇↔偶”之间走，任何可达路径的搜索树节点数不可能超过所有这类交替排列总数。 最坏时间复杂度严格上界： $$ \boxed{O\!\big(m!\cdot (m-1)!\big)} $$ 这里每一步扩展与回退的代价是 $O(1)$（邻接表已排序，used 为布尔数组），因此总时间与遍历的结点数同阶。 给出代码： C++//Author: Alencryenfo //Date: 2025-10-18 16:47:19 #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair int contain[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; bool vis[21]; auto check = [](int x)-> bool { for (int con: contain)if (con == x) return true; return false; }; bool dfs(int x, const auto &g, vector if (now.size() == 20 and check(now[0]+now[19])) { for (int i = 0; i < 20; i++) { cout << now[i]; if (i != 19) cout << " "; } return true; } for (auto nx: g[x]) { if (vis[nx] == false) { vis[nx] = true; auto nnow = now; nnow.push_back(nx); if (dfs(nx, g, nnow)==true)return true; vis[nx] = false; } } return false; } void solve() { vector for (int i = 1; i <= 20; i++) { for (int j = i + 1; j <= 20; j++) { if (check(i + j)) { g[i].push_back(j); g[j].push_back(i); } } } //构建图 for (int i = 1; i <= 20; i++) { sort(g[i].begin(), g[i].end()); } vis[1] = true; vector now.push_back(1); dfs(1, g, now); } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; T = 1; while (T--) { solve(); } return 0; } 第6关：迷宫问题 给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。 输入 多个测例。输入的第一行是一个整数 $n$，表示测例的个数。接下来是 $n$ 个测例，每个测例占21行，第一行四个整数 $x1，y1，x2，y2$ 是起止点的位置（坐标从零开始），$（x1，y1）$是起点，$（x2，y2$）是终点。下面20行每行20个字符，.表示空格；X表示墙。 输出 每个测例的输出占一行，输出Yes或No。 一个较为简单的搜索题，普通搜索时间复杂度 $O(n^2)$，给出代码： C++//Author: Alencryenfo //Date: 2025-10-18 17:45:47 #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair int dx[] = {+1, -1, 0, 0}, dy[] = {0, 0, -1, +1}; void solve() { int x1, y1, x2, y2,vis[20][20]; memset(vis,0,sizeof(vis)); vector cin >> x1 >> y1 >> x2 >> y2; for (int i = 0; i < 20; ++i) { cin >> g[i]; } queue bool f = false; nxt.emplace(x1, y1); vis[x1][y1] = true; while (!nxt.empty()) { auto [cx,cy] = nxt.front(); vis[cx][cy] = true; nxt.pop(); if (cx == x2 and cy == y2) { f = true; break; } else { for (int i = 0; i < 4; i++) { int nx = cx + dx[i], ny = cy + dy[i]; if (nx>=0 and nx<20 and ny>=0 and ny<20 and !vis[nx][ny] and g[nx][ny] == '.')nxt.emplace(nx,ny),vis[nx][ny] = true; } } } if (f == true)cout<<"Yes"<<"\n"; else cout<<"No"<<"\n"; } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin >> T; while (T--) { solve(); } return 0; } 第7关：踩气球 题意不清，注意两个人踩的气球是一样的，气球每个编号都只有一个。 六一儿童节，小朋友们做踩气球游戏，气球的编号是1～100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。 输入 输入为两个数字，0 0表示结束； 输出 输出为获胜的数字。 通过搜索判断真话假话即可，注意每种气球只有1个，给出代码 C++//Author: Alencryenfo //Date: 2025-10-18 18:19:14 #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair int contains[100]; bool check(int x, vector if (x == 1) { if (need1_end) { if (!vis[1]) { vis[1] = true; return true; } return false; } return true; } for (int i = 2; i <= 100; i++) { if (vis[i]) continue; if (x % i == 0) { vis[i] = true; if (check(x / i, vis, need1_end)) return true; vis[i] = false; } } return false; } void solve() { iota(std::begin(contains), std::end(contains), 1); while (true) { int x, y, ans = 0; cin >> x >> y; if (x == 0 and y == 0) return; int a = min(x, y), b = max(x, y); vector bool small_true = false; if (a == 1) { if (!vis[1]) { vis[1] = true; small_true = true; } } else { vector small_true = check(a, vis_small, false); if (small_true) vis = vis_small; } bool big_true = false; if (small_true) { vector big_true = (b == 1) ? (!vis_big[1] ? (vis_big[1] = true, true) : false) : check(b, vis_big, false); } else { if (b == 1) { vector big_true = !vis_full[1]; } else { vector big_true = check(b, vis_full, false); } } if (small_true && !big_true) ans = a; else ans = b; cout << ans << '\n'; } } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; T = 1; while (T--) { solve(); } return 0; } 第8关：字母转换 通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT到TORT: Plaintext[ i i i i o o o o i o i i o o i o ] 输入 给定两个字符串，第一个字符串是源字符串，第二个字符是目标目标字符串。 输出 所有的进栈和出栈序列,输出结果需满足字典序。 当栈为空时只有入栈操作，当待选字符串为空的时候只有出栈操作，当两者均非空的时候，有两个操作。 考虑记录已经出栈的字符来剪枝，同时先考虑出栈再考虑入栈，这样保证字典序的顺序。 时间复杂度 $O(2^n)$，给出代码： 注意每行末尾不要带空格 C++//Author: Alencryenfo //Date: 2025-10-18 21:47:33 #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair deque void dfs(stack int cur = lst.size() + rstr.size(); if (rstr.size() == s2.size()) { auto tmp = op; while (tmp.size()) { cout << tmp.front(); if (int(tmp.size()) != 1)cout<<" "; tmp.pop_front(); } cout << "\n"; return; } else { //in if (cur < s1.size()) { lst.push(s1[cur]); op.push_back('i'); dfs(lst, rstr, s1, s2); op.pop_back(); lst.pop(); } //out if (!lst.empty() and lst.top() == s2[rstr.size()]) { rstr.push_back(lst.top()); lst.pop(); op.push_back('o'); dfs(lst, rstr, s1, s2); op.pop_back(); rstr.pop_back(); } } } void solve() { string s1, s2; while (cin >> s1 >> s2) { cout << "[\n"; op.clear(); if (s1.size() == s2.size())dfs(stack cout << "]\n"; } } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; T = 1; while (T--) { solve(); } return 0; } 第9关：农场灌溉问题 输入 给出若干由字母表示的最大不超过50×50具体由 $(m，n)$ 表示的农场图。 输出 编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。 预处理每个字母可以到达的方向，然后遍历每未标记的点，遇到水渠就进入广度优先搜索完成联通部分扫描并且标记，进入广度优先搜索的次数就是答案。 注意水渠联通还要求所到达的水渠可以反向连通 时间复杂度 $O(n^2)$，给出代码： C++//Author: Alencryenfo //Date: 2025-10-18 22:39:45 #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair constexpr pii UP = {-1,0}, DOWN = {1,0}, LEFT = {0,-1}, RIGHT = {0,1}; vector {UP, LEFT}, {UP, RIGHT}, {LEFT, DOWN}, {RIGHT, DOWN}, {UP, DOWN}, {LEFT, RIGHT}, {UP, LEFT, RIGHT}, {UP, LEFT, DOWN}, {LEFT, DOWN, RIGHT}, {UP, DOWN, RIGHT}, {UP, LEFT, DOWN, RIGHT} }; bool check(int nex,int dx,int dy) { for (auto [x,y] : f[nex]) if (x==dx && y==dy) return true; return false; } void solve() { while (true) { int m, n, ans = 0; cin >> m >> n; if (m == -1 and n == -1) return; vector vector for (int i = 0; i < m; i++) { string tmp; cin >> tmp; for (int j = 0; j < n; j++)g[i][j] = tmp[j] - 'A'; } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (vis[i][j])continue; ans++; queue nxt.emplace(i, j); vis[i][j] = true; while (!nxt.empty()) { auto [x,y] = nxt.front(); nxt.pop(); for (auto [dx,dy]: f[g[x][y]]) { int nx = x + dx, ny = y + dy; if (nx >= 0 and nx < m and ny >= 0 and ny < n and vis[nx][ny] == false and check(g[nx][ny],-dx,-dy)) { nxt.emplace(x + dx, y + dy); vis[x + dx][y + dy] = true; } } } } } cout << ans << "\n"; } } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T = 1; while (T--) { solve(); } return 0; } 第10关：求图像的周长 给一个用.和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边长。 输入 首先给出 $m$、$n$、$x$、$y$ 四个正整数，下面给出 $m×n$ 的图形，$x$、$y$ 表示点击的位置，全 $0$ 表示结束。 输出 点击的图形的周长。 注意到，每个X贡献的边长为 4-X的上、下、左、右的X的数目，对于点击到的位置直接广度优先搜索就能解决。 时间复杂度 $O(mn)$，给出代码： C++//Author: Alencryenfo //Date: 2025-10-18 23:51:43 #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair int dx[] = {+1, -1, 0, 0}, dy[] = {0, 0, -1, +1}, pdx[] = {+1, -1, +1, -1}, pdy[] = {+1, -1, -1, +1}; void solve() { while (true) { int m, n, x, y, ans = 0; cin >> m >> n >> x >> y; if (m == 0 and n == 0 and x == 0 and y == 0)return; x--, y--; //转为0-base vector vector for (int i = 0; i < m; i++) { cin >> g[i]; } queue q.emplace(x, y); vis[x][y] = true; while (!q.empty()) { auto [cx, cy] = q.front(); q.pop(); //ans for (int k = 0; k < 4; k++) { int nx = cx + dx[k], ny = cy + dy[k]; if (nx < m and nx >= 0 and nx < m and ny >= 0 and ny < n and g[nx][ny] == '.') ans++; else if (!(nx < m and nx >= 0 and nx < m and ny >= 0 and ny < n)) ans++; } //nxt for (int k = 0; k < 4; k++) { int nx = cx + pdx[k], ny = cy + pdy[k]; if (nx < m and nx >= 0 and nx < m and ny >= 0 and ny < n and vis[nx][ny] == false and g[nx][ny] == 'X') { q.emplace(nx, ny); vis[nx][ny] = true; } } for (int k = 0; k < 4; k++) { int nx = cx + dx[k], ny = cy + dy[k]; if (nx < m and nx >= 0 and nx < m and ny >= 0 and ny < n and vis[nx][ny] == false and g[nx][ny] == 'X') { q.emplace(nx, ny); vis[nx][ny] = true; } } } cout << ans << "\n"; } } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T = 1; while (T--) { solve(); } return 0; } 第11关：图的m着色问题 给定无向连通图 $G$ 和 $m$ 种不同的颜色。用这些颜色为图 $G$ 的各顶点着色，每个顶点着一种颜色。如果有一种着色法使 $G$ 中每条边的2个顶点着不同颜色，则称这个图是 $m$ 可着色的。图的 $m$ 着色问题是对于给定图 $G$ 和 $m$ 种颜色，找出所有不同的着色法。 输入 第1行有3个正整数 $n$，$r$ 和 $m$（$n < 20$,$r < 200$,$m < 10$），表示给定的图 $G$ 有 $n$ 个顶点和 $r$ 条边，$m$ 种颜色。顶点编号为 $0$，$1$，$2$，$…$，$n-1$。接下来的 $r$ 行中，每行有2个正整数 $u,v$，表示图 $G$ 的一条边 $(u,v)$。 输出 输出不同的着色方案的总数。 由于这是一个普通的无向连通图，一种朴素的方法是直接深度优先搜索，考虑优化剪枝: 首先，我们考虑从度数最多的开始搜索，这样可以显著降低搜索树的规模 考虑每一次节点可以选择的染色合法性判断，最简单的方法是做一个 $O(n^2)$ 的匹配，注意到这个颜色数目非常有限，可以考虑通过位运算减少匹配时间复杂度，通过位运算OR可以在时间复杂度 $O(n)$ 得到所有不可选的颜色，在对每一点都维护不可选的颜色，即可优化 本题还可以通过位压缩DP与快速子集卷积优化至时间复杂度 $O(m\cdot n^2\cdot 2^n)$ 时间复杂度 $O(m^n)$，给出代码： C++//Author: Alencryenfo //Date: 2025-10-19 00:20:41 #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair void dfs(int idx, const vector const vector vector int n, int m, long long &ans) { if (idx == n) { ++ans; return; } int u = order[idx]; int full_mask = (m >= 16) ? 0xFFFFu : (int) ((1 << m) - 1); int avail = (int) (full_mask & (int) ~forbid[u]); if (avail == 0) return; // 逐颜色尝试 for (int c = 0; c < m; ++c) { int bit = (int) (1 << c); if ((avail & bit) == 0) continue; // 前向：给 u 用颜色 c，则所有邻居禁用 c vector for (int v = 0; v < n; ++v) { if (adj[u] & (1 << v)) { if ((forbid[v] & bit) == 0) { forbid[v] = (int) (forbid[v] | bit); changed.push_back(v); } } } dfs(idx + 1, adj, order, forbid, n, m, ans); // 回溯 for (int v: changed) forbid[v] = (int) (forbid[v] ^ bit); } } void solve() { int n, r, m; cin >> n >> r >> m; vector for (int i = 0; i < r; i++) { int u, v; cin >> u >> v; adj[u] |= (1 << v); adj[v] |= (1 << u); } // 顶点顺序：按度数降序 vector for (int i = 0; i < n; ++i) order[i] = i; sort(order.begin(), order.end(), [&](int a, int b) { int da = 0, db = 0; for (int v = 0; v < n; ++v) { if (adj[a] & (1 << v)) ++da; } for (int v = 0; v < n; ++v) { if (adj[b] & (1 << v)) ++db; } if (da != db) return da > db; return a < b; }); vector long long ans = 0; dfs(0, adj, order, forbid, n, m, ans); cout << ans << "\n"; } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; T = 1; while (T--) { solve(); } return 0; } 第12关：三阶幻方 三阶幻方是最简单的幻方，又叫九宫格，是由1,2,3,4,5,6,7,8,9九个数字组成的一个三行三列的矩阵，其对角线、横行、纵向的的和都为15。 输出 按字典序输出所有的满足条件的幻方矩阵，每两个数字之间带一个空格，行尾无空格，每个幻方后带一个空行。 简单题，给出代码 C++ //Author: Alencryenfo //Date: 2025-10-19 01:18:21 #include using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair int g[3][3], vis[10]; bool check() { // 行 for (int i = 0; i < 3; ++i) { int s = 0; for (int j = 0; j < 3; ++j) s += g[i][j]; if (s != 15) return false; } // 列 for (int j = 0; j < 3; ++j) { int s = 0; for (int i = 0; i < 3; ++i) s += g[i][j]; if (s != 15) return false; } // 对角线 int d1 = g[0][0] + g[1][1] + g[2][2]; int d2 = g[0][2] + g[1][1] + g[2][0]; return d1 == 15 && d2 == 15; } void dfs(int x, int y) { if (x >= 3) { if (check()) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cout << g[i][j]; if (j != 2) cout << " "; } cout<<"\n"; } cout << "\n"; } } else { for (int i = 1; i <= 9; i++) { if (vis[i] == true) continue; vis[i] = true; g[x][y] = i; if (y == 2)dfs(x + 1, 0); else dfs(x, y + 1); vis[i] = false; g[x][y] = 0; } } } void solve() { dfs(0, 0); } signed main() { #ifdef DEBUG freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; T = 1; while (T--) { solve(); } return 0; } 本文章只发布在泣语，未经作者书面许可不得转载。