注册网站不用手机短信验证的,近三天发生的国际新闻,深圳做网站多少,北京建设商业网站文章目录
排书回转游戏 一、排书OJ链接 本题思路:先考虑每一步的决策数量#xff1a;当抽取长度为 i 的一段时#xff0c;有 n−i1 种抽法#xff0c;对于每种抽法#xff0c;有 n−i 种放法。另外#xff0c;将某一段向前移动#xff0c;等价于将跳过的那段向后移动当抽取长度为 i 的一段时有 n−i1 种抽法对于每种抽法有 n−i 种放法。另外将某一段向前移动等价于将跳过的那段向后移动因此每种移动方式被算了两遍所以每个状态总共的分支数量是∑ni1(n−i)∗(n−i1)/2(15∗1414∗13…2∗1)/2560。考虑在四步以内解决最多有 5604个状态会超时。可以使用双向BFS或者IDA*来优化。我们用IDA*来解决此题。 估价函数 估价函数需要满足不大于实际步数 在最终状态下每本书后面的书的编号应该比当前书多1。 每次移动最多会断开三个相连的位置再重新加入三个相连的位置因此最多会将3个错误的连接修正所以如果当前有 tot个连接那么最少需要 ⌈tot/3⌉次操作。因此当前状态 s的估价函数可以设计成 f(s)⌈tot/3⌉。如果当前层数加上 f(s)大于迭代加深的层数上限则直接从当前分支回溯。
#include bits/stdc.hconstexpr int N20;int n;
int q[N], w[5][N];int f()
{int res 0;for (int i 0; i 1 n; i )if (q[i 1] ! q[i] 1)res ;return (res 2) / 3;
}bool check()
{for (int i 0; i n; i )if (q[i] ! i 1)return false;return true;
}bool dfs(int depth, int max_depth)
{if (depth f() max_depth) return false;if (check()) return true;for (int l 0; l n; l )for (int r l; r n; r )for (int k r 1; k n; k ){memcpy(w[depth], q, sizeof q);int x, y;for (x r 1, y l; x k; x , y ) q[y] w[depth][x];for (x l; x r; x , y ) q[y] w[depth][x];if (dfs(depth 1, max_depth)) return true;memcpy(q, w[depth], sizeof q);}return false;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T;std::cinT;while (T -- ){std::cinn;for (int i 0; i n; i ) std::cinq[i];int depth 0;while (depth 5 !dfs(0, depth)) depth ;if (depth 5) std::cout5 or morestd::endl;else std::coutdepthstd::endl;}return 0;
}二、回转游戏OJ链接 本题思路:本题采用 IDA* 算法即迭代加深的 A* 算法。
估价函数
统计中间8个方格中出现次数最多的数出现了多少次记为 k 次。 每次操作会从中间8个方格中移出一个数再移入一个数所以最多会减少一个不同的数。 因此估价函数可以设为 8−k。 剪枝
记录上一次的操作本次操作避免枚举上一次的逆操作。 如何保证答案的字典序最小
由于最短操作步数是一定的因此每一步枚举时先枚举字典序小的操作即可。 时间复杂度假设答案最少需要 k 步每次需要枚举 7 种不同操作除了上一步的逆操作因此最坏情况下需要枚举 7^k种方案。但加入启发函数后实际枚举到的状态数很少。
#include bits/stdc.hconst int N 24;int q[N];
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 center[8] {6, 7, 8, 11, 12, 15, 16, 17};
int opposite[8] {5, 4, 7, 6, 1, 0, 3, 2};int path[100];int f()
{static int sum[4];memset(sum, 0, sizeof sum);for (int i 0; i 8; i ) sum[q[center[i]]] ;int s 0;for (int i 1; i 3; i ) s std::max(s, sum[i]);return 8 - s;
}bool check()
{for (int i 1; i 8; i )if (q[center[i]] ! q[center[0]])return false;return true;
}void operation(int x)
{int t q[op[x][0]];for (int i 0; i 6; i ) q[op[x][i]] q[op[x][i 1]];q[op[x][6]] t;
}bool dfs(int depth, int max_depth, int last)
{if (depth f() max_depth) return false;if (check()) return true;for (int i 0; i 8; i ){if (opposite[i] last) continue;operation(i);path[depth] i;if (dfs(depth 1, max_depth, i)) return true;operation(opposite[i]);}return false;
}int main()
{while (std::cinq[0],q[0]){for (int i 1; i N; i ) std::cinq[i];int depth 0;while (!dfs(0, depth, -1)){depth ;}if (!depth) std::coutNo moves needed;for (int i 0; i depth; i ) std::cout(char)(A path[i]);std::coutstd::endl q[6]std::endl;}return 0;
}
