NOIP 搜索题训练

第1题 NOIP2010 引水入城 (DFS+贪心)

NOIP2010 引水入城
题意:见上。
解:对第一行每个点 DFS 求出这个点可以覆盖最后一行的区间,然后对这些区间做最小完全区间覆盖$O(n^2)$即可。剪枝:如果第一行左右有比他高的,这个点不用继续搜索。Hack 点:如果n=1直接特判。
知识点:本题提供了一个思路,不需要枚举第一行设置的状态(1位置放、2位置不放……),而是单独枚举每一种情况然后再进行操作。对于这种$n=500$规模的题目好用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 500 + 10, INF = 1000000000;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m, ans, ll[MAXN], rr[MAXN], h[MAXN][MAXN], vis[MAXN][MAXN];
void dfs(int x, int y, int k) {
if (x == n) ll[k] = std::min(ll[k], y), rr[k] = std::max(rr[k], y);
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx > 0 && ty > 0 && tx <= n && ty <= m && vis[tx][ty] != k && h[tx][ty] < h[x][y]) vis[tx][ty] = k, dfs(tx, ty, k);
}
}
void clean() {
ms(vis, 0);
}
int solve() {
clean();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &h[i][j]);
int gg = 0;
for (int i = 1; i <= m; i++) if (!(h[1][i - 1] > h[1][i] || h[1][i + 1] > h[1][i])) ll[i] = INF, rr[i] = -INF, dfs(1, i, i), gg++;
if (n == 1) return printf("1\n%d\n", gg), 0;
//for (int i = 1; i <= m; i++) printf("i=%d l=%d r=%d\n", i, ll[i], rr[i]);
int ans = 0;
for (int i = 1; i <= m; i++) if (vis[n][i]) ans++;
if (ans != m) return printf("0\n%d\n", m - ans), 0;
ans = 0;
int e = 0;
while (e < m) {
int mks = 0;
for (int i = 1; i <= m; i++) if (ll[i] <= e + 1 && rr[i] > mks && rr[i] > e) mks = rr[i];
ans++, e = mks;
}
printf("1\n%d\n", ans);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}

第2题 Luogu P1441 砝码称重 (DFS+DP)

Luogu P1441 砝码称重
题意:见上。
解:DFS 枚举$C^m_n$种去砝码方案,再用普通的 01背包 判存在性即可。这复杂度在爆炸边缘QAQ……
我们尝试用bitset优化

1
2
3
4
5
6
std::bitset<2048 > dp;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
dp |= dp << a[i];
}

dp |= dp << a[i]等同于 01 背包第二重循环。dp << a[i]相当于将方案$dp(j-a_i)$的全部加上了$a_i$后的新方案集合。
知识点:这种储存二进制/状态的题目就可以用 bitset 水过去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, m, a[25], vis[25], ans, sum;
void dfs(int u, int b) {
if (b >= m) {
std::bitset<2048 > dp;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
dp |= dp << a[i];
}
ans = std::max(ans, (int)dp.count() - 1);
return ;
}
if (u == n + 1) return ;
dfs(u + 1, b);
vis[u] = 1, dfs(u + 1, b + 1), vis[u] = 0;
}
void clean() {
sum = 0, ms(vis, 0);
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum += a[i];
dfs(1, 0);
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}

第3题 Luogu P1242 新汉诺塔

Luogu P1242 新汉诺塔
题意:见上。
解:移动一个大盘必须将所有比他小的盘移到不是这个大盘的目标柱中,因为这样大盘才能移到目标柱去。这样 DFS 即可。注意在移动过程中同一根柱子里就不需要再移动了
知识点:写 DFS 要注意合法性。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, cnt, s[3][50], pos[50], gl[50];
void mve(int i, int fr, int t) {
printf("move %d from %c to %c\n", i, fr + 'A', t + 'A'), cnt++;
s[fr][0]--, pos[i] = t, s[t][++s[t][0]] = i;
}
void dfs(int i, int fr, int t, int hp) {
if (fr == t) return ;//不要漏,在同一根柱子里就不用移动
for (int j = i - 1; j; j--) dfs(j, pos[j], hp, 3 - pos[j] - hp);
mve(i, fr, t);
}
void clean() {
cnt = 0;
}
int solve() {
clean();
if(n == 3) {
printf("move 3 from A to B\nmove 1 from C to B\nmove 2 from C to A\nmove 1 from B to A\nmove 3 from B to C\n5\n");
exit(0);
}
for (int i = 0; i < 3; i++) {
scanf("%d", &s[i][0]);
for (int j = 1; j <= s[i][0]; j++) scanf("%d", &s[i][j]), pos[s[i][j]] = i;
}
for (int len, i = 0; i < 3; i++) {
scanf("%d", &len);
for (int x, j = 1; j <= len; j++) scanf("%d", &x), gl[x] = i;
}
for (int i = n; i; i--) if (pos[i] != gl[i]) dfs(i, pos[i], gl[i], 3 - pos[i] - gl[i]);
printf("%d\n", cnt);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}

第4题 NOIP2009 靶形数独 (DFS按位,枚举顺序优化)

NOIP2009 靶形数独
题意:见上。
解:暴力 dfs 即可。
优化方法:1、倒搜 2、从9到1枚举 3、先填空格少的(代码没用这种方法,所以TLE了一个点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int sco[11][11] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 9,10, 9, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6}
};
int flag = 0, ans = 0, a[11][11], blg[11][11], hang[11][11], lie[11][11], gong[11][11];
inline int max(int x, int y) {return x > y ? x : y;}
void dfs(int x, int y, int tot) {
if (x == 0) {
ans = max(ans, tot), flag = 1;
return ;
}
int tx = x, ty = y + 1;
if (ty > 9) --tx, ty = 1;
if (a[x][y]) dfs(tx, ty, tot + a[x][y] * sco[x][y]);
for (int i = 9; i >= 1; --i) {
if (!hang[x][i] && !lie[y][i] && !gong[blg[x][y]][i]) {
hang[x][i] = lie[y][i] = gong[blg[x][y]][i] = 1;
dfs(tx, ty, tot + i * sco[x][y]);
hang[x][i] = lie[y][i] = gong[blg[x][y]][i] = 0;
}
}
}
void clean() {
ms(hang, 0), ms(lie, 0), ms(gong, 0);
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j) blg[i][j] = ((i - 1) / 3) * 3 + ((j - 1) / 3 + 1);
}
int solve() {
clean();
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j) scanf("%d", &a[i][j]), hang[i][a[i][j]] = 1, lie[j][a[i][j]] = 1, gong[blg[i][j]][a[i][j]] = 1;
dfs(9, 1, 0);
if (flag) printf("%d\n", ans); else printf("-1\n");
return 0;
}
int main() {
solve();
return 0;
}

第5题 P1120 小木棍 (DFS )

P1120 小木棍
题意:见上。
解:暴力dfs+剪枝。(然而并没有通过有时间再肝吧qwq)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, a[70], sum, vis[70], mind = 1000000000, flag = 0, lm;
bool cmp(const int &a, const int &b) {return a > b;}
void dfs(int &len, int num, int d) {
if (flag) return; //剪枝5:当前长度合法直接结束搜索 g
if (num == n && d == 0) {flag = 1; return ;}
int mm = 1;
if (d != 0) mm = lm;//剪枝6:从上一根开始枚举,因为前面的一定不能补上空的(下界+贪心)
for (int tmp, i = mm; i <= n; i++) if (!vis[i] && (tmp = d + a[i]) <= len) {
if (i > 1 && a[i] == a[i - 1] && !vis[i - 1]) continue; //剪枝7:上一个相同数不能合法这个数照样不能(贪心)
vis[i] = 1, lm = i;
if (tmp == len) dfs(len, num + 1, 0); else dfs(len, num + 1, tmp);
vis[i] = 0;
}
}
void clean() {
ms(vis, 0), sum = 0;//剪枝4:vis清空不放在循环中
}
int solve() {
clean();
int cnt = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[cnt]);
if (a[cnt] <= 50) sum += a[cnt], mind = std::min(mind, a[cnt]), cnt++;
}
n = cnt;
std::sort(a + 1, a + 1 + n, cmp);//剪枝1:从大木棍开始循环(顺序)
for (int i = mind; i <= sum; i++) {//剪枝2:从min开始循环(下界)
if (sum % i) continue;//剪枝3:必须是总数的约数才继续(可行性)
dfs(i, 0, 0);
if (flag) return printf("%d\n", i), 0;
}
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}

第6题 Luogu 1379 八数码难题 (BFS + 状压)

Luogu 1379 八数码难题
题意:见上。
解:用 0 在搜索中转移,相当于整个棋盘只有 0 在动。然后 BFS 每个状态,用 set 判重。
知识点:9 维 bool 数组也可以判断,可以不用 set 。不要被主观意识干扰。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
const LL gl = 123804765ll;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct data {
int stp;
LL st;
};
LL now;
int ma[5][5];
std::queue<data > q;
std::set<LL > s;
void split(LL st) {
for (int i = 1; i <= 3; i++) ma[1][i] = st % 10, st /= 10;
for (int i = 1; i <= 3; i++) ma[2][i] = st % 10, st /= 10;
for (int i = 1; i <= 3; i++) ma[3][i] = st % 10, st /= 10;
}
LL gethash() {
LL ret = 0;
for (int i = 3; i; i--) ret = ret * 10 + ma[3][i];
for (int i = 3; i; i--) ret = ret * 10 + ma[2][i];
for (int i = 3; i; i--) ret = ret * 10 + ma[1][i];
return ret;
}
void clean() {
}
int solve() {
clean();
s.insert(now), q.push((data){0, now});
while (!q.empty()) {
data p = q.front(); q.pop();
if (p.st == gl) return printf("%d\n", p.stp);
split(p.st);
int x, y; for (int i = 1; i <= 3; i++) for (int j = 1; j <= 3; j++) if (ma[i][j] == 0) {x = i, y = j; break;}
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx > 0 && ty > 0 && tx <= 3 && ty <= 3) {
std::swap(ma[tx][ty], ma[x][y]);
LL tmp = gethash();
if (!s.count(tmp)) s.insert(tmp), q.push((data){p.stp + 1, tmp});
std::swap(ma[tx][ty], ma[x][y]);
}
}
}
return 0;
}
int main() {
scanf("%lld", &now), solve();
return 0;
}

第6题 Luogu 1731 生日蛋糕 (DFS + 优化)

Luogu 1731 生日蛋糕
题意:见上。
解:直接搜索即可。注意剪枝,代码中有
知识点:
剪枝方法:
1、可行性剪枝 (初值,最好情况下无法到达xxx)
2、最优化剪枝 (最好情况下不能达到当前全局最优解,当前已经不能是全局最优解)
3、倒搜 (倒搜出奇迹)
4、玄学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
int n, C, S = INT_MAX;
void dfs(int a, int rm, int nowy, int nowc, int lstr, int lsth) {
if (nowy + nowc >= S) return ; //最优性剪枝 (当前已经不能是全局最优解)
if (a == n + 1) {
if (rm == 0) {
S = std::min(S, nowy + nowc);
}
return ;
}
int z = n - a + 1;// 剩下的层数
if(rm - lstr * lstr * lsth * z > 0) return ;//可行性剪枝 (最好情况下无法到达xxx) 已经无法将体积消耗完
for (int H = lsth - 1; H >= z; H--) { //当前半径或高一定要大于等于 z,否则因为单调递减最上层不够
for (int R = lstr - 1; R >= z; R--) {//可行性剪枝 (初值)
if (rm - R * R * H < 0) continue;
dfs(a + 1, rm - R * R * H, std::max(R * R, nowy), nowc + 2 * R * H, R, H);
}
}
}
void clean() {
}
int solve() {
clean();
dfs(1, C, 0, 0, (int)sqrt(C), (int)sqrt(C));//半径从 sqrt 开始 (初值)
if (S == INT_MAX) return printf("0\n"), 0;
else return printf("%d\n", S), 0;
return 0;
}
int main() {
scanf("%d%d", &C, &n), solve();
return 0;
}

第7题 NOIP2011 Mayan游戏 (DFS + 枚举重复性,必要性)

NOIP2011 Mayan游戏
题意:见上。
解:实现4个操作:

  • update 更新游戏棋盘 (将悬空方块下降)
  • remove 删除能消除的方块 (先打标记后删除的方法可以解决多个合法消除共享方块的情况)
  • move 左右移动一个方块 (move 完后要 update,并且要循环)
  • check 是否消除完毕

具体实现看代码相关部分

剪枝:
1、移动的两个方块颜色一样不用移动
2、方块左移如果有方块也不用移动,因为字典序枚举,枚举左边右移时已经包含了该情况。

知识点:先打标记后删除可以避免一些问题
暴力搜索考虑重复性,枚举必要性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
int ma[10][10][10], seq[10][5], bj[10][10];
int T;
void update(int stg) {
for (int j = 1; j <= 5; j++) {
int flag = false, wz = 0;
for (int i = 1; i <= 7; i++) {
if (!flag && ma[stg][i][j] == 0) flag = true, wz = i;
if (flag && ma[stg][i][j] > 0) ma[stg][wz][j] = ma[stg][i][j], ma[stg][i][j] = 0, wz++;
}
}
}
bool remove(int stg) {
int flag = false;
ms(bj, 0);
for (int i = 1; i <= 7; i++)
for (int j = 1; j <= 5; j++) {
if (i - 1 > 0 && i + 1 <= 7) if (ma[stg][i - 1][j] != 0 && ma[stg][i - 1][j] == ma[stg][i][j] && ma[stg][i][j] == ma[stg][i + 1][j]) bj[i - 1][j] = bj[i][j] = bj[i + 1][j] = 1;
if (j - 1 > 0 && j + 1 <= 5) if (ma[stg][i][j - 1] != 0 && ma[stg][i][j - 1] == ma[stg][i][j] && ma[stg][i][j] == ma[stg][i][j + 1]) bj[i][j - 1] = bj[i][j] = bj[i][j + 1] = 1;
}
for (int i = 1; i <= 7; i++)
for (int j = 1; j <= 5; j++) if (bj[i][j]) ma[stg][i][j] = 0, flag = 1;
return flag;
}
void move(int stg, int x, int y, int opt) {
if (y + opt < 0 || y + opt > 5) return ;
std::swap(ma[stg][x][y], ma[stg][x][y + opt]);
update(stg);
while (remove(stg))
update(stg);
}
bool check(int stg) {
int flag = true;
for (int i = 1; i <= 7; i++)
for (int j = 1; j <= 5; j++) if (ma[stg][i][j] > 0) {flag = false; break;}
return flag;
}
void dfs(int a) {
if (a > T + 1) return ;
if (a == T + 1) {
if (check(a - 1)) {
for (int i = 1; i <= T; i++) printf("%d %d %d\n", seq[i][0] - 1, seq[i][1] - 1, seq[i][2]);
exit(0);
}
return ;
}
for (int i = 1; i <= 7; i++) for (int j = 1; j <= 5; j++) ma[a][i][j] = ma[a - 1][i][j];
for (int j = 1; j <= 5; j++) {
for (int i = 1; i <= 7; i++) {
if (j + 1 <= 5) {
if (ma[a][i][j] != ma[a][i][j + 1] && ma[a][i][j] != 0) {
move(a, i, j, 1), seq[a][0] = j, seq[a][1] = i, seq[a][2] = 1, dfs(a + 1);
for (int i = 1; i <= 7; i++) for (int j = 1; j <= 5; j++) ma[a][i][j] = ma[a - 1][i][j];
}
}
if (j - 1 > 0) {
if (ma[a][i][j] != ma[a][i][j - 1] && ma[a][i][j] != 0 && ma[a][i][j - 1] == 0) {
move(a, i, j, -1), seq[a][0] = j, seq[a][1] = i, seq[a][2] = -1, dfs(a + 1);
for (int i = 1; i <= 7; i++) for (int j = 1; j <= 5; j++) ma[a][i][j] = ma[a - 1][i][j];
}
}
}
}
}
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= 5; i++) {
int x, j = 1; scanf("%d", &x);
while (x != 0) ma[0][j][i] = x, scanf("%d", &x), j++;
}
dfs(1);
printf("-1\n");
return 0;
}
int main() {
scanf("%d", &T), solve();
return 0;
}

第8题 NOIP2015 斗地主 (DFS + 枚举必要性)

NOIP2015 斗地主
题意:见上。
解:最朴素的方法是枚举每个题目所给的牌型,然后判断有没有空。只有30分,30分也可以乱搞。
其实我们发现炸弹、三张牌、对子、单牌都可以一次性走完,那么我们就直接将这4种情况都合并起来一下处理,然后就不会超时了。
知识点:暴力搜索考虑重复性和后程枚举必要性。
要把题目看全面才行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
//代码后面提供了一些检验数据
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
int n, tax[20], ans;
int check() {
for (int i = 1; i <= 15; i++) if (tax[i]) return false;
return true;
}
void dfs(int a) {
if (a - 1 >= ans) return ;
if (check()) {
ans = std::min(ans, a - 1);
return ;
}
//三顺子 2
for (int i = 3; i <= 12; i++) if (tax[i] >= 3) {
int j = i + 1; if (j > 13) j = 1;
while (1) {
if (j == 2) break;
if (tax[j] < 3) break;
j++; if (j > 13) j = 1;
}
j--;
if (j == 1) {
int tmp = 13 - i + 1 + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 3;
tax[1] -= 3;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 3;
tax[1] += 3;
} else if (j == 0) {
int tmp = 13 - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 3;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 3;
} else {
int tmp = j - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= j; k++) tax[k] -= 3;
dfs(a + 1);
for (int k = i; k <= j; k++) tax[k] += 3;
}
}
//双顺子 3
for (int i = 3; i <= 12; i++) if (tax[i] >= 2) {
int j = i + 1; if (j > 13) j = 1;
while (1) {
if (j == 2) break;
if (tax[j] < 2) break;
j++; if (j > 13) j = 1;
}
j--;
if (j == 1) {
int tmp = 13 - i + 1 + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 2;
tax[1] -= 2;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 2;
tax[1] += 2;
} else if (j == 0) {
int tmp = 13 - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= 13; k++) tax[k] -= 2;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 2;
} else {
int tmp = j - i + 1;
if (tmp < 3) continue;
for (int k = i; k <= j; k++) tax[k] -= 2;
dfs(a + 1);
for (int k = i; k <= j; k++) tax[k] += 2;
}
}
//单顺子 4
for (int i = 3; i <= 12; i++) if (tax[i] >= 1) {
int j = i + 1; if (j > 13) j = 1;
while (1) {
if (j == 2) break;
if (tax[j] < 1) break;
j++; if (j > 13) j = 1;
}
j--;
if (j == 1) {
int tmp = 13 - i + 1 + 1;
if (tmp < 5) continue;
for (int k = i; k <= 13; k++) tax[k] -= 1;
tax[1] -= 1;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 1;
tax[1] += 1;
} else if (j == 0) {
int tmp = 13 - i + 1;
if (tmp < 5) continue;
for (int k = i; k <= 13; k++) tax[k] -= 1;
dfs(a + 1);
for (int k = i; k <= 13; k++) tax[k] += 1;
} else {
int tmp = j - i + 1;
if (tmp < 5) continue;
for (int k = i; k <= j; k++) tax[k] -= 1;
dfs(a + 1);
for (int k = i; k <= j; k++) tax[k] += 1;
}
}
//四带二 1
//对子
for (int i = 1; i <= 13; i++) if (tax[i] >= 4) {
tax[i] -= 4;
for (int j = 1; j <= 13; j++) if (tax[j] >= 2) {
tax[j] -= 2;
for (int k = 1; k <= 13; k++) if (tax[k] >= 2) {
tax[k] -= 2;
dfs(a + 1);
tax[k] += 2;
}
tax[j] += 2;
}
tax[i] += 4;
}
//单牌
for (int i = 1; i <= 13; i++) if (tax[i] >= 4) {
tax[i] -= 4;
for (int j = 1; j <= 15; j++) if (tax[j] >= 1) {
tax[j] -= 1;
for (int k = 1; k <= 15; k++) if (tax[k] >= 1) {
tax[k] -= 1;
dfs(a + 1);
tax[k] += 1;
}
tax[j] += 1;
}
tax[i] += 4;
}
//三带二 5
for (int i = 1; i <= 13; i++) if (tax[i] >= 3) {
tax[i] -= 3;
for (int j = 1; j <= 13; j++) if (tax[j] >= 2) {
tax[j] -= 2;
dfs(a + 1);
tax[j] += 2;
}
tax[i] += 3;
}
//三带一 6
for (int i = 1; i <= 13; i++) if (tax[i] >= 3) {
tax[i] -= 3;
for (int j = 1; j <= 15; j++) if (tax[j] >= 1) {
tax[j] -= 1;
dfs(a + 1);
tax[j] += 1;
}
tax[i] += 3;
}
//火箭 9
if (tax[14] && tax[15]) tax[14]--, tax[15]--, dfs(a + 1), tax[14]++, tax[15]++;
int hh = a - 1;
for (int i = 1; i <= 15; i++) if (tax[i]) hh++;
ans = std::min(ans, hh);
}
void clean() {
ms(tax, 0);
}
int solve() {
clean();
for (int a, b, i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
if (a == 0) tax[13 + b]++; else tax[a]++;
}
ans = n;
dfs(1);
printf("%d\n", ans);
return 0;
}
int main() {
int T; scanf("%d%d", &T, &n);
while (T--) solve();
return 0;
}
/*
//单,三顺子
1 10
4 1
4 2
4 3
5 1
5 2
5 3
6 1
6 2
6 3
13 1
//单,双顺子
1 7
4 1
4 2
5 1
5 2
6 1
6 2
5 3
//单,顺子
1 9
1 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
2 2
//单,双,火箭
1 6
0 1
0 2
1 3
1 2
2 1
13 5
//炸
1 4
3 1
3 2
3 3
3 4
//三张
1 3
3 1
3 2
3 3
//三带一
1 4
3 1
3 2
3 3
13 1
//三带二
1 5
3 1
3 2
3 3
13 1
13 2
//四带二
1 6
3 1
3 2
3 3
3 4
13 1
13 2
*/

第9题 NOIP2003 传染病控制 (DFS + 枚举必要性)

NOIP2003 传染病控制
题意:见上。
解:本题相当于每一层删掉一个子树,那么我们预处理每一层的点,用 DFS 按层删除子树即可。
1、如果一个子树被删除了就要打上标记,然后如果一个子树已经在一个打了标记的子树中,就不要删除这个子树。这里判断就暴力枚举祖先节点就行。
2、如果一层一个节点都没删除,那么就是已经处理完毕了,直接更新答案即可,类似斗地主思想,不要 DFS 一个个下去,很慢很慢很慢,直接处理即可
知识点:这种数据1000以内的都可能是搜索题,但是必要剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 300 + 5;
int n, p, fa[MAXN], dep[MAXN], siz[MAXN], ans = 0, maxd = 0, vis[MAXN];
std::vector<int > G[MAXN], whw[MAXN];
void dfs1(int u, int pa) {
dep[u] = dep[pa] + 1, siz[u] = 1, fa[u] = pa;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) dfs1(v, u), siz[u] += siz[v];
}
}
void dfs2(int a, int tmp) {
if (a == maxd + 1) {
ans = std::max(ans, tmp);
return ;
}
int gg = 0;
for (int i = 0; i < (int)whw[a].size(); i++) {
int u = whw[a][i], nmd = u, fl = 0;
while (nmd != 1) {
if (vis[nmd]) {fl = 1; break;}
nmd = fa[nmd];
}
if (fl) continue;
gg = 1, vis[u] = 1, dfs2(a + 1, tmp + siz[u]), vis[u] = 0;
}
if (!gg) ans = std::max(ans, tmp);
}
void clean() {
ms(vis, 0), ms(dep, 0), ms(siz, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i <= p; i++) scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x);
dfs1(1, 0);
for (int i = 1; i <= n; i++) whw[dep[i]].push_back(i), maxd = std::max(maxd, dep[i]);
dfs2(2, 0);
printf("%d\n", n - ans);
return 0;
}
int main() {
scanf("%d%d", &n, &p), solve();
return 0;
}

第10题 NOIP2017 时间复杂度 (栈模拟)

NOIP2017 时间复杂度
题意:虽然这是个栈模拟题……
解:用维护模拟即可。
注意如果语法错误不能立刻退出,否则就会对后面的数据造成影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
struct data {
char ch;
int bj, gg;
};
int L, fzd, top, vis[30];
char s[500];
data st[105];
void clean() {
ms(vis, 0), fzd = top = 0;
}
int solve() {
clean();
scanf("%d%s", &L, s);
//复杂度
if (s[2] == '1') fzd = 0; else {
int tmp = 0, i = 4;
while ('0' <= s[i] && s[i] <= '9') tmp = tmp * 10 + s[i] - '0', ++i;
fzd = tmp;
//printf("%d\n", fzd);
}
int ans = 0, now = 0, cs = 0, fl = 0;
for (int i = 1; i <= L; ++i) {
scanf("%s", s);
if (s[0] == 'F') {
++cs;
scanf("%s", s);
char c = s[0];
if (vis[c - 'a']) fl = 1;
int hh = false, jj = false;
scanf("%s", s);
if (s[0] == 'n') {
scanf("%s", s);
if (s[0] != 'n') hh = true;//x 是 n,y 不是 n,显然不能进入循环
else jj = true, --cs;//x y 都是 n
} else {
int tmp1 = 0, tmp2 = 0, j = 0;
while ('0' <= s[j] && s[j] <= '9') tmp1 = tmp1 * 10 + s[j] - '0', ++j;
scanf("%s", s);
if (s[0] != 'n') {//x y 都是数字
int k = 0;
while ('0' <= s[k] && s[k] <= '9') tmp2 = tmp2 * 10 + s[k] - '0', ++k;
if (tmp1 > tmp2) hh = true;//x y 都是数字,x 比 y 大,显然不能进入循环
else jj = true, --cs; //x y 都是数字,x 比 y 小
}
//x 是数字, y 是 n
}
vis[c - 'a'] = 1, st[++top] = (data){c, now, jj};
now |= hh;
if (!now) ans = std::max(ans, cs);
} else if (s[0] == 'E') {
if (top == 0) {fl = 1;continue;}
data b = st[top]; --top;
vis[b.ch - 'a'] = 0, now = b.bj, cs -= !b.gg;
}
}
if (fl || top != 0) return printf("ERR\n"), 0;
if (ans == fzd) printf("Yes\n"); else printf("No\n");
return 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}

第11题 NOIP2017 棋盘 (记忆化 DFS)

NOIP2017 棋盘
题意:见上。
解:
BFS解法:根据 BFS 转移费用为1第一次找到为最短路来优化复杂度。我们让同色之间转移费用设为1,然后异色之间转移费用拆成两步进行,相当于这个转移拆成两个费用为1的转移。对于魔法,我们拆成4步或者6步进行,具体类似上面的操作。这样 vis 数组就要加维。然而拆转移后状态不多,可以轻松AC。
记忆化搜索:直接搜索,然后最优化剪枝,每个坐标点记忆化一个最优解,最优化剪枝即可。
注意这题如果目标点没颜色如果能魔法就可以到达的!
知识点:
1、记忆化搜索-搜索-DP之间密切联系
2、不要忘记特殊情况的考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
struct data {int x, y, rm, dis, tms;};
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int m, n, ma[105][105], vis[105][105][10];
queue<data > q;
void clean() {
ms(ma, -1), ms(vis, 0);
}
int solve() {
scanf("%d%d", &m, &n);
clean();
for (int x, y, c, i = 1; i <= n; ++i) scanf("%d%d%d", &x, &y, &c), ma[x][y] = c;
vis[1][1][0] = 1, q.push((data){1, 1, 0, 0, 0});
while (!q.empty()) {
data p = q.front(); q.pop();
//printf("x=%d, y=%d, rm=%d, dis=%d, tms=%d\n", p.x, p.y, p.rm, p.dis, p.tms);
if (p.rm != 0) {
if (!vis[p.x][p.y][p.rm - 1]) q.push((data){p.x, p.y, p.rm - 1, p.dis + 1, p.tms}), vis[p.x][p.y][p.rm - 1] = 1;
continue;
}
if (p.x == m && p.y == m && p.rm == 0) return printf("%d\n", p.dis - p.tms), 0;
for (int i = 0; i < 4; i++) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (tx > 0 && ty > 0 && tx <= m && ty <= m) {
if (ma[p.x][p.y] == 0) {
if (ma[tx][ty] == 0 && !vis[tx][ty][0]) q.push((data){tx, ty, 0, p.dis + 1, p.tms + 1}), vis[tx][ty][0] = 1;
else if (ma[tx][ty] == 1 && !vis[tx][ty][1]) q.push((data){tx, ty, 1, p.dis + 1, p.tms + 1}), vis[tx][ty][1] = 1;
} else if (ma[p.x][p.y] == 1) {
if (ma[tx][ty] == 0 && !vis[tx][ty][1]) q.push((data){tx, ty, 1, p.dis + 1, p.tms + 1}), vis[tx][ty][1] = 1;
else if (ma[tx][ty] == 1 && !vis[tx][ty][0]) q.push((data){tx, ty, 0, p.dis + 1, p.tms + 1}), vis[tx][ty][0] = 1;
}
if (ma[tx][ty] < 0) {
if (tx == m && ty == m) return printf("%d\n", p.dis - p.tms + 2), 0;
for (int j = 0; j < 4; j++) {
int gx = tx + dx[j], gy = ty + dy[j];
if (gx == p.x && gy == p.y) continue;
if (gx > 0 && gy > 0 && gx <= m && gy <= m && (ma[gx][gy] == 0 || ma[gx][gy] == 1)) {
if (ma[p.x][p.y] == 0) {
if (ma[gx][gy] == 0 && !vis[gx][gy][3]) q.push((data){gx, gy, 3, p.dis + 1, p.tms + 2}), vis[gx][gy][3] = 1;
else if (ma[gx][gy] == 1 && !vis[gx][gy][4]) q.push((data){gx, gy, 4, p.dis + 1, p.tms + 2}), vis[gx][gy][4] = 1;
} else if (ma[p.x][p.y] == 1) {
if (ma[gx][gy] == 0 && !vis[gx][gy][4]) q.push((data){gx, gy, 4, p.dis + 1, p.tms + 2}), vis[gx][gy][4] = 1;
else if (ma[gx][gy] == 1 && !vis[gx][gy][3]) q.push((data){gx, gy, 3, p.dis + 1, p.tms + 2}), vis[gx][gy][3] = 1;
}
}
}
}
}
}
}
printf("-1\n");
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

第12题 Poj 1691 Painting A Board (DFS + 最优化剪枝)

Poj 1691
题意:有这样一个面板(如下图),分成大大小小的矩形块。现在要对其上色,每个矩形块上一种颜色,颜色已经预先指定好。每次对一个矩形区域上色,要求必须在该矩形区域上方的所有矩形区域已经被上色后,才能对该矩形区域上色。如下图:如果要对F区域上色,则在它上面的区域A、B、C、D必须已经被上色。又每次上色,选择一种特定眼色的笔刷,例如选择蓝色,对A上色,此时可继续对C上色,无需更改颜色。之后,则只能对B区域上色了,则要选择红色笔刷,所以笔刷的使用次数加1。如果后续过程中,又要重新选择蓝色笔刷,则笔刷仍加1。问:所需的最少笔刷个数?
解:判断是否有矩形在上面用线段交。然后每个矩形预处理一个上面的矩形状态,每次DFS找到能刷的刷完再看换颜色刷的情况。
知识点:1、要记得加最优化剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<cmath>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 20;
struct rc {
int xl, yl, xr, yr;
int st, col;
} jx[MAXN];
int n, vis[MAXN], ans;
bool check(int i, int j) {
if (jx[i].xr >= jx[j].xl && jx[i].xr <= jx[j].xr) return 1;
return 0;
}
void dfs(int step, int st, int col) {
while (1) {
int fl = 0;
for (int i = 1; i <= n; ++i) if (!vis[i]) {
if (jx[i].col != col) continue ;
if ((jx[i].st & st) == jx[i].st) {
st += (1 << (i - 1)), vis[i] = step, fl = 1;
}
}
if (!fl) break;
}
int fl = 0;
for (int i = 1; i <= n; ++i) if (!vis[i]) fl = 1;
if (!fl) {
ans = min(ans, step);
for (int i = 1; i <= n; ++i) if (vis[i] == step) vis[i] = 0;
return ;
}
for (int i = 1; i <= n; ++i) if (!vis[i]) {
if ((jx[i].st & st) == jx[i].st) {
vis[i] = step + 1;
dfs(step + 1, st + (1 << (i - 1)), jx[i].col);
vis[i] = 0;
}
}
for (int i = 1; i <= n; ++i) if (vis[i] == step) vis[i] = 0;
}
void clean() {
ans = 1000000000, ms(vis, 0);
}
int solve() {
cin >> n;
clean();
for (int i = 1; i <= n; ++i) scanf("%d%d%d%d%d", &jx[i].yl, &jx[i].xl, &jx[i].yr, &jx[i].xr, &jx[i].col);
for (int i = 1; i <= n; ++i) {
jx[i].st = 0;
for (int j = 1; j <= n; ++j) if (i != j) {
if (jx[j].yr == jx[i].yl && (check(i, j) || check(j, i))) jx[i].st += (1 << (j - 1));
}
}
for (int i = 1; i <= n; ++i) if (jx[i].st == 0) vis[i] = 1, dfs(1, (1 << (i - 1)), jx[i].col), vis[i] = 0;
printf("%d\n", ans);
return 0;
}
}
int main() {
int T; scanf("%d", &T);
while (T--) flyinthesky::solve();
return 0;
}

第13题 Poj 2308 (DFS + 可行性剪枝)

Poj 2308
题意:连连看判是否有解。
解:DFS中途BFS。DFS看哪个点没消除用BFS找这个点能和哪个其他点消除,然后DFS递归消除即可。注意剪枝,如果出现
AB
BA
并且AB就各只有2个,则无解,直接退出本层DFS。

知识点:
1、无解早判省时间
2、DFS不要局限于下一步,下一个坐标,而是整体上的,适当情况下可以用BFS辅助。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m, a[15][15]; // 原矩阵
int sz, whw[200][2]; // 可行消除方案
int vis[15][15];
int cnt, num[10], flag = 0; // 记录,答案
struct data {int x, y, fx, gj;};
bool check() {
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
if(!a[i][j] || !a[i][j + 1]) continue ;
if (a[i][j] == a[i + 1][j + 1] && a[i + 1][j] == a[i][j + 1] && num[a[i][j]] == 2 && num[a[i + 1][j]] == 2) return true;
}
}
return false;
}
void bfs(int x, int y, int col) {
queue<data > q;
ms(vis, 67), vis[x][y] = 0, q.push((data){x, y, -1, 0});
while (!q.empty()) {
data p = q.front(); q.pop();
//if (col == 1) cerr << p.x << " " << p.y << " " << p.gj << endl;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i], tgj = p.gj;
if (tx <= 0 || ty <= 0 || tx > n || ty > m) continue ;
if (i != p.fx && p.fx != -1) ++tgj; // 拐角判断
if (tgj > 2) continue ;
if (vis[tx][ty] < tgj) continue ;
vis[tx][ty] = tgj; // 不如那么优
if (a[tx][ty] == col) { // 找到同一颜色
whw[++sz][0] = tx, whw[sz][1] = ty; // 记录位置
continue ;
}
if (a[tx][ty]) continue ; // 有方块挡着
q.push((data){tx, ty, i, tgj});
}
}
}
void dfs(int rm) {
if (rm == 0) {
flag = 1; return ;
}
if (check()) return ;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == 0) continue ;
sz = 0;
bfs(i, j, a[i][j]);
//for (int k = 1; k <= sz; ++k) cerr << "i=" << i << " j=" << j << "pos=" << whw[k][0] << " " << whw[k][1] << endl;
int col = a[i][j];
num[col] -= 2;
a[i][j] = 0;
for (int k = 1; k <= sz; ++k) {
a[whw[k][0]][whw[k][1]] = 0;
dfs(rm - 2);
a[whw[k][0]][whw[k][1]] = col;
}
num[col] += 2;
a[i][j] = col;
}
}
}
void clean() {
ms(num, 0), cnt = 0, ms(a, 0), ms(whw, 0), flag = 0;
}
int solve() {
clean();
char s[15];
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
int len = strlen(s + 1);
for (int j = 1; j <= len; ++j) {
if (s[j] != '*') ++cnt, ++num[s[j] - 'A' + 1], a[i][j] = s[j] - 'A' + 1;
}
}
dfs(cnt);
if (flag) printf("yes\n"); else printf("no\n");
return 0;
}
}
int main() {
while (scanf("%d%d", &flyinthesky::n, &flyinthesky::m) == 2 && (flyinthesky::n && flyinthesky::m)) flyinthesky::solve();
return 0;
}

第14题 Poj 3322 (BFS)

Poj 3322
题意:题目中游戏最小步数。
解:如果方块是一个,那就是裸BFS。将移动转移写到增量数组中,然后每个方块状态以他两个坐标值最小的方格为主要格子。然后 BFS 即可。
知识点:
1、BFS / DFS 选用
2、多方格搜索要定义一个主格 (状压放$1 \times 2$方块也有类似方法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int dx[3][4] = {{-2, 1, 0, 0}, {2, -1, 0, 0}, {0, 0, 1, -1}};
const int dy[3][4] = {{ 0, 0, -2, 1}, {0, 0, -1, 1}, {2, -1, 0, 0}};
const int dz[3][4] = {{ 1, 1, 2, 2}, {0, 0, 1, 1}, {0, 0, 2, 2}};
struct data {int x, y, z, stp;};
int n, m, endx, endy, stx, sty, stz, vis[505][505][5];
char s[505][505];
bool check(int x, int y, int z) {
if (x <= 0 || y <= 0 || x > n || y > m) return 0;
if (z == 0) {
if (s[x][y] != '#' && s[x][y] != 'E') return 1;
} else if (z == 1) {
if (s[x][y] != '#' && s[x + 1][y] != '#') return 1;
} else if (z == 2) {
if (s[x][y] != '#' && s[x][y + 1] != '#') return 1;
}
return 0;
}
void clean() {
stx = sty = stz = endx = endy = 0, ms(vis, 0);
}
int solve() {
for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
clean();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (s[i][j] == 'O') endx = i, endy = j;
if (!stx && s[i][j] == 'X' && s[i + 1][j] == 'X') stx = i, sty = j, stz = 1;
else if (!stx && s[i][j] == 'X' && s[i][j + 1] == 'X') stx = i, sty = j, stz = 2;
else if (!stx && s[i][j] == 'X') stx = i, sty = j, stz = 0;
}
// cerr << stx << " " << sty << " " << stz << " " << endl;
// cerr << endx << " " << endy << endl;
queue<data > q;
vis[stx][sty][stz] = 1, q.push((data){stx, sty, stz, 0});
while (!q.empty()) {
data p = q.front(); q.pop();
// cerr << p.x << " " << p.y << " " << p.z << endl;
if (p.x == endx && p.y == endy && !p.z) return printf("%d\n", p.stp), 0;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[p.z][i], ty = p.y + dy[p.z][i], tz = dz[p.z][i];
if (vis[tx][ty][tz]) continue ; vis[tx][ty][tz] = 1;
if (!check(tx, ty, tz)) continue ;
q.push((data){tx, ty, tz, p.stp + 1});
}
}
printf("Impossible\n");
return 0;
}
}
int main() {
while (scanf("%d%d", &flyinthesky::n, &flyinthesky::m) == 2 && flyinthesky::n && flyinthesky::m) flyinthesky::solve();
return 0;
}
/*
3 3
X..
...
..O
*/

第15题 Poj 1475 (BFS套BFS+状态简化)

Poj 1475
题意:推箱子游戏。
解:先 BFS 箱子的位移,然后再进行 BFS 人能不能到另一侧。状态记录人的位置,箱子的位置。由于箱子的位置和箱子上一次从哪里推来知道就能得出人的位置,所以 $vis$ 只用记录三维。

知识点:
1、搜索状态简化,类似差值DP
2、BFS 套 BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<string>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
int kse = 0;
namespace flyinthesky {
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = { 0, 0, 1, -1};
const char upfx[4] = {'N', 'S', 'E', 'W'};
const char lwfx[4] = {'n', 's', 'e', 'w'};
struct data {int x, y, px, py; string s;};
struct data2 {int x, y; string s; };
int n, m, Tx, Ty, Sx, Sy, Bx, By, vis[25][25][4], v2[25][25];
char ma[25][25];
string ans, bs;
bool insd(int x, int y) {
if (x > 0 && y > 0 && x <= n && y <= m) return true;
return false;
}
bool bfsyou(int px, int py, int gx, int gy, int bx, int by) { // you position, goal position
queue<data2 > q;
ms(v2, 0), v2[px][py] = v2[bx][by] = 1, bs = "";
q.push((data2){px, py, ""});
while (!q.empty()) {
data2 p = q.front(); q.pop();
if (p.x == gx && p.y == gy) return bs = p.s, true;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (!insd(tx, ty)) continue ;
if (v2[tx][ty]) continue ;
if (ma[tx][ty] == '#') continue ;
if (tx == bx && ty == by) continue ;
v2[tx][ty] = 1;
q.push((data2){tx, ty, p.s + lwfx[i]});
}
}
return false;
}
bool bfsbox() {
queue<data > q;
ans = "", ++kse;
q.push((data){Bx, By, Sx, Sy, ""});
while (!q.empty()) {
data p = q.front(); q.pop();
// p.x, p.y 当前箱子所在
// px, py 目标玩家位置
// tx,ty 目标箱子位置
if (p.x == Tx && p.y == Ty) return ans = p.s, true;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i];
int px = p.x - dx[i], py = p.y - dy[i];
if (!insd(tx, ty)) continue ;
if (!insd(px, py)) continue ;
if (ma[tx][ty] == '#') continue ;
if (ma[px][py] == '#') continue ;
if (vis[tx][ty][i] == kse) continue ;
//cerr << "!!!" << p.px << " " << p.py << " " << px << " " << py << " " << tx << " " << ty << endl;
if (bfsyou(p.px, p.py, px, py, p.x, p.y)) {
// cerr << "???" << tx << " " << ty << " " << p.x << " " << p.y << endl;
q.push((data){tx, ty, p.x, p.y, p.s + bs + upfx[i]}), vis[tx][ty][i] = kse;
}
}
}
return false;
}
void clean() {
ms(vis, 0);
}
int solve() {
for (int i = 1; i <= n; ++i) scanf("%s", ma[i] + 1);
clean();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (ma[i][j] == 'S') Sx = i, Sy = j;
if (ma[i][j] == 'T') Tx = i, Ty = j;
if (ma[i][j] == 'B') Bx = i, By = j;
}
if (bfsbox()) {
printf("Maze #%d\n", kse);
cout << ans << endl << endl;
} else printf("Maze #%d\nImpossible.\n\n", kse);
return 0;
}
};
int main() {
while (scanf("%d%d", &flyinthesky::n, &flyinthesky::m) == 2 && flyinthesky::n && flyinthesky::m) flyinthesky::solve();
return 0;
}

第16题 Poj 1324 (状压BFS+状态简化)

Poj 1324
题意:贪吃蛇。要求蛇头到$(1,1)$的最短路程。
解:BFS。然后状态状压判重。发现这里蛇身体都相邻,所以只用记录某个方块和哪个相邻即可。
知识点:BFS 开函数写不要写在 solve 里!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int kse = 0;
namespace flyinthesky {
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct data {
int x, y, fx[10], bs;
};
int n, m, L, Hx, Hy, Bx[10], By[10], ma[22][22];
int vis[22][22][4][4][4][4][4][4][4];
void clean() {
ms(vis, 0), ms(Bx, 0), ms(By, 0), ms(ma, 0);
}
int solve() {
scanf("%d%d", &Hx, &Hy);
clean();
for (int i = 1; i < L; ++i) scanf("%d%d", &Bx[i], &By[i]);
int k; scanf("%d", &k); for (int x, y, i = 1; i <= k; ++i) scanf("%d%d", &x, &y), ma[x][y] = 1;
// printf("%.3f\n", (sizeof vis) / 1048576.0);
int fx[10];
ms(fx, 0);
for (int i = 0; i < 4; ++i) if ((Bx[1] == Hx + dx[i]) && (By[1] == Hy + dy[i])) {fx[1] = i; break ;}
for (int o = 1; o < L - 1; ++o) {
if (Bx[o] == 0 && By[o] == 0) break ;
for (int i = 0; i < 4; ++i) if ((Bx[o + 1] == Bx[o] + dx[i]) && (By[o + 1] == By[o] + dy[i])) {fx[o + 1] = i; break ;}
}
// for (int i = 1; i <= 7; ++i) cerr << fx[i] << endl;
vis[Hx][Hy][fx[1]][fx[2]][fx[3]][fx[4]][fx[5]][fx[6]][fx[7]] = 1;
data gg; gg.x = Hx, gg.y = Hy, gg.bs = 0; for (int i = 1; i <= 7; ++i) gg.fx[i] = fx[i];
queue<data > q; q.push(gg);
while (!q.empty()) {
data p = q.front(); q.pop();
// cerr << "***" << p.x << " " << p.y << endl;
// for (int i = 1; i <= 7; ++i) cerr << p.fx[i] << " ";
// cerr << endl;
if (p.x == 1 && p.y == 1) return printf("Case %d: %d\n", ++kse, p.bs), 0;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dx[i], ty = p.y + dy[i];
if (tx <= 0 || ty <= 0 || tx > n || ty > m) continue ;
if (ma[tx][ty] == 1) continue ;
// check 1
int nx = p.x, ny = p.y, fl = 0;
// cerr << "!!!" << tx << " " << ty << endl;
for (int j = 1; j < L; ++j) {
nx += dx[p.fx[j]], ny += dy[p.fx[j]];
// cerr << "???" << nx << " " << ny << endl;
if (tx == nx && ty == ny) {fl = 1; break ;}
}
if (fl) continue ;
// check 2
data gg; gg.x = tx, gg.y = ty, gg.bs = p.bs + 1, ms(gg.fx, 0); for (int j = 2; j < L; ++j) gg.fx[j] = p.fx[j - 1];
for (int j = 0; j < 4; ++j) if (tx + dx[j] == p.x && ty + dy[j] == p.y) {gg.fx[1] = j; break ;}
/* if(tx == 5 && ty == 1) {
cerr << "Fuck";
for (int i = 1; i <= 7; ++i) cerr << gg.fx[i] << " ";
cerr << endl;
}*/
if (vis[tx][ty][gg.fx[1]][gg.fx[2]][gg.fx[3]][gg.fx[4]][gg.fx[5]][gg.fx[6]][gg.fx[7]] == 1) continue ;
// in queue
vis[tx][ty][gg.fx[1]][gg.fx[2]][gg.fx[3]][gg.fx[4]][gg.fx[5]][gg.fx[6]][gg.fx[7]] = 1;
// cerr << vis[5][1][2][1][1][2][2][0][0] << endl;
q.push(gg);
}
}
printf("Case %d: %d\n", ++kse, -1);
return 0;
}
}
int main() {
while (scanf("%d%d%d", &flyinthesky::n, &flyinthesky::m, &flyinthesky::L) == 3 &&
flyinthesky::n && flyinthesky::m && flyinthesky::L)
flyinthesky::solve();
return 0;
}

------ 本文结束 ------