主要写一些数据结构模版
以及综合应用

拓扑排序：有向环解决二阶矩阵

矩阵问题，求方程式是否有解
本质是用拓扑排序判断有向环，解决循环引用的问题

LA5154

题目分析：
LA5154

1/ 表达式的表示

1
2
const int maxl = 128;
char exp[maxr][maxc][maxl];

2/ 读取表达式中的一串数字

1
2
3
4
5
6
7
8
9
10
11
12
13
int read(const char* str, int& len) {
    len = 0;
    // len 初始化为多少，具体问题具体分析
    int ans = 0, base = 1;
    while(str[len] && isdigit(str[len])) {
        ans *= base;
        ans += str[len] - '0';
        base *= 10;

        len++;
    }
    return ans;
}

3/ 二维拓扑排序程序结构

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
int vis[maxr][maxc];
Set(vis, 0);

bool candfs(int r, int c) {
    int& ok = vis[r][c];
    if(ok == -1) return false;
    else if(ok == 1) return true;

    ok = -1;

    /*

    read_from_exp(exp_);
    if(!candfs(nr, nc)) return false;

    */

    ok = 1;
    return true;
} 

void dfs() {
    bool cycle = false;
    _for(i, 0, R) _for(j, 0, c) {
        bool ok = candfs(i, j);

        if(!ok) {
            cycle = true;
            print_ans();
        }
    }
    if(cycle) return;
}

4/ 表达式求解：读取表达式的值
A7898787这样，从A+1开始，往后读取连续的值7898787

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
bool candfs(int r, int c) {
    int& val = value[r][c];
    val = 0;

    int& ok = vis[r][c];
    ....
    ....
    // 代码同上

    // read_from_exp(exp_):

    const char* exp_ = exp[r][c];
    int sign = 1;
    _for(i, 0, strlen(exp_)) {
        if(exp_[i] == '-') sign = -1;
        else if(exp_[i] == '+') sign = 1;
        else if(isdigit(exp_[i])) {
            int elen, res;
            res = read(exp_+i, elen);

            val += res * sign;
            sign = 1;
            i += elen - 1;
        }
        else if(isupper(exp_[i])) {
            int elen;
            int row = exp_[i] - 'A';
            int col = read(exp_+i+1, elen);

            if(!candfs(row, col)) return false;

            val += sign * value[row][col];
            sign = 1;
            i += elen + 1 - 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
//
//  main.cpp
//  LA5154
//
//  Created by zhangmin chen on 2019/4/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>

using namespace std;
typedef long long llong;

#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)

const int maxr = 20 + 5;
const int maxc = 10 + 5;

int R, C;
int vis[maxr][maxc], value[maxr][maxc];
char exp[maxr][maxc][128];

int read(const char* str, int& len) {
    //
    len = 0;
    int ans = 0, base = 1;
    while(str[len] && isdigit(str[len])) {
        //
        ans *= base;
        ans += str[len] - '0';
        base *= 10;
        
        len++;
    }
    return ans;
}

int canDfs(int r, int c) {
    // template of toposort()
    
    int& ok = vis[r][c];
    if(ok == -1) return false;
    else if(ok == 1) return true;
    
    ok = -1;
    // visit signed
    
    
    int& val = value[r][c];
    val = 0;
    
    const char* exp_ = exp[r][c];
    int len = (int)strlen(exp_), sign = 1;
    
    for(int i = 0; i < len; i++) {
        if(exp_[i] == '-') sign = -1;
        else if(exp_[i] == '+') sign = 1;
        else if(isdigit(exp_[i])) {
            // just digit, assign value
            int elen;
            int res = read(exp_+i, elen);
            
            val += res * sign;
            sign = 1;
            i += elen - 1;
            
        }
        else if(isupper(exp_[i])) {
            // A1+B2.... judge topo cycle?
            int elen;
            int row = exp_[i] - 'A';
            int col = read(exp_+i+1, elen);
            
            if(!canDfs(row, col)) return false;
            
            val += sign * value[row][col];
            
            sign = 1;
            i += elen - 1 + 1;
            // we add 'A', 'B', upper alpha
        }
    }
    
    // then is the true situation
    ok = 1;
    return true;
}


void dfs() {
    //
    memset(vis, 0, sizeof(vis));
    bool cycle = false;
    
    for(int i = 0; i < R; i++) for(int j = 0; j < C; j++) {
        bool ok = canDfs(i, j);
        
        if(!ok) {
            cycle = true;
            printf("%c%d: %s\n", 'A'+i, j, exp[i][j]);
        }
    }
    
    if(cycle) return;
    
    // then we can explain the exp
    printf(" ");
    for(int i = 0; i < C; i++) printf("%6d", i);
    cout << endl;
    
    for(int i = 0; i < R; i++) {
        printf("%c", i+'A');
        for(int j = 0; j < C; j++)
            printf("%6d", value[i][j]);
        cout << endl;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while(true) {
        cin >> R >> C;
        if(R == 0 || C == 0) break;
        
        for(int i = 0; i < R; i++) for(int j = 0; j < C; j++) scanf("%s", exp[i][j]);
        
        // then we run solve()
        dfs();
        cout << endl;
    }
}

状态建图：内存池方法

以骰子为例，程序结构如下：

LA5210

1/ bfs：根据状态建图，类的属性以及成员函数分析如下
因为要输出路径，所以需要保存prev信息
骰子走在棋盘上，需要棋盘信息，和骰子的posture

hash由棋盘位置+骰子posture共同决定
hash值是用来判断这个状态是否vis过

bfs中， queue< Statp > que， 存储状态指针， 更方便判断是否存在最短路径
set< Statp > vis, 用vis.count(nxt)， 判断下一步是否走过了？

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
class Stat {
public:
    int r, c;
    // nr = r + dir[i], nc = c + dir[i]
    // 棋盘信息

    int face, back, top, bottom, left, right;
    // 骰子自己的posture信息

    Stat* prev;

    void Stat(int r_, int c_) : r(r_), c(c_) {}
    // 棋盘位置初始化

    void init(int top, int face) {
        this->top = top;
        this->face = face;
        // 
    }
    // 骰子posture初始化

    int hash() const {
        return 1000 * (r-1) + 100 * (c-1) + 10 * top + face;
    }

    // 棋盘状态+骰子状态，确定状态hash
    // 用于set<Statp, StatCmp> vis, vis.count(nxt)判断下一步路径是否走过
};

2/ 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
typedef Stat* Statp;

class Mempool {
public:
    vector<Statp> buf;

    void create() {
        buf.push_back(new Stat());
        return buf.back();
    }

    void fresh() {
        _for(i, 0, buf.size()) delete buf[i];
        buf.clear();
    }
};

Mempool pools;

class StatCmp {
public:
    bool operator() (const Statp& lhs, const Statp& rhs) const {
        return lhs->hash() < rhs->hash();
    }    
};

StatCmp用法：
状态 = 棋盘位置 + 骰子posture
是否访问过？我们用set < Statp, StatCmp > vis来存储

3/ bfs move信息，获取下一步的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool Stat::canMove(int dir) {
    int nr = r + dr[dir], nc = c + dc[dir];
    if(nr > R || nr < 1 || nc > C || nc < 1) return false;

    int mv = grid[nr][nc];
    return mv == right_pos;
}

Statp Stat::move(int dir) {
    Statp nxt = pools.create();

    // init在棋盘上的位置
    int nr = r + dr[dir], nc = c + dc[dir];
    nxt->prev = this;
    nxt->r = nr; nxt->c = nc;

    // 骰子自身posture需要init
    if(dir == UP) nxt->init(face, bottom);
    // 模拟骰子翻滚的过程

    return nxt;
}

4/ 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
Statp bfs(const Stat& dest, Statp beg) {
    queue<Statp> que;
    set<Statp, StatCmp> vis;

    que.push(beg);
    vis.insert(beg);

    while(!que.empty()) {
        Statp cur = que.front(); que.pop();
        if(cur->r == dest.r && cur->c == dest.c) return cur;

        _for(i, 0, 4) {
            if(cur->canMove(i)) {
                Statp nxt = cur->move(i);

                if(vis.count(nxt)) continue;

                vis.insert(nxt);
                que.push(nxt);
            }
        }
    }
    return null;
}

5/ 技巧：状态信息用Statp来表示
queue< Statp > que, set< Statp, StatCmp> vis
class Mempool { public: vector< Statp > buf; };

bfs无解的时候，可以很容易用if来判断

代码实现

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
//
//  main.cpp
//  DiceyProblem
//
//  Created by zhangmin chen on 2019/4/17.
//  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>

using namespace std;
typedef long long llong;

#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)

// dice[face][top] = left
// check:
// (1, 1) = null, (1, 2) = 3, (1, 3) = 5, (1, 4) = 2, (1, 5) = 4, (1, 6) = null
// (2, 1) = 4, (2, 2) = null, (2, 3) = 1, (2, 4) = 6, (2, 5) = null, (2, 6) = 3
// (3, 1) = 2, (3, 2) = 6, (3, 3) = null, (3, 4) = null, (3, 5) = 1, (3, 6) = 5
// (4, 1) = 5, (4, 2) = 1, (4, 3) = null, (4, 4) = null, (4, 5) = 6, (4, 6) = 2
// (5, 1) = 3, (5, 2) = null, (5, 3) = 6, (5, 4) = 1, (5, 5) = null, (5, 6) = 4
// (6, 1) = null, (6, 2) = 4, (6, 3) = 2, (6, 4) = 5, (6, 5) = 3, (6, 6) = null

const int maxn = 15;

const int dice[6][6] = {
    {-1, 3, 5, 2, 4, -1},
    {4, -1, 1, 6, -1, 3},
    {2, 6, -1, -1, 1, 5},
    {5, 1, -1, -1, 6, 2},
    {3, -1, 6, 1, -1, 4},
    {-1, 4, 2, 5, 3, -1}
};

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, -1, 0, 1};
// {up, left, down, right}

const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
int R, C;
int grid[maxn][maxn];

class Stat {
public:
    int r, c;
    int face, back, top, bottom, left, right;
    Stat* prev;
    // why prev? did we need nxt?
    
    Stat() {
        prev = NULL;
    }
    
    Stat(int r, int c) : r(r), c(c) {}
    
    void init(int top, int face) {
        this->top = top;
        this->face = face;
        
        back = 7 - face;
        bottom = 7 - top;
        
        left = dice[face - 1][top - 1];
        right = 7 - left;
    }
    
    bool canMove(int dir);
    Stat* move(int dir);
    
    // usage: if(canMove(i)) move(i)
    
    int hash() const {
        return 1000 * (r-1) + 100 * (c-1) + 10 * top + face;
    }
};


typedef Stat* Statp;

class MemPool {
public:
    vector<Statp> buf;
    
    Statp create() {
        //
        buf.push_back(new Stat());
        return buf.back();
    }
    
    void fresh() {
        for(int i = 0; i < buf.size(); i++) delete buf[i];
        buf.clear();
    }
};

struct StatCmp {
    //
    bool operator() (const Statp& lhs, const Statp& rhs) const {
        return lhs->hash() < rhs->hash();
    }
};

MemPool pools;

bool Stat::canMove(int dir) {
    //
    int nr = r + dr[dir], nc = c + dc[dir];
    if(nr > R || nr < 1 || nc > C || nc < 1) return false;
    
    int mv = grid[nr][nc];
    if(mv == 0) return false;
    
    return mv == -1 || mv == top;
}

Statp Stat::move(int dir) {
    //
    // usage:
    // if(canMove(dir)) move(dir)
    Statp nxt = pools.create();
    int nr = r + dr[dir], nc = c + dc[dir];
    nxt->prev = this; nxt->r = nr; nxt->c = nc;
    
    if(dir == UP) nxt->init(face, bottom);
    if(dir == LEFT) nxt->init(right, face);
    if(dir == DOWN) nxt->init(back, top);
    if(dir == RIGHT) nxt->init(left, face);
    
    return nxt;
    
}

Statp bfs(const Stat& dest, Statp beg) {
    //
    queue<Statp> que;
    set<Statp, StatCmp> vis;
    
    que.push(beg);
    vis.insert(beg);
    
    while(!que.empty()) {
        Statp cur = que.front(); que.pop();
        if(cur->r == dest.r && cur->c == dest.c)
            return cur;
        
        for(int i = 0; i < 4; i++) {
            if(cur->canMove(i)) {
                Statp nxt = cur->move(i);
                
                if(vis.count(nxt)) continue;
                
                vis.insert(nxt);
                que.push(nxt);
            }
        }
    }
    return NULL;
}


int main() {
    freopen("input.txt", "r", stdin);
    string name;
    deque<Statp> res;
    
    while(cin >> name && name != "END") {
        memset(grid, 0, sizeof(grid));
        cin >> R >> C;
        int tmpR, tmpC, tmpT, tmpF;
        cin >> tmpR >> tmpC >> tmpT >> tmpF;
        
        Stat st(tmpR, tmpC);
        st.prev = NULL;
        st.init(tmpT, tmpF);
        
        for(int i = 1; i <= R; i++) for(int j = 1; j <= C; j++) cin >> grid[i][j];
        cout << name << endl;
        
        // finish init! then bfs()
        
        Statp ans = NULL;
        for(int i = 0; i < 4; i++) {
            if(st.canMove(i)) {
                ans = bfs(st, st.move(i));
                if(ans) break;
            }
        }
        
        if(ans) {
            res.clear();
            while(ans) {
                res.push_front(ans);
                ans = ans->prev;
            }
            
            for(int i = 0; i < res.size(); i++) {
                if(i) {
                    cout << ",";
                    if(i % 9 == 0) cout << endl;
                }
                if(i % 9 == 0) cout << "  ";
                cout << "(" << res[i]->r << "," << res[i]->c << ")";
            }
            cout << endl;
        }
        else
            cout << "  No Solution Possible" << endl;
        pools.fresh();
    }
}

根据bfs和dfs序列重新建树

Tree Reconstruction

UVA10410

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
//
//  main.cpp
//  UVA10410
//
//  Created by zhangmin chen on 2019/3/31.
//  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>

using namespace std;
typedef long long llong;

#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)


const int maxn = 1000 + 5;
int pa[maxn];
int n;

vector<int> bseq, dseq[maxn];
vector<int> G[maxn];

int read() {
    int x;
    scanf("%d", &x);
    return x;
}

void init() {
    bseq.clear();
    for(int i = 0; i < maxn; i++) dseq[i].clear();
    for(int i = 0; i < maxn; i++) G[i].clear();
    memset(pa, 0, sizeof(pa));
}

void dfs(int u, int& bi) {

    // find all sub_nodes
    // the we construct all sub-tree of node v
    // construct dseq[u] -> desq[v] -> dseq[vv]
    
    // i travel all sub node in dfs-seq
    //debug(dseq[u].size());
    
    // bseq[bi] is a direct-child of node u
    // find v == bseq[bi] in dseq[u][]
    // construct child nodes of dseq[v] at the same time!
    
    _for(i, 0, (int)dseq[u].size()) {
        int v = dseq[u][i];
        
        if(bi < n && v == bseq[bi]) {
            bi++;
            G[u].push_back(v);
            pa[v] = u;
            
            for(int j = i+1; j < dseq[u].size() && bi < n; j++) {
                int vv = dseq[u][j];
                if(vv == bseq[bi]) break;
                
                // dseq[v+1] -> vv, each node is sub-node of v
                // refresh dseq[v]
                dseq[v].push_back(vv);
                pa[vv] = v;
            }
        }
    }
    
    
    while(bi < n) dfs(pa[bseq[bi]], bi);
}

int main() {
    //
    freopen("input.txt", "r", stdin);
    while(cin >> n && n) {
        //
        init();
        for(int i = 0; i < n; i++) bseq.push_back(read());
        read();
        for(int i = 1; i < n; i++) dseq[bseq[0]].push_back(read());
        
        // the we deal the problem
        int bi = 1;
        dfs(bseq[0], bi);
        
        for(int i = 1; i <= n; i++) {
            sort(G[i].begin(), G[i].end());
            printf("%d:", i);
            for(int k = 0; k < G[i].size(); k++) {
                printf(" %d", G[i][k]);
            }
            printf("\n");
        }
    }
}

链表模拟题

环形链表处理模版

LA5185
LA5185

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
//
//  main.cpp
//  LA5185
//
//  Created by zhangmin chen on 2019/3/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>

using namespace std;
typedef long long llong;

#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)

const int CNT = 52;
const int maxn = 7;

int read() {
    int x;
    scanf("%d", &x);
    return x;
}

struct Pile {
    deque<int> cards;
    Pile *left, *right;
    
    void init() {
        cards.clear();
        left = right = nullptr;
    }
};

typedef Pile* Pilep;
Pile piles[maxn+1], *nil;
set<string> status;

deque<int> hcards;

void link(Pilep l, Pilep r) {
    l->right = r;
    r->left = l;
}

void start() {
    // init
    hcards.clear();
    status.clear();
    for(int i = 0; i <= maxn; i++) {
        piles[i].init();
    }
}

void deal(Pile& p) {
    int sz = (int)p.cards.size();
    if(sz < 3) return;
    
    if( (p.cards[0]+p.cards[1]+p.cards.back()) % 10 == 0 ) {
        //
        hcards.push_back(p.cards[0]); hcards.push_back(p.cards[1]); hcards.push_back(p.cards.back());
        p.cards.pop_front(); p.cards.pop_front(); p.cards.pop_back();
        deal(p);
        return;
    }
    
    if( (p.cards[0]+p.cards[sz-2]+p.cards[sz-1]) % 10 == 0 ) {
        //
        hcards.push_back(p.cards[0]); hcards.push_back(p.cards[sz-2]); hcards.push_back(p.cards[sz-1]);
        p.cards.pop_front(); p.cards.pop_back(); p.cards.pop_back();
        deal(p);
        return;
    }
    
    if( (p.cards[sz-3]+p.cards[sz-2]+p.cards[sz-1]) % 10 == 0 ) {
        hcards.push_back(p.cards[sz-3]); hcards.push_back(p.cards[sz-2]); hcards.push_back(p.cards[sz-1]);
        p.cards.pop_back(); p.cards.pop_back(); p.cards.pop_back();
        deal(p);
        return;
    }
}

void encode(string& ans) {
    ans.clear();
    Pilep first = nil->right;
    while(first != nil) {
        for(int i = 0; i < first->cards.size(); i++) ans += (char)first->cards[i];
        
        ans += '|';
        first = first->right;
    }
    
    for(int i = 0; i < hcards.size(); i++) ans += (char) hcards[i];
}

void putCard() {
    int cur = hcards.front();
    hcards.pop_front();
    
    Pilep first = nil->right;
    link(nil, first->right);
    link(nil->left, first);
    link(first, nil);
    
    first->cards.push_back(cur);
    deal(*first);
    if(first->cards.empty()) link(first->left, first->right);
}

bool simulate(int times) {
    if(nil->right == nil) {
        cout << "Win : " << times << endl;
        return false;
    }
    if(hcards.empty()) {
        cout << "Loss: " << times << endl;
        return false;
    }
    
    string st;
    encode(st);
    
    if(status.count(st)) {
        //
        cout << "Draw: " << times << endl;
        return false;
    } else {
        status.insert(st);
    }
    
    putCard();
    return true;
}


int main() {
    freopen("input.txt", "r", stdin);
    
    
    while(true) {
        //
        // start()
        start();
        
        nil = &(piles[0]);
        nil->init();
        nil->right = &(piles[1]);
        
        for(int i = 1; i <= CNT; i++) {
            int val = read();
            if(val == 0) return 0;
            
            // get pile
            hcards.push_back(val);
        }
        
        for(int i = 1; i <= 7; i++) {
            Pile& p = piles[i];
            p.init();
            
            // get_link and get_data
            p.left = &(piles[i-1]);
            if(i+1 <= 7) p.right = &(piles[i+1]);
            p.cards.push_back(hcards.front());
            hcards.pop_front();
        }
        
        Pilep last = &(piles[7]);
        link(last, nil);
        //debug(nil->right);
        
        // simulate()
        int t = 7;
        while(true) if(!simulate(t++)) break;
        
    }
}

环形链表模拟：程序结构

一般链表题的程序结构如下：

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
class Pile {
public:
    stack<Card> cards;
    Pile *left, *right;

    void init() {
        while(!cards.empty()) cards.pop();
        left = right = nullptr;
    }
};

typedef Pile* Pilep;

void link(Pilep l, Pilep r) {
    if(l) l->right = r;
    if(r) r->left = l;
}

Pile piles[N + 1];
Pilep nil;

int main() {
    _for(i, 1, N) {
        Pile& p = piles[i];
        p.init();

        p.left = &(piles[i-1]);
        if(i+1 < N) p.right = &(piles[i+1]);
    }
}

具体应用：
UVA127

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
//
//  main.cpp
//  POJ1214
//
//  Created by zhangmin chen on 2019/3/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>

using namespace std;
typedef long long llong;

#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)

const int CNT = 52;

struct Card {
    //
    char suit, rank;
    Card(int s, int r) : suit(s), rank(r) {}
    
    bool operator == (const Card& rhs) const {
        return suit == rhs.suit || rank == rhs.rank;
    }
};

struct Pile {
    // Link-list
    stack<Card> cards;
    Pile *left, *right;
    
    void init() {
        while(!cards.empty()) cards.pop();
        left = right = nullptr;
    }
};
typedef Pile* Pilep;

void link(Pilep l, Pilep r) {
    if(l) l->right = r;
    if(r) r->left = l;
}


Pile piles[CNT+1];
Pilep nil;

// use Linklist to deal piles[CNT]

Pilep getleft3(Pilep cur) {
    for(int i = 0; i < 3; i++) {
        cur = cur->left;
        if(cur == nullptr) return nullptr;
    }
    return cur;
}

void solve() {
    Pilep from, to, cur;
    
    while(true) {
        from = to = nullptr;
        cur = nil->right;
        
        while(cur) {
            //
            Pilep l3 = getleft3(cur);
            if(l3 != nullptr && l3 != nil) {
                //
                if(l3->cards.top() == cur->cards.top()) {
                    from = cur; to = l3;
                    break;
                }
            }
            
            Pilep l1 = cur->left;
            if(l1 != nullptr && l1 != nil) {
                if(l1->cards.top() == cur->cards.top()) {
                    from = cur; to = l1;
                    break;
                }
            }
            
            cur = cur->right;
        }
        
        if(from == nullptr) break;
        to->cards.push(from->cards.top());
        from->cards.pop();
        
        if(from->cards.empty()) link(from->left, from->right);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    
    string str;
    nil = &(piles[0]);
    nil->init();
    nil->right = &(piles[1]);
    
    while(true) {
        for(int i = 1; i <= CNT; i++) {
            //
            if(cin >> str && str.size() == 2) {
                // get str, and card
                Pile& p = piles[i];
                p.init();
                
                p.left = &(piles[i-1]);
                if(i+1 <= CNT) p.right = &(piles[i+1]);
                
                p.cards.push(Card(str[0], str[1]));
                
            }
            else return 0;
        }
        
        // get data
        // then we solve
        
        solve();
        vector<int> ans;
        
        Pilep cur = nil->right;
        while(cur) {
            ans.push_back((int)cur->cards.size());
            cur = cur->right;
        }
        
        printf("%d", (int)ans.size());
        printf(" pile");
        if(ans.size() > 1) printf("s");
        printf(" remaining:");
        
        for(int i = 0; i < ans.size(); i++) {
            printf(" %d", ans[i]);
        }
        
        printf("\n");
    }
}

BFS常见模版题

UVA1600

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

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

#define debug(x) cout << #x << ": " << x << endl
#define Set(x, v) memset(x, v, sizeof(x))
#define REP(i, l, r) for(int i = (l); i <= (r); i++)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

using namespace std;
const int maxn = 24;

int read() {
    int x;
    scanf("%d", &x);
    return x;
}

bool inRange(int x, int l, int r) {
    return l > r ? inRange(x, r, l) : (l <= x && x <= r);
}

int grid[maxn][maxn];
int dist[maxn][maxn][maxn];
// dist(x, y, ob) = dist_pre + 1;


// struct
int k, m, n;
struct POS {
    int x, y, ob;
    POS(int x, int y) : x(x), y(y) {}
};

bool operator== (const POS& a, const POS& b) {
    return a.x == b.x && a.y == b.y;
}


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


int bfs() {
    // x: m    y: n
    POS from(0, 0); POS to(m-1, n-1);
    from.ob = 0;
    Set(dist, -1);
    
    queue<POS> que;
    que.push(from);
    dist[from.x][from.y][from.ob] = 0;
    
    while(!que.empty()) {
        POS& f = que.front(); que.pop();
        //debug(dist[f.x][f.y][f.ob]);
        if(f == to) return dist[f.x][f.y][f.ob];
        int d = dist[f.x][f.y][f.ob];
        
        for(int i = 0; i < 4; i++) {
            int nx = f.x + dx[i];
            int ny = f.y + dy[i];
            
            if(!inRange(nx, 0, m-1) || !inRange(ny, 0, n-1)) continue;
            if(grid[nx][ny] == 1 && f.ob + 1 > k) continue;
            int nob = (grid[nx][ny] == 1) ? f.ob + 1 : 0;
            // i made a bug here
            //debug(nob);
            
            //POS nxt(nx, ny);
            //nxt.ob = nob;
            if(dist[nx][ny][nob] == -1) {
                dist[nx][ny][nob] = d+1;
                POS nxt(nx, ny);
                nxt.ob = nob;
                que.push(nxt);
            }
        }
    }
    return -1;
}

int main() {
    //
    freopen("input.txt", "r", stdin);
    int kase = read();
    while(kase--) {
        m = read();
        n = read();
        k = read();
        // m lines, n cols
        
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                grid[i][j] = read();
        
        // then bfs()
        int ans = bfs();
        printf("%d\n", ans);
    }
}


欧拉路径和连通分量的综合应用

LA4059
LA4059

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
//
//  main.cpp
//  LA4059
//
//  Created by zhangmin chen on 2019/5/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>

using namespace std;
typedef long long llong;
const int maxn = 1000 + 10;

#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)

vector<int> G[maxn];
int vis[maxn];

int V, E, T;
void init() {
    _for(i, 0, maxn) G[i].clear();
    Set(vis, 0);
}

int dfs(int u) {
    if(vis[u]) return 0;
    vis[u] = 1;
    
    int P = G[u].size() % 2;
    _for(i, 0, G[u].size()) {
        int v = G[u][i];
        P += dfs(v);
    }
    return P;
}

// cc:
/*
 int main()
     _for(i, 0, N)
        if(vis[i] || G[i].empty()) continue;
        cc++;
        res += max(0, (dfs(i)-1) / 2)
 */

int main() {
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    for(int from, to, kase = 1; cin >> V >> E >> T && V; kase++) {
        init();
        _for(i, 0, E) {
            cin >> from >> to;
            G[from-1].push_back(to-1);
            G[to-1].push_back(from-1);
        }
        
        int cc = 0, res = E;
        _for(i, 0, V) {
            if(vis[i] || G[i].empty()) continue;
            cc++;
            res += max(0, (dfs(i) - 2) / 2);
        }
        printf("Case %d: %d\n", kase, T*(res + max(0, cc-1)));
    }
}

数据结构和算法的模版已经给出。
接下来还有一些高级数据结构，以后再总结