搜索进阶
A - 滑雪
题目链接
思路
搜索模板题无需多说，注意一下记忆化搜索和剪枝
代码
#include#include using namespace std; const int N = 1005; typedef pair<int, int> PII; int n, m, dis[N][N], s[N][N]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int dfs(int i, int j) { if (dis[i][j] != 0) return dis[i][j]; dis[i][j]=1; for (int l = 0; l < 4; l++) { int x = i + dx[l]; int y = j + dy[l]; if (x >= 1 && x <= n && y >= 1 && y <= n && s[i][j] > s[x][y]) dis[i][j] = max(dfs(x, y) + 1, dis[i][j]); } return dis[i][j]; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> s[i][j]; int mas = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) mas = max(dfs(i, j), mas); cout<<mas; return 0; }
B - Dungeon Master
题目链接
题意
一个三维的迷宫问题
思路
三维于二维迷宫问题只是多了上下两个搜索方向，其余没有什么不同
代码
#include#include <string.h> #include using namespace std; #define maxn 100 struct node { int x, y, z, step; }; int h, m, n; //高，长和宽 // 6个方向可以走 int dir[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}; char G[maxn][maxn][maxn]; int OK(int z, int x, int y) //判断这点是否可以走 { if (z >= 0 && z < h && x >= 0 && x < m && y >= 0 && y < n && G[z][x][y] != '#') return 1; return 0; } int DFS(node s, node e) { queue Q; Q.push(s); while (Q.size()) { s = Q.front(); Q.pop(); if (s.x == e.x && s.y == e.y && s.z == e.z) return s.step; for (int i = 0; i < 6; i++) { node q = s; q.x += dir[i][0]; q.y += dir[i][1]; q.z += dir[i][2]; q.step += 1; if (OK(q.z, q.x, q.y) == 1) { G[q.z][q.x][q.y] = '#'; Q.push(q); } } } return -1; } int main() { while (scanf("%d%d%d", &h, &m, &n), h + m + n) { int i, j, k; node s, e; for (i = 0; i < h; i++) for (j = 0; j < m; j++) { scanf("%s", G[i][j]); for (k = 0; k < n; k++) { if (G[i][j][k] == 'S') { s.z = i; s.x = j; s.y = k; s.step = 0; } if (G[i][j][k] == 'E') { e.z = i; e.x = j; e.y = k; } } } int ans = DFS(s, e); if (ans != -1) printf("Escaped in %d minute(s).\n", ans); else printf("Trapped!\n"); } return 0; }
C - 8 Puzzle on Graph
题目链接
题意
给一个 3 x 3 的表格从上到下位置编号为 1~3，4~6，7~9，将1~8 共8个数放入其中，给予一系列的移动规则，如 1 - 2 指编号为1的格子可以于编号为2的格子互换，互换时必须有一个格子为空。问是否能将数字移到对应编号上，如果可以输出至少移动几步，不可以输出 -1
思路
想明白题意花了好长时间，注意题目给的初始状态是指第几个数在哪个位置 比如
3 9 2 4 5 6 7 8
1 在 编号 3
2 在 编号 9
. . .
以此类推
明白了题意接下来就简单了，只要从空白格子开始广搜就行了，用字符串表示不同状态同时标记避免重复
代码
#includeusing namespace std; map<string, int> ma; int vis[10][10]; vector<int> q[10]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int a, b; cin >> a >> b; q[a - 1].push_back(b - 1); q[b - 1].push_back(a - 1); } string s = "999999999"; for (int i = 1; i <= 8; i++) { int a; cin >> a; s[a-1] = i + '0'; } queue<string> e; e.push(s); ma[s] = 0; while (!e.empty()) { string s1 = e.front(); e.pop(); if (s1 == "123456789") { cout << ma[s1]; return 0; } int k; for (int i = 0; i < 9; i++) if (s1[i] == '9') k = i; for (int i = 0; i < q[k].size(); i++) { string sc = s1; swap(sc[k], sc[q[k][i]]); if (ma[sc] == 0) { ma[sc] = ma[s1] + 1; e.push(sc); } } } cout << -1; return 0; }
D - Subtree K-th Max
题目链接
题意
n 个数，q 个询问
接下来一行 n 个数：xi 表示第 i 个点的权值是 xi
接下来 n ? 1 行，每行两个数 a , b ，表示 a 和 b 之间有一条边
接下来 q 行，每行两个数 a , b ，问以 a 为根节点的子树中所有节点权值的第 b大是多少。
思路
从1开始搜索，每到一个节点记录以这个节点为根节点的前20大（因为 1<=b<=20，所以记录20个就够了）
然后对每个查询就可以直接输出
代码
#includeusing namespace std; const int N = 100233; int sa[N]; vector<int> q[N]; vector<int> w[N]; bool cmp(int a, int b) { return a > b; } void dfs(int t, int p)//t为根结点，p为其父节点 { w[t].push_back(sa[t]); for (auto x : q[t]) { if (x == p)//避免重复 continue; dfs(x,t); for (auto y : w[x]) w[t].push_back(y); } sort(w[t].begin(), w[t].end(), cmp); if (w[t].size() > 20) w[t].resize(20); } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> sa[i]; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; q[a].push_back(b); q[b].push_back(a); } dfs(1, 0); for (int i = 1; i <= m; i++) { int a, k; cin >> a >> k; cout << w[a][k - 1] << endl; } return 0; }