< gc; i++) {if (gcd(p[g[i]], p[idx]) > 1) return false;}return true;}void dfs(int g, int gc, int tc, int start) {if (g >= ans) return;if (tc == N) {ans = g;return;}bool flag = true;for (int i = start; i < N; i++) {if (!vis[i] && check(group[g], gc, i)) {flag = false;vis[i] = true;group[g][gc] = i;dfs(g, gc + 1, tc + 1, i + 1);vis[i] = false;}}if (flag) dfs(g + 1, 0, tc, 0);}int main() {scanf("%d", &N);for (int i = 0; i < N; i++) scanf("%d", &p[i]);dfs(1, 0, 0, 0);printf("%d\n", ans);return 0;}
6. 167. 木棒
#include#include#include#includeusing namespace std;const int maxn = 70;int w[maxn], N, length, sum;bool vis[maxn];bool dfs(int u, int s, int start) {if (length * u == sum) return true;if (s == length) return dfs(u + 1, 0, 0);for (int i = start; i < N; i++) {if (vis[i]) continue;if (s + w[i] > length) continue;vis[i] = true;if (dfs(u, s + w[i], i + 1)) return true;vis[i] = false;if (s == 0) return false;if (s + w[i] == length) return false;int j = i;while (j < N && w[i] == w[j]) j++;i = j - 1;//注意这里，因为马上要i++了，千万别写成i = j 。}return false;}int main() {while (cin >> N, N) {memset(vis, false, sizeof vis);//注意，当一个length行不通的时候，vis都会被回溯成false的 。sum = 0;for (int i = 0; i < N; i++) {cin >> w[i];sum += w[i];}sort(w, w + N, greater());for (length = 1; ; length++) {if (sum % length == 0 && dfs(0, 0, 0)) {cout << length << endl;break;}}}return 0;}
7. 181. 回转游戏
15adb54fa5e62901814118aa1791edcb
#include#include#includeusing namespace std;int op[8][7]{{0, 2, 6, 11, 15, 20, 22},{1, 3, 8, 12, 17, 21, 23},{10, 9, 8, 7, 6, 5, 4},{19, 18, 17, 16, 15, 14, 13},{23, 21, 17, 12, 8, 3, 1},{22, 20, 15, 11, 6, 2, 0},{13, 14, 15, 16, 17, 18, 19},{4, 5, 6, 7, 8, 9, 10}};int opposite[8] = { 5, 4, 7, 6, 1, 0, 3, 2 };int center[8] = { 6, 7, 8, 11, 12, 15, 16, 17 };int q[24], path[100];int f() {int sum[4] = {0};for (int i = 0; i < 8; i++) sum[q[center[i]]]++;int s = 0;for (int i = 1; i <= 3; i++) s = max(s, sum[i]);return 8 - s;}void operate(int id) {int head = q[op[id][0]];for (int i = 0; i < 6; i++) q[op[id][i]] = q[op[id][i + 1]];q[op[id][6]] = head;}bool dfs(int depth, int max_depth, int last) {if (depth + f() > max_depth) return false;if (f() == 0) return true;for (int i = 0; i < 8; i++) {if (opposite[i] != last) {operate(i);path[depth] = i;if (dfs(depth + 1, max_depth, i)) return true;operate(opposite[i]);}}return false;}int main() {while (scanf("%d", &q[0]) && q[0]) {for (int i = 1; i < 24; i++) scanf("%d", &q[i]);int depth = 0;while (!dfs(0, depth, -1)) depth++;if (!depth) printf("No moves needed\n");else {//再次提醒！！ 一定要小心这个输出，循环到 depth - 1 就行！for (int i = 0; i < depth; i++) printf("%c", path[i] + 'A');printf("\n");}printf("%d\n", q[center[1]]);}return 0;}
二、BFS 1. 八数码
queue> que;unordered_map, int> d;int dx[] = { 0, 0, -1, 1 }, dy[] = { 1, -1, 0, 0 };string st, ed("12345678x");int bfs() {d[st] = 0;que.push(st);while (que.size()) {auto s = que.front(); que.pop();int dis = d[s];if (s == ed) return dis;int k = s.find('x');int x = k / 3, y = k % 3;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;swap(s[x * 3 + y], s[nx * 3 + ny]);if (!d.count(s)) {d[s] = dis + 1;que.push(s);}swap(s[nx * 3 + ny], s[x * 3 + y]);}}return -1;}
2. 1107. 魔板
#includeusing namespace std;queue> que;unordered_map, int> d;map, pair, char> > pre;int dx[] = { 0, 0, -1, 1 }, dy[] = { 1, -1, 0, 0 };string st("12345678"), ed;int bfs() {d[st] = 0;que.push(st);pre[st].first = "-1";while (que.size()) {auto s = que.front(); que.pop();if (s == ed) return d[s];string t = s;swap(t[0], t[7]), swap(t[1], t[6]), swap(t[2], t[5]), swap(t[3], t[4]);if (!d.count(t)) {d[t] = d[s] + 1;que.push(t);pre[t] = make_pair(s, 'A');}t = s;swap(t[3], t[2]), swap(t[2], t[1]), swap(t[1], t[0]);swap(t[4], t[5]), swap(t[5], t[6]), swap(t[6], t[7]);if (!d.count(t)) {d[t] = d[s] + 1;que.push(t);pre[t] = make_pair(s, 'B');}t = s;char c = t[1];t[1] = t[6], t[6] = t[5], t[5] = t[2], t[2] = c;if (!d.count(t)) {d[t] = d[s] + 1;que.push(t);pre[t] = make_pair(s, 'C');}}}int main() {char c;for (int i = 0; i