主要针对常见的暴力枚举
还有状态空间搜索写了一些自己的模版和解法

回溯求解

位模拟枚举二叉树

LA3403

算法分析：
mobile-computing
mobile-computing2
mobile-computing3

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
//
//  main.cpp
//  LA3403
//
//  Created by zhangmin chen on 2019/6/19.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 6;
const int MAXN = (1 << 6);

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;


class Node {
public:
    double L, R;
    Node(double _L = 0, double _R = 0) : L(_L), R(_R) {}
};

int vis[MAXN];
double sum[MAXN], weight[maxn + 5];
vector<Node> nodes[MAXN];

int s;
double r;

void init1() {
    Set(vis, 0);
    Set(sum, 0);
    Set(weight, 0);
    _for(i, 0, MAXN) nodes[i].clear();
}

int init2() {
    int root = (1 << s) - 1;
    _rep(i, 0, root) _for(k, 0, s) {
        if( (1 << k) & i ) sum[i] += weight[k];
    }
    return root;
}

void dfs(int u) {
    if(vis[u]) return;
    vis[u] = true;
    
    bool haveChild = false;
    for(int left = (u - 1) & u; left; left = (left - 1) & u) {
        haveChild = true;
        
        int right = u ^ left;
        double dl = sum[right] / sum[u];
        double dr = sum[left] / sum[u];
        
        dfs(left);
        dfs(right);
        
        _for(i, 0, nodes[left].size()) _for(j, 0, nodes[right].size()) {
            Node cur;
            cur.L = max(nodes[left][i].L + dl, nodes[right][j].L - dr);
            cur.R = max(nodes[left][i].R - dl, nodes[right][j].R + dr);
            if(cur.L + cur.R < r) nodes[u].push_back(cur);
        }
    }
    
    if(!haveChild) nodes[u].push_back(Node());
}


int main() {
    freopen("input.txt", "r", stdin);
    
    int kase;
    scanf("%d", &kase);
    
    while (kase--) {
        scanf("%lf%d", &r, &s);
        init1();
        _for(i, 0, s) scanf("%lf", &weight[i]);
        int root = init2();
        
        dfs(root);
        double ans = -1;
        _for(i, 0, nodes[root].size()) {
            ans = max(ans, nodes[root][i].L + nodes[root][i].R);
        }
        
        printf("%.10lf\n", ans);
    }
}

n皇后问题

nQueens
nQueens2

实现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
//
//  main.cpp
//  nQueens01
//
//  Created by zhangmin chen on 2019/6/15.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 50;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int col[maxn], tot = 0, n = 8;
int nc = 0;

void init() {
    Set(col, 0);
    tot = 0;
    nc = 0;
}

void search(int cur) {
    nc++;
    if(cur == n) tot++;
    else {
        _for(i, 0, n) {
            int ok = 1;
            col[cur] = i;
            
            _for(j, 0, cur) {
                if(col[j] == col[cur] || col[j] + j == col[cur] + cur || cur - col[cur] == j - col[j]) {
                    ok = 0;
                    break;
                }
            }
            
            if(ok) search(cur + 1);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) && n) {
        init();
        search(0);
        printf("%d\n", tot);
        cout << endl;
    }
}

实现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
//
//  main.cpp
//  nQueens02
//
//  Created by zhangmin chen on 2019/6/15.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 50;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int vis[3][maxn], col[maxn], n = 8;
int tot = 0;

void init() {
    Set(vis, 0);
    Set(col, 0);
    tot = 0;
}

void search(int cur) {
    if(cur == n) tot++;
    else {
        _for(i, 0, n) {
            if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur+ n-i]) {
                col[cur] = i;
                vis[0][i] = vis[1][cur+i] = vis[2][cur+ n-i] = 1;
                search(cur+1);
                vis[0][i] = vis[1][cur+i] = vis[2][cur+ n-i] = 0;
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    
    while(scanf("%d", &n) == 1 && n) {
        init();
        //
        search(0);
        printf("%d\n", tot);
    }
}

解答树填空法

UVA524

解答树填空分析
UVA524

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
//
//  main.cpp
//  UVA524
//
//  Created by zhangmin chen on 2019/6/18.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int inf = 0x3f3f3f3f;
const int maxn = 50;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int A[maxn + 5], vis[maxn + 5], n;

int isPrime(int val) {
    for(int i = 2; i * i <= val; i++) {
        if(val % i == 0) return 0;
    }
    return 1;
}

void init() {
    Set(A, 0);
    Set(vis, 0);
}

void dfs(int cur) {
    if(cur == n && isPrime(A[n-1] + A[0])) {
        //debug(isPrime(A[n-1] + A[0]))
        _for(i, 0, n) {
            if(i != 0) printf(" ");
            printf("%d", A[i]);
        }
        printf("\n");
    }
    else {
        for(int x = 2; x <= n; x++) {
            if(!vis[x] && isPrime(x + A[cur-1])) {
                A[cur] = x;
                // debug(x);
                vis[x] = 1;
                dfs(cur + 1);
                vis[x] = 0;
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while(scanf("%d", &n) == 1 && n > 0) {
        // debug(n);
        if(kase > 0) cout << endl;
        printf("Case %d:\n", ++kase);
        
        init();
        A[0] = 1;
        dfs(1);
    }
}

简单字符串状态搜索：枚举后缀

HDU1627

HDU1627

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
//
//  main.cpp
//  HDU1627
//
//  Created by zhangmin chen on 2019/6/20.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 100;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int S[maxn], n, L;
int cnt = 0;

void init() {
    Set(S, 0);
    cnt = 0;
}

int OK(int cur) {
    for(int len = 1; len*2 <= cur+1; len++) {
        int equal = 1;
        _for(i, 0, len) {
            if(S[cur-i] != S[cur-i-len]) {
                equal = 0;
                break;
            }
        }
        if(equal) return 0;
    }
    return 1;
}

int dfs(int cur) {
    if(cnt++ == n) {
        _for(i, 0, cur) {
            if(i % 64 == 0 && i > 0) printf("\n");
            else if(i % 4 == 0 && i > 0) printf(" ");
            
            printf("%c", 'A' + S[i]);
        }
        printf("\n%d\n", cur);
        return 0;
    } else {
        _for(i, 0, L) {
            S[cur] = i;
            if(OK(cur) && !dfs(cur + 1)) return 0;
        }
    }
    return 1;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &L) == 2 && n > 0) {
        //
        init();
        dfs(0);
    }
}

剪枝

用到的STL函数

1
char *strchr(const char *str, int c)

在str字符串中搜索第一个c出现的位置
返回值从第一个c出现的位置，截取字符串到结束

LA5570

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
//
//  main.cpp
//  UVA140
//
//  Created by zhangmin chen on 2019/6/20.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 10;
const int maxc = 256;
const int maxl = 1000 + 10;

int letter[maxn], id[maxc];

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

vector<int> u;
map<int, vector<int> > v;



char str[maxl];



int read() {
    int n = 0;
    for(char c = 'A'; c <= 'Z'; c++) {
        if(strchr(str, c) != NULL) {
            id[c] = n++;
            letter[id[c]] = c;
        }
    }
    
    int p = 0, q = 0;
    int len = (int)strlen(str);
    for(;;) {
        while(p < len && str[p] != ':') p++;
        if(p == len) break;
        
        while(q < len && str[q] != ';') q++;
        u.push_back(id[str[p-1]]);
        
        _for(i, p+1, q) {
            v[id[str[p-1]]].push_back(id[str[i]]);
        }
        
        p++;
        q++;
    }
    return n;
}

int N, ans;
// N = read()

int P[maxn], bestP[maxn], pos[maxn];

void init() {
    Set(letter, 0);
    Set(id, 0);
    Set(P, 0);
    Set(bestP, 0);
    Set(pos, 0);
    u.clear();
    v.clear();
}


void solve() {
    ans = N;
    _for(i, 0, N) P[i] = i;

    for(;;) {
        _for(i, 0, N) pos[P[i]] = i;
        
        int bandwidth = 0;
        _for(i, 0, u.size()) {
            int node = u[i];
            for(auto& x : v[node]) {
                bandwidth = max(bandwidth, abs(pos[node] - pos[x]));
            }
        }
        
        if(bandwidth < ans) {
            ans = bandwidth;
            memcpy(bestP, P, sizeof(P));
        }
        
        if(!next_permutation(P, P + N)) break;
    }
}


int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%s", str) == 1 && str[0] != '#') {
        init();
        N = read();
        solve();
        
        _for(i, 0, N) printf("%c ", letter[bestP[i]]);
        printf("-> %d\n", ans);
    }
}

隐式图路径寻找

八数码问题求解：编码和解码

思路分析

eightCode
eightCode2

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
//
//  main.cpp
//  eightCode
//
//  Created by zhangmin chen on 2019/6/22.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxstate = 1000000;
const int inf = 362880 + 5;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;


typedef int State[9];
State nodes[maxstate], goal;
int dist[maxstate];

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int vis[inf], fact[9];

void init() {
    //
    Set(vis, 0);
    Set(fact, 0);
    
    fact[0] = 1;
    _for(i, 1, 9) fact[i] = fact[i-1] * i;
}

bool tryInsert(int id) {
    //
    int code = 0;
    _for(i, 0, 9) {
        int cnt = 0;
        _for(j, i+1, 9) { if(nodes[id][i] > nodes[id][j]) cnt++; }
        code += cnt * fact[8-i];
    }
    // debug(code);
    if(vis[code]) return false;
    return vis[code] = 1;
}

bool valid(int x, int y) {
    if(x >= 0 && x < 3 && y >= 0 && y < 3) return true;
    return false;
}

int bfs() {
    init();
    int front = 1, rear = 2;
    
    while(front < rear) {
        // solve:
        State& cur = nodes[front];
        if(Cmp(goal, cur) == 0) return front;
        
        int z;
        for(z = 0; z < 9; z++) if(!cur[z]) break;
        
        int x = z / 3, y = z % 3;
        
        _for(dir, 0, 4) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            int nz = nx * 3 + ny;
            
            //debug(nz);
            
            if(valid(nx, ny)) {
                //debug(nx);
                //debug(ny);
                
                State& to = nodes[rear];
                memcpy(&to, &cur, sizeof(cur));
                
                to[nz] = cur[z];
                to[z] = cur[nz];
                
                dist[rear] = dist[front] + 1;
                if(tryInsert(rear)) rear++;
            }
        }
        
        front++;
    }
    return 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    
    //init();
    
    // scanf nodes[1][9]
    _for(i, 0, 9) scanf("%d", &nodes[1][i]);
    _for(i, 0, 9) scanf("%d", &goal[i]);

    
    int ans = bfs();
    //debug(ans);
    if(ans > 0) printf("%d\n", dist[ans]);
    else printf("-1\n");
    
    return 0;
}

八数码问题求解： 哈希表

eightCode3
eightCode4

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
//
//  main.cpp
//  eightCode2
//
//  Created by zhangmin chen on 2019/6/24.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxstate = 1000000;
const int inf = 362880 + 5;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

typedef int State[9];
int dist[maxstate];
State nodes[maxstate], goal;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int vis[inf], fact[9];



bool valid(int x, int y) {
    if(x >= 0 && x < 3 && y >= 0 && y < 3) return true;
    return false;
}

const int hashSZ = 1000003;
int head[hashSZ], nxt[maxstate];


void init() {
    Set(vis, 0);
    Set(fact, 0);
    Set(head, 0);
    Set(nxt, 0);
    
    fact[0] = 1;
    _for(i, 1, 9) fact[i] = fact[i-1] * i;
}

int Hash(const State& s) {
    int val = 0;
    _for(i, 0, 9) val = val * 10 + s[i];
    return val % hashSZ;
}

void link(int id, int h) {
    nxt[id] = head[h];
    head[h] = id;
}

bool tryInsert(int id) {
    int h = Hash(nodes[id]);
    int u = head[h];
    
    while(u) {
        //
        if(Cmp(nodes[u], nodes[id]) == 0) return 0;
        u = nxt[u];
    }
    link(id, h);
    return true;
}

int bfs() {
    init();
    int front = 1, rear = 2;
    
    while (front < rear) {
        State& cur = nodes[front];
        if(Cmp(goal, cur) == 0) return front;
        
        int z;
        for(z = 0; z < 9; z++) if(!cur[z]) break;
        
        int x = z / 3, y = z % 3;
        
        _for(dir, 0, 4) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            int nz = nx * 3 + ny;
            
            if(valid(nx, ny)) {
                State& to = nodes[rear];
                Cpy(to, cur);
                
                to[nz] = cur[z];
                to[z] = cur[nz];
                
                dist[rear] = dist[front] + 1;
                if(tryInsert(rear)) rear++;
            }
        }
        
        front++;
    }
    return 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    
    _for(i, 0, 9) scanf("%d", &nodes[1][i]);
    _for(i, 0, 9) scanf("%d", &goal[i]);
    
    int ans = bfs();
    if(ans > 0) printf("%d\n", dist[ans]);
    else printf("-1\n");
    
    return 0;
}

隐式图(Implicit Graph)相关问题

终点状态未知：标签法

UVA10603

分析：
Fill

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
//
//  main.cpp
//  Fill
//
//  Created by zhangmin chen on 2019/6/26.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 200 + 5;
const int inf = 362880 + 5;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Node {
public:
    int pour[3], dist;
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }
    
    Node() {
        Set(pour, 0);
        dist = 0;
    }
    
    Node(const Node& rhs) {
        //
        Cpy(pour, rhs.pour);
        dist = rhs.dist;
    }
};

int vis[maxn][maxn], cap[3], ans[maxn];

void init() {
    Set(vis, 0);
    Set(cap, 0);
    Set(ans, -1);
}

void update(const Node& u) {
    _for(i, 0, 3) {
        int d = u.pour[i];
        if(ans[d] < 0 || u.dist < ans[d]) ans[d] = u.dist;
    }
}

void solve(int a, int b, int c, int d) {
    //
    cap[0] = a; cap[1] = b; cap[2] = c;
    priority_queue<Node> que;
    Node start;
    start.dist = 0;
    start.pour[0] = 0; start.pour[1] = 0; start.pour[2] = c;
    vis[0][0] = 1;
    que.push(start);
    
    while (!que.empty()) {
        Node x = que.top(); que.pop();
        update(x);
        if(ans[d] >= 0) break;
        
        // then bfs and spread the node
        // pour i to j
        _for(i, 0, 3) _for(j, 0, 3) if(i != j) {
            Node nxt(x);
            if(x.pour[i] == 0 || x.pour[j] == cap[j]) continue;
            
            int amount = min(cap[j], x.pour[i] + x.pour[j]) - x.pour[j];
            nxt.pour[i] -= amount;
            nxt.pour[j] += amount;
            nxt.dist = x.dist + amount;
            
            if(!vis[nxt.pour[0]][nxt.pour[1]]) {
                vis[nxt.pour[0]][nxt.pour[1]] = 1;
                que.push(nxt);
            }
        }
    }
    
    while (d >= 0) {
        if(ans[d] >= 0) {
            printf("%d %d\n", ans[d], d);
            return;
        }
        d--;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    
    int kase, a, b, c, d;
    scanf("%d", &kase);
    //debug(kase);
    
    while (kase--) {
        init();
        scanf("%d%d%d%d", &a, &b, &c, &d);
        solve(a, b, c, d);
    }
}

双向BFS

POJ3523

算法分析：

POJ3523-01
POJ3523-02

**注意的点：C 库函数 char *fgets(char str, int n, FILE stream)
从指定的流 stream 读取一行，并把它存储在 str 所指向的字符串内。
当读取 (n-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
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
//
//  main.cpp
//  POJ3523
//
//  Created by zhangmin chen on 2019/6/26.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 200;
const int maxs = 20;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }

const int dx[] = {-1, 0, 1, 0, 0};
const int dy[] = {0, -1, 0, 1, 0};

class Node{
public:
    int x, y;
    Node(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};

int from[3], to[3];
int deg[maxn], G[maxn][5];
Node nodes[maxn];
char grid[maxs][maxs];
int id[maxs][maxs];

int dist[maxn][maxn][maxn];
int color[maxn][maxn][maxn];

void init() {
    Set(from, 0);
    Set(to, 0);
    Set(deg, 0);
    Set(G, 0);
    Set(grid, 0);
    Set(id, 0);
    Set(dist, -1);
    Set(color, 0);
    
    _for(i, 0, maxn) {
        nodes[i].x = nodes[i].y = 0;
    }
}

int ID(int p1, int p2, int p3) {
    return (p1 << 16) | (p2 << 8) | p3;
}

void decode(int x, int& p1, int& p2, int& p3) {
    p1 = (x >> 16) & 0xff;
    p2 = (x >> 8) & 0xff;
    p3 = x & 0xff;
}

bool conflicit(int p1, int p2, int p12, int p22) {
    return p12 == p22 || (p1 == p22 && p2 == p12);
}

int bfs() {
    queue<int> queF;
    queue<int> queB;
    
    dist[from[0]][from[1]][from[2]] = 0;
    dist[to[0]][to[1]][to[2]] = 1;
    
    color[from[0]][from[1]][from[2]] = 1;
    color[to[0]][to[1]][to[2]] = 2;
    
    queF.push(ID(from[0], from[1], from[2]));
    queB.push(ID(to[0], to[1], to[2]));
    
    while (!queF.empty() || !queB.empty()) {
        int fSZ = (int)queF.size(), bSZ = (int)queB.size();
        
        while (fSZ--) {
            //
            int x = queF.front(); queF.pop();
            int p1, p2, p3;
            decode(x, p1, p2, p3);
            
            _for(i, 0, deg[p1]) {
                int p12 = G[p1][i];
                
                _for(j, 0, deg[p2]) {
                    int p22 = G[p2][j];
                    
                    if(conflicit(p1, p2, p12, p22)) continue;
                    
                    _for(k, 0, deg[p3]) {
                        int p32 = G[p3][k];
                        if(conflicit(p1, p3, p12, p32) || conflicit(p2, p3, p22, p32)) continue;
                        
                        if(color[p12][p22][p32] == 0) {
                            dist[p12][p22][p32] = dist[p1][p2][p3] + 1;
                            color[p12][p22][p32] = 1;
                            queF.push(ID(p12, p22, p32));
                        } else if(color[p12][p22][p32] == 2)
                            return dist[p12][p22][p32] + dist[p1][p2][p3];
                    }
                }
            }
        }
        
        while (bSZ--) {
            //
            int x = queB.front(); queB.pop();
            int p1, p2, p3;
            decode(x, p1, p2, p3);
            
            _for(i, 0, deg[p1]) {
                int p12 = G[p1][i];
                
                _for(j, 0, deg[p2]) {
                    int p22 = G[p2][j];
                    
                    if(conflicit(p1, p2, p12, p22)) continue;
                    
                    _for(k, 0, deg[p3]) {
                        int p32 = G[p3][k];
                        
                        if(conflicit(p1, p3, p12, p32) || conflicit(p2, p3, p22, p32)) continue;
                        
                        if(color[p12][p22][p32] == 0) {
                            dist[p12][p22][p32] = dist[p1][p2][p3] + 1;
                            color[p12][p22][p32] = 2;
                            queB.push(ID(p12, p22, p32));
                        } else if(color[p12][p22][p32] == 1)
                            return dist[p12][p22][p32] + dist[p1][p2][p3];
                    }
                }
            }
        }
    }
    
    return -1;
}

int main() {
    freopen("input.txt", "r", stdin);
    
    int w, h, n;
    while(scanf("%d%d%d\n", &w, &h, &n) == 3 && n) {
        init();
        _for(i, 0, h) fgets(grid[i], 20, stdin);
        
         // debugArr(grid, h, w);
        int cnt = 0;
        _for(i, 0, h) _for(j, 0, w) {
            if(grid[i][j] == '#') continue;
            
            nodes[cnt].x = i; nodes[cnt].y = j;
            id[i][j] = cnt;
            
            if(islower(grid[i][j])) from[grid[i][j] - 'a'] = cnt;
            else if(isupper(grid[i][j])) to[grid[i][j] - 'A'] = cnt;
            
            cnt++;
        }
        
        // build graph:
        _for(i, 0, cnt) {
            _for(d, 0, 5) {
                int nx = nodes[i].x + dx[d];
                int ny = nodes[i].y + dy[d];
                if(grid[nx][ny] == '#') continue;
                
                G[i][deg[i]++] = id[nx][ny];
            }
        }
        
        if(n <= 2) {
            deg[cnt] = 1; G[cnt][0] = cnt; from[2] = to[2] = cnt++;
        }
        if(n <= 1) {
            deg[cnt] = 1; G[cnt][0] = cnt; from[1] = to[1] = cnt++;
        }
        
        printf("%d\n", bfs());
    }
}

迭代加深搜索IDA*

埃及分数问题

Egyptian Fractions

算法分析：
UVA12558

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
//
//  main.cpp
//  UVA12558
//
//  Created by zhangmin chen on 2019/6/27.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 100 + 10;
const int maxv = 200000;
const int inf = 0x3f3f3f3f;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }

set<llong> vis;
llong v[maxn], ans[maxn];
int a, b, k;

void init() {
    vis.clear();
    Set(v, 0);
    Set(ans, -1);
}

llong gcd(llong a, llong b) {
    return b == 0 ? a : gcd(b, a % b);
}

bool better(int d) {
    _forDown(i, d, 0) {
        if(v[i] != ans[i]) {
            return ans[i] == -1 || v[i] < ans[i];
        }
    }
    return false;
}

inline int getFrom(llong a, llong b) {
    return (int)(b / a + 1);
}

bool dfs(int d, int maxd, int from, llong a, llong b) {
    //
    if(d == maxd) {
        if(b % a) return false;
        if(vis.count(b / a)) return false;
        
        v[d] = b / a;
        if(better(d)) {
            memcpy(ans, v, sizeof(llong) * (d + 1));
        }
        return true;
    }
    
    bool ok = false;
    from = max(from, getFrom(a, b));
    
    _for(i, from, inf) {
        if(b * (maxd - d + 1) <= a * i) break;
        if(vis.count(i)) continue;
        v[d] = i;
        
        llong a2 = i * a - b;
        llong b2 = i * b;
        llong g = gcd(a2, b2);
        
        // I made a bug here:
        if(dfs(d+1, maxd, i+1, a2/g, b2/g)) {
            ok = true;
        }
    }
    
    return ok;
}

bool solve(int& maxd) {
    //
    int ok = 0;
    for(maxd = 1; maxd <= 100; maxd++) {
        //
        Set(ans, -1);
        Set(v, 0);
        int f = getFrom(a, b);
        if(dfs(0, maxd, f, a, b)) {
            ok = 1;
            break;
        }
    }
    return ok;
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    int t;
    scanf("%d", &t);
    
    while (t--) {
        init();
        
        cin >> a >> b >> k;
        _for(i, 0, k) {
            int v;
            cin >> v;
            vis.insert(v);
        }
        
        // finished init
        
        // bool solve()
        int maxd;
        int ok = solve(maxd);
        
        cout << "Case " << ++kase << ": ";
        if(ok) {
            cout << a << "/" << b << "=";
            _for(i, 0, maxd) cout << "1/" << ans[i] << "+";
            cout << "1/" << ans[maxd] << "\n";
        } else cout << "No solution.\n";
    }
    return 0;
}

字符串：固定字符个数，有限次变换

UVA11212

UVA11212

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
//
//  main.cpp
//  UVA11212
//
//  Created by zhangmin chen on 2019/6/29.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 9;
const int MAXD = 10;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }

int v[maxn], n;

void init() {
    Set(v, 0);
}

bool sorted() {
    _for(i, 0, n-1) {
        if(v[i] >= v[i+1]) return false;
    }
    return true;
}

int h() {
    int cnt = 0;
    _for(i, 0, n-1) if(v[i] + 1 != v[i+1]) cnt++;
    
    if(v[n-1] != n) cnt++;
    return cnt;
}

int dfs(int d, int maxd) {
    //
    if( h() > 3 * (maxd - d) ) return false;
    if(sorted()) return true;
    
    // then: try to dfs(d+1, maxd)
    int buf[maxn], oldv[maxn];
    Cpy(oldv, v);
    
    _for(i, 0, n) _for(j, i, n) {
        int cnt = 0;
        _for(k, 0, n) if(k < i || k > j) buf[cnt++] = v[k];
        
        _for(p, 0, cnt) {
            int cnt2 = 0;
            _rep(k, 0, p) v[cnt2++] = buf[k];
            _rep(k, i, j) v[cnt2++] = oldv[k];
            _for(k, p+1, cnt) v[cnt2++] = buf[k];
            
            if(dfs(d+1, maxd)) return true;
            Cpy(v, oldv);
        }
    }
    
    return false;
}

int solve() {
    if(sorted()) return 0;
    int maxd;
    for(maxd = 1; maxd < MAXD; maxd++) {
        if(dfs(0, maxd)) return maxd;
    }
    return MAXD;
}

int main() {
    freopen("input.txt", "r", stdin);
    
    int kase = 0;
    
    while (scanf("%d", &n) == 1 && n) {
        _for(i, 0, n) scanf("%d", &v[i]);
        
        // dfs and solve()
        printf("Case %d: %d\n", ++kase, solve());
    }
}

综合应用

对仗工整的枚举

LA5703
LA5703

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
//
//  main.cpp
//  LA5703
//
//  Created by zhangmin chen on 2019/6/30.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int inf = 65536;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(llong i = (l); i <= (r); i++)
#define _for(i, l, r) for(llong i = (l); i < (r); i++)
#define _forDown(i, l, r) for(llong i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    
    for(int kase = 1; kase <= T; kase++) {
        // solve the problem
        llong ans = 0;
        int n, s1, v1, s2, v2;
        scanf("%d%d%d%d%d", &n, &s1, &v1, &s2, &v2);
        
        if(s1 > s2) {
            swap(s1, s2);
            swap(v1, v2);
        }
        
        if(n / s2 >= inf) {
            //
            _rep(i, 0, s1) ans = max(ans, v2 * i + (n - s2 * i) / s1 * v1);
            _rep(i, 0, s2) ans = max(ans, v1 * i + (n - s1 * i) / s2 * v2);
        }
        else {
            for(llong i = 0; s2 * i <= n; i++) {
                ans = max(ans, v2 * i + (n - s2 * i) / s1 * v1);
            }
        }
        
        printf("Case #%d: %lld\n", kase, ans);
    }
}

IDA*旋转游戏

POJ2286

POJ2286

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
//
//  main.cpp
//  POJ2286
//
//  Created by zhangmin chen on 2019/6/30.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 24;
const int maxl = 2000;
const int inf = 2400;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }

/*
         00    01
         02    03
   04 05 06 07 08 09 10
         11    12
   13 14 15 16 17 18 19
         20    21
         22    23
 */


const int revID[8] = {5, 4, 7, 6, 1, 0, 3, 2};
const int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int line[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}
};

int v[maxn];
char res[maxl];

void addLine() {
    _for(i, 4, 8) _for(j, 0, 7) {
        line[i][j] = line[revID[i]][6-j];
    }
}

void init() {
    Set(v, 0);
    Set(res, 0);
}

bool finish() {
    _for(i, 0, 8) if(v[center[i]] != v[center[0]]) return false;
    return true;
}

int diff(int t) {
    int cnt = 0;
    _for(i, 0, 8) if(v[center[i]] != t) cnt++;
    return cnt;
}

int h() {
    int ans = inf;
    _rep(i, 1, 3) ans = min(ans, diff(i));
    return ans;
}

void mv(int dir) {
    int tmp = v[line[dir][0]];
    _for(i, 0, 6) v[line[dir][i]] = v[line[dir][i+1]];
    v[line[dir][6]] = tmp;
}

int dfs(int d, int maxd) {
    if(finish()) {
        res[d] = '\0';
        printf("%s\n", res);
        return true;
    }
    if(h() + d > maxd) return false;
    
    // then recurse:
    _for(dir, 0, 8) {
        res[d] = 'A' + dir;
        mv(dir);
        if(dfs(d+1, maxd)) return true;
        mv(revID[dir]);
    }
    
    return false;
}


int main() {
    //
    freopen("input.txt", "r", stdin);
    addLine();
    init();
    
    while (scanf("%d", &v[0]) == 1 && v[0]) {
        //init();
        
        _for(i, 1, maxn) scanf("%d", &v[i]);
        _for(i, 0, maxn) if(!v[i]) return 0;
        
        if(finish()) {
            printf("No moves needed\n");
        } else {
            int maxd = 1;
            for(maxd = 1; ; maxd++) {
                if(dfs(0, maxd)) break;
            }
        }
        printf("%d\n", v[6]);
        init();
    }
}

The art of IDA*

POJ1084

POJ1084

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
//
//  main.cpp
//  POJ1084
//
//  Created by zhangmin chen on 2019/7/2.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 60;
const int maxs = 5 + 1;


#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

llong cell[maxs][maxs];
llong bit[maxn];
int n, tot, k;
llong st;

llong sqr[maxn];
int sqrN;

void init1() {
    Set(cell, 0);
    Set(sqr, 0);
}

void init2() {
    bit[0] = 1;
    _rep(i, 1, maxn) bit[i] = (bit[i-1] << 1);
}

int getR(int x, int y) {
    return (2 * n + 1) * x + y;
}

int getC(int x, int y) {
    return (2 * n + 1) * x + y + n;
}

int build() {
    int cnt = 0;
    // then cnt how many square
    
    _for(i, 0, n) _for(j, 0, n) {
        cell[i][j] |= (bit[getR(i, j)] | bit[getR(i, j) + (2 * n + 1)]);
        cell[i][j] |= (bit[getC(i, j)] | bit[getC(i, j) + 1]);
        sqr[cnt] = cell[i][j];
        cnt++;
    }
    
    _rep(sz, 2, n) {
        _forPlus(x, 0, sz - 1, n) _forPlus(y, 0, sz - 1, n) {
            _for(dx, 0, sz) _for(dy, 0, sz) { sqr[cnt] ^= cell[x + dx][y + dy]; }
            cnt++;
        }
    }
    
    return cnt;
}

int h(llong st) {
    int cnt = 0;
    _for(i, 0, sqrN) if( (sqr[i] & st) == sqr[i] ) {
        cnt++;
        st ^= sqr[i];
    }
    
    return cnt;
}

int dfs(int d, int maxd, llong st) {
    //
    if(d == maxd) {
        _for(i, 0, sqrN) if( (sqr[i] & st) == sqr[i] ) return false;
        return true;
    }
    
    if(h(st) + d > maxd) return false;
    
    // then recurse:
    // del is the square to be destroyed
    llong del = 0;
    _for(i, 0, sqrN) if( (st & sqr[i]) == sqr[i] ) {
        if(!del) {
            del = sqr[i];
            break;
        }
    }
    
    _for(i, 0, tot) if( (bit[i] & del) == bit[i]) {
        if(dfs(d+1, maxd, st ^ bit[i])) return true;
    }
    
    
    return false;
}

int solve(llong st) {
    int maxd = 1;
    for (maxd = 1; ; maxd++) {
        if(dfs(0, maxd, st)) break;
    }
    return maxd;
}

int main() {
    freopen("input.txt", "r", stdin);
    
    int kase;
    scanf("%d", &kase);
    
    while (kase--) {
        init1();
        init2();
        
        scanf("%d%d", &n, &k);
        tot = 2 * n * (n + 1);
        st = bit[tot] - 1;
        _for(i, 0, k) {
            int a;
            scanf("%d", &a);
            st ^= bit[a-1];
        }
        
        // finish input, then build square
        sqrN = build();
        printf("%d\n", solve(st));
    }
}

如果位运算面临数组开不下的问题
使用普通解法，需要一个标记flag数组(contains)数组
用来标记sqr[i]的边有没有number = k的火柴
contains[i][k] => sqr[i] has number k edge

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
//
//  main.cpp
//  POJ1084-2
//
//  Created by zhangmin chen on 2019/7/4.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 60 + 5;

int n, tot, k;
int exist[maxn];
int contains[maxn][maxn];
int full[maxn], sqr[maxn];
int sqrN;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

void init1() {
    Set(exist, 0);
    Set(contains, 0);
    Set(sqr, 0);
    Set(full, 0);
}

void initSqr(int k) {
    _for(i, 0, tot) exist[i] = 1;
    // debug(tot);
    while (k--) {
        int a;
        scanf("%d", &a);
        exist[a - 1] = 0;
    }
}

int getR(int x, int y) {
    return (2 * n + 1) * x + y;
}

int getC(int x, int y) {
    return (2 * n + 1) * x + y + n;
}

int build() {
    int cnt = 0;
    _rep(sz, 1, n) {
        _forPlus(x, 0, sz - 1, n) _forPlus(y, 0, sz - 1, n) {
            full[cnt] = 4 * sz;
            sqr[cnt] = 0;
            
            _for(dl, 0, sz) {
                int up = getR(x, y + dl);
                int down = getR(x + sz, y + dl);
                int left = getC(x + dl, y);
                int right = getC(x + dl, y + sz);
                
                contains[cnt][up] = 1;
                contains[cnt][down] = 1;
                contains[cnt][left] = 1;
                contains[cnt][right] = 1;
                
                sqr[cnt] += (exist[up] + exist[down] + exist[left] + exist[right]);
            }
            
            cnt++;
        }
    }
    
    return cnt;
}



int dfs(int d, int maxd) {
    if(d == maxd) {
        _for(i, 0, sqrN) if(sqr[i] == full[i]) return false;
        return true;
    }
    
    //if(d + h() > maxd) return false;
    
    int del = 0;
    // del is the id number of square to be destoryed
    _for(i, 0, sqrN) if(sqr[i] == full[i]) {
        del = i;
        break;
    }
    
    _for(i, 0, tot) {
        // debug(tot);
        if(contains[del][i]) {
            _for(k, 0, sqrN) if(contains[k][i]) sqr[k]--;
            if(dfs(d+1, maxd)) return true;
            _for(k, 0, sqrN) if(contains[k][i]) sqr[k]++;
        }
    }
    
    return false;
}

int solve() {
    int maxd = 1;
    for (maxd = 1; ; maxd++) {
        if(dfs(0, maxd)) break;
    }
    return maxd;
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    scanf("%d", &kase);
    
    while (kase--) {
        init1();
        
        scanf("%d%d", &n, &k);
        tot = 2 * n * (n + 1);
        initSqr(k);
        sqrN = build();
        
        printf("%d\n", solve());
    }
}

快速幂计算

POJ3134

POJ3134

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
//
//  main.cpp
//  POJ3134
//
//  Created by zhangmin chen on 2019/7/4.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 1000 + 10;


#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int n;
int v[maxn];

void init() {
    Set(v, 0);
    v[0] = 1;
}

int h(int* v, int d, int maxd) {
    int maxv = v[0];
    _rep(i, 1, d) maxv = max(maxv, v[i]);
    return maxv << (maxd - d);
}

int dfs(int d, int maxd) {
    if(d == maxd) {
        if(v[d] == n) return true;
        return false;
    }
    
    if(h(v, d, maxd) < n) return false;
    
    // if(dfs(d+1, ...)) return true;
    _forDown(i, d, 0) {
        v[d+1] = v[d] + v[i];
        if(dfs(d+1, maxd)) return true;
        
        v[d+1] = v[d] - v[i];
        if(dfs(d+1, maxd)) return true;
    }
    
    return false;
}

int solve() {
    //
    if(n == 1) return 0;
    v[0] = 1;
    int maxd = 1;
    for(maxd = 1; ; maxd++) {
        //
        if(dfs(0, maxd)) break;
    }
    
    return maxd;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();
        printf("%d\n", solve());
    }
}