搜索训练
1.HDU 2208
给小朋友分组，两两小朋友都喜欢对方才能分一组（因此既不是并查集，也不是强连通），数据多小啊，搜索先来一发。
更好的思路是root[i]=J 表示i属于j组，找到每个root[i]==i的与新元素判断是否都在集合中，是就加入或不加入，不是就新产生一组。
我还是比较喜欢用STL
#include <cstdio> #include <vector> using namespace std; int G[13][13]; int n, m; bool flag; vector<int> part[22]; void dfs(int num, int team) { if (flag) return; if (team > m) return; if (num == n) { flag = 1; return; } for (int i = 0; i < team; i++) { int j; for (j = 0; j < part[i].size(); j++) if (!G[num][part[i][j]]) break; if (j == part[i].size()) { part[i].push_back(num); dfs(num + 1, team); part[i].pop_back(); } if (flag) break; } part[team].clear(); part[team].push_back(num); dfs(num + 1, team + 1); } int main() { // freopen("data3.txt", "r", stdin); int tn, j; while (~scanf("%d%d", &n, &m)) { flag = 0; memset(G, 0, sizeof(G)); for (int i = 0; i < n; i++) { part[i].clear(); scanf("%d", &tn); while (tn--) { scanf("%d", &j); G[i][j] = 1; } } part[0].push_back(0); dfs(1, 1); if (flag) puts("YES"); else puts("NO"); } return 0; }
2.HDU 1258
这个太简单了，主要是去重就是可以一个一个选，但只要开始不选，相同的后面就都不能选了
#include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> ans; int cnt; int n, tot, num[1009]; void dfs(int pos, int sum) { if (sum > tot) return; if (sum == tot) { cnt++; printf("%d", ans[0]); for (int i = 1; i < ans.size(); i++) printf("+%d", ans[i]); puts(""); return; } if (pos >= n) return; ans.push_back(num[pos]); dfs(pos + 1, sum + num[pos]); ans.pop_back(); while (pos + 1 < n && num[pos] == num[pos + 1]) pos++; dfs(pos + 1, sum); } int main() { // freopen("data3.txt", "r", stdin); while (~scanf("%d%d", &tot, &n) && n) { printf("Sums of %d: ", tot); cnt = 0; for (int i = 0; i < n; i++) scanf("%d", &num[i]); sort(num, num + n); reverse(num, num + n); dfs(0, 0); if (!cnt) puts("NONE"); } return 0; }
3.HDU 4607
就是个树的直径巧妙应用
#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define MAXN 100005 int n, m; int tot, head[MAXN]; struct Edge { int v, next; } edge[MAXN * 2]; void init() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot++; } void dfs(int u, int fa, int deep, int &max_len, int &max_id) { if (head[u] == -1) return; if (deep > max_len) max_len = deep, max_id = u; for (int i = head[u]; i != -1; i = edge[i].next) if (edge[i].v != fa) dfs(edge[i].v, u, deep + 1, max_len, max_id); } int tree_2r() { int max_len = -1, max_id; dfs(1, -1, 0, max_len, max_id); max_len = -1; dfs(max_id, -1, 0, max_len, max_id); return max_len; } int main() { // freopen("data3.txt", "r", stdin); int T, u, v; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); init(); for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } int len = tree_2r(); int q; while (m--) { scanf("%d", &q); if (q <= len + 1) printf("%d ", q - 1); else printf("%d ", len + (q - len - 1) * 2); } } return 0; }
4.HDU 1175
做了好长时间，主要是对BFS理解不够深入，BFS的访问次序只是路径长度，相同的有几种，而路径短的可能拐了好几个弯，用过vis记录每个点最小拐弯数，次数更少的也要进入队列。还有考虑这题可以用Astar尝试做下。
#include <cstdio> #include <vector> #include <algorithm> #include <queue> using namespace std; int n, m; int G[1009][1009]; int vis[1009][1009]; struct Node { int x, y; int aim, cnt; Node() { } Node(int _x, int _y) { x = _x, y = _y, aim = -1, cnt = -1; } bool operator ==(const Node &tmp) const { return tmp.x == x && tmp.y == y; } bool operator !=(const Node &tmp) const { return tmp.x != x || tmp.y != y; } }; int dir[4][2] = { 0, -1, -1, 0, 1, 0, 0, 1 }; bool BFS(Node s, Node t) { if (s == t) return 0; queue<Node> Q; Q.push(s); while (!Q.empty()) { Node cur = Q.front(); Q.pop(); Node tmp = cur; for (int j = tmp.aim; j < tmp.aim + 4; j++) { int i = (j + 4) % 4; if (i + tmp.aim == 3) continue; cur.x = tmp.x + dir[i][0], cur.y = tmp.y + dir[i][1]; if (cur.x > n || cur.y > m || cur.x <= 0 || cur.y <= 0) continue; if (G[cur.x][cur.y] && cur != t) continue; if (tmp.aim != i) cur.cnt = tmp.cnt + 1, cur.aim = i; if (cur.cnt > 2) continue; if (cur == t) return 1; if (vis[cur.x][cur.y] > cur.cnt) { vis[cur.x][cur.y] = cur.cnt; Q.push(cur); } } } return 0; } int main() { // freopen("data3.txt", "r", stdin); int q, x1, y1, x2, y2; while (~scanf("%d%d", &n, &m) && m && n) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &G[i][j]); scanf("%d", &q); while (q--) { memset(vis, 0x3f, sizeof(vis)); scanf("%d%d%d%d", &x1, &y1, &x2, &y2); if (!G[x1][y1] || !G[x2][y2] || G[x1][y1] != G[x2][y2] || !BFS(Node(x1, y1), Node(x2, y2))) puts("NO"); else puts("YES"); } } return 0; }
5. POJ 1054
坐标哈希的裸题，要有最优化剪枝的
#include <iostream> #include <algorithm> using namespace std; #define MAXN 5009 #define hash_size 20100 struct Node { int x, y; Node() { } Node(int _x, int _y) : x(_x), y(_y) { } bool operator <(const Node &tmp) const { return (x == tmp.x) ? y < tmp.y : x < tmp.x; } } point[MAXN]; int head[hash_size]; int next[MAXN]; int getHash(Node p) { int h = hash_size; return ((p.x * 20001 + p.y) % h + h) % h; } bool find(int x, int y) { int f = getHash(Node(x, y)); for (int i = head[f]; i != -1; i = next[i]) if (point[i].x == x && point[i].y == y) return 1; return 0; } int R, C, n; bool check(Node tp) { return tp.x <= 0 || tp.x > R || tp.y <= 0 || tp.y > C; } int main() { // freopen("data3.txt", "r", stdin); while (~scanf("%d%d", &R, &C)) { scanf("%d", &n); memset(head, -1, sizeof(head)); for (int i = 0; i < n; i++) scanf("%d%d", &point[i].x, &point[i].y); sort(point, point + n - 1); for (int i = 0; i < n; i++) { int f = getHash(point[i]); next[i] = head[f]; head[f] = i; } int ans = 2, dx, dy, cnt; Node tp; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { cnt = 1; dx = point[j].x - point[i].x; dy = point[j].y - point[i].y; tp.x = point[i].x - dx, tp.y = point[i].y - dy; if (!check(tp)) continue; if (dx > R / 2 || dy > C / 2) continue; tp.x = point[i].x + (ans - 1) * dx, tp.y = point[i].y + (ans - 1) * dy; if (check(tp)) continue; tp.x = point[j].x, tp.y = point[j].y; bool flag = 0; while (find(tp.x, tp.y)) { tp.x += dx, tp.y += dy; cnt++; if (check(tp)) { flag = 1; break; } } if (flag && cnt > 2) ans = max(ans, cnt); } } if (ans > 2) printf("%d ", ans); else puts("0"); } return 0; }
6. HDU 1813
比较容易想的DFSID问题，首先求所有点到边界的最短距离的最大值开始为深度DFS，每次把没移到边界的点按一个方向挪进行搜索，采用计算最大最短距离作为剪枝。
搞了2小时了还是T，应该是一种情况的死循环。先贴T的代码
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> using namespace std; int G[19][19]; int N; int dis[19][19]; int dir[4][2] = { 0, 1, -1, 0, 1, 0, 0, -1 }; struct Point { int x, y; int yes; int len, aim; Point() { } Point(int _x, int _y) : x(_x), y(_y) { yes = 0; } Point(int _x, int _y, int _len, int _aim) : x(_x), y(_y), len(_len), aim(_aim) { } }; inline bool out(int x, int y) { if (G[x][y]) return 1; if (x < 1 || x > N || y < 1 || y > N) return 1; return 0; } inline bool ok(int x, int y) { if (x == 1 || x == N || y == 1 || y == N) return 1; return 0; } queue<Point> Q; int cnt; void BFS(int x, int y, int aim) { if (out(x, y)) return; dis[x][y] = 0; while (!Q.empty()) Q.pop(); Q.push(Point(x, y, 0, aim)); Point cur, tmp; while (!Q.empty()) { cur = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { if (cur.aim + i == 3) continue; tmp.x = cur.x + dir[i][0]; tmp.y = cur.y + dir[i][1]; if (out(tmp.x, tmp.y)) continue; if (dis[tmp.x][tmp.y] > cur.len + 1) { tmp.len = dis[tmp.x][tmp.y] = cur.len + 1; tmp.aim = i; Q.push(tmp); } } } } inline int Astar(Point SET[], int cnt) { int Min_deep = -1; for (int i = 0; i < cnt; i++) { Min_deep = max(Min_deep, dis[SET[i].x][SET[i].y]); } return Min_deep; } bool flag; int ans[109]; void DFSID(Point SET[], int deep, int last) { if (flag) return; if (last == 0) { flag = 1; return; } if (deep == 0 || Astar(SET, cnt) > deep) return; int last_t = last; Point point_t[101]; for (int i = 0; i < cnt; i++) { point_t[i] = SET[i]; } for (int d = 0; d < 4; d++) { for (int i = 0; i < cnt; i++) { if (SET[i].yes) continue; if (G[SET[i].x + dir[d][0]][SET[i].y + dir[d][1]]) continue; point_t[i].x = SET[i].x + dir[d][0]; point_t[i].y = SET[i].y + dir[d][1]; if (ok(point_t[i].x, point_t[i].y)) { point_t[i].yes = deep; last_t--; } } ans[deep] = d; DFSID(point_t, deep - 1, last_t); if (flag) return; last_t = last; } } int main() { // freopen("data3.txt", "r", stdin); bool p = 0; while (~scanf("%d", &N)) { if (p) puts(""); p = 1; getchar(); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) G[i][j] = getchar() - '0'; getchar(); } if (N < 3) { continue; } memset(dis, 0x7f, sizeof(dis)); for (int i = 1; i <= N; i++) { BFS(1, i, 3); BFS(N, i, 0); BFS(i, 1, 2); BFS(i, N, 1); } Point SET[109]; cnt = 0; int Min_deep = -1; for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) if (dis[i][j] != 2139062143 && !ok(i, j)) { Min_deep = max(Min_deep, dis[i][j]); SET[cnt++] = Point(i, j); } if (Min_deep == -1) continue; for (int deep = Min_deep;; deep++) { flag = 0; DFSID(SET, deep, cnt); if (flag) { for (int i = deep; i > 0; i--) { if (ans[i] == 0) puts("east"); else if (ans[i] == 1) puts("north"); else if (ans[i] == 2) puts("south"); else if (ans[i] == 3) puts("west"); } break; } } } return 0; }
7.UVA 10453
添加最少个字母使串为回文，记忆化搜索
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define MAXN 1009 #define INF 0x3fffffff int dp[MAXN][MAXN]; char str[MAXN]; int dfs(int left, int right) { if (left >= right) return dp[left][right] = 0; if (dp[left][right] != INF) return dp[left][right]; if (str[left] == str[right]) return dp[left][right] = min(dfs(left + 1, right - 1), min(dfs(left + 1, right), dfs(left, right - 1)) + 1); return dp[left][right] = min(dfs(left + 1, right), dfs(left, right - 1)) + 1; } void print(int left, int right) { if (left > right) return; if (left == right) { putchar(str[left]); return; } if (str[left] == str[right]) { putchar(str[left]); print(left + 1, right - 1); putchar(str[right]); return; } if (dp[left + 1][right] + 1 == dp[left][right]) { putchar(str[left]); print(left + 1, right); putchar(str[left]); return; } putchar(str[right]); print(left, right - 1); putchar(str[right]); } int main() { // freopen("data3.txt", "r", stdin); while (~scanf("%s", str)) { int len = strlen(str); for (int i = 0; i < len; i++) for (int j = i; j < len; j++) dp[i][j] = INF; printf("%d ", dfs(0, len - 1)); print(0, len - 1); puts(""); } return 0; }
8. HDU 2485
通过搜索枚举各种删除点方案，通过BFS找到一条路径，删除这条路径的每个点后DFS看能不能再找到可达路径，找到再枚举删除点，加上最优化剪枝
这题学到了BFS在状态中记录路径的姿势
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define MAXN 55 #define INF 0x3f3f3f3f using namespace std; int n, m, k, ans, tot; int head[MAXN]; bool vis[MAXN], del[MAXN]; struct Node { int v; int next; } edge[4005]; struct Point { int x, c; int path[MAXN]; } cur; void addedge(int u, int v) { edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot++; } bool bfs() { queue<Point> Q; memset(vis, 0, sizeof(vis)); cur.x = 1; cur.c = 0; vis[1] = 1; Q.push(cur); Point tmp; while (!Q.empty()) { cur = Q.front(); Q.pop(); for (int i = head[cur.x]; i != -1; i = edge[i].next) { int v = edge[i].v; if (del[v]) continue; if (!vis[v] && cur.c < k) { vis[v] = 1; if (v == n) { return 1; } tmp = cur; tmp.x = v; tmp.path[tmp.c++] = v; Q.push(tmp); } } } return 0; } void dfs(int num) { if (num >= ans) //最优化剪枝 return; if (!bfs()) { ans = num; return; } Point tmp = cur; for (int i = 0; i < tmp.c; i++) { int v = tmp.path[i]; del[v] = 1; dfs(num + 1); del[v] = 0; } } int main() { // freopen("data3.txt", "r", stdin); int u, v; while (scanf("%d%d%d", &n, &m, &k) && n && m && k) { tot = 0; memset(head, -1, sizeof(head)); for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); addedge(u, v); } ans = INF; memset(del, 0, sizeof(del)); dfs(0); printf("%d ", ans); } return 0; }
9. HDU 4090
对每个局面枚举一个操作，深搜加最优化剪枝。这里学到了用队列配合保存状态，对每个局面有局面备份和走过记录，还有位置转化很难写
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<string> using namespace std; int a[10][10]; int n, m, k; int ans; int cnt[10]; int dx[] = { 0, -1, 1, 0, -1, 1, -1, 1 }; int dy[] = { -1, 0, 0, 1, 1, 1, -1, -1 }; struct Point { int x, y; } Q[10000]; int len; int cnt_num(int x, int y, bool vis[][10]) { len = 1; Point tmp, cur; int front = 0, rear = 0; cur.x = x; cur.y = y; Q[rear++] = cur; vis[x][y] = 1; while (front < rear) { cur = Q[front++]; for (int d = 0; d < 8; d++) { tmp = cur; tmp.x += dx[d]; tmp.y += dy[d]; if (a[tmp.x][tmp.y] == a[x][y] && !vis[tmp.x][tmp.y]) { vis[tmp.x][tmp.y] = 1; len++; Q[rear++] = tmp; } } } return len; } inline void save(int sa[][10]) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) sa[i][j] = a[i][j]; } inline void recover(int sa[][10]) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = sa[i][j]; } void move() { //删和调整位置 for (int i = 0; i < len; i++) a[Q[i].x][Q[i].y] = 0; for (int i = 1; i <= n - 1; i++) //向下沉 for (int j = 1; j <= m; j++) { if (a[i][j] && !a[i + 1][j]) { int x; for (x = i; a[x][j]; x--) a[x + 1][j] = a[x][j]; a[x + 1][j] = 0; } } for (int j = m; j >= 1; j--) { bool flag = 1; for (int i = 1; i <= n; i++) if (a[i][j]) flag = 0; if (flag) { for (int r = 1; r <= n; r++) { int p, k; for (p = m; p > j; p--) //找到右数第一个位置p if (a[r][p]) break; if (p == j) continue; for (k = j; k < p; k++) a[r][k] = a[r][k + 1]; a[r][k] = 0; } } } } inline int get_H() { //剩余个数最优化情况 int sum = 0; for (int i = 1; i <= k; i++) { if (cnt[i] >= 3) sum += cnt[i] * cnt[i]; } return sum; } void dfs(int score) { //通过深搜每一次操作 ans = max(ans, score); if (get_H() + score <= ans) //预测函数剪枝 return; bool vis[10][10] = { 0 }; //与BFS传参保证这次枚举操作不多次枚举相同连通块 int a_backup[10][10]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (a[i][j] == 0 || vis[i][j]) continue; int s = cnt_num(i, j, vis); if (s < 3) continue; save(a_backup); cnt[a[i][j]] -= s; move(); dfs(score + s * s); recover(a_backup); cnt[a[i][j]] += s; } } int main() { // freopen("data_tmp.txt", "r", stdin); while (~scanf("%d%d%d", &n, &m, &k)) { memset(a, 0, sizeof(a)); memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); cnt[a[i][j]]++; } } ans = -1; dfs(0); printf("%d ", ans); } return 0; }