算法竞赛入门经典第七章习题(18/18)

题解都能写吐🤮

下次我一定边做题边写题解

gogogo，第九章就在眼前

Firetruck

UVA - 208

题意：输入n个节点的无向图，和节点k，按字典序输出从节点1到节点k的所有路径

题解：暴力搜索即可, 提前判断节点能否到达1，否则会T， pdf样例有误， 看udebug

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-03 21:03:11
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << "Debug: " << *it << " = " << a << endl;
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
istringstream it(_s);err(istream_iterator<string>(it), args);}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 30, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int n, fa[Ma];
bool g[Ma][Ma];
int find(int u) {return fa[u] = fa[u] == u ? u : find(fa[u]);}
void unio(int a, int b) {
	int p1 = find(a), p2 = find(b);
	if (p1 == p2) return ;
	fa[p2] = p1;
}

int ans[Ma], inn[Ma];

void init() {
	rep (i, Ma) fa[i] = i, inn[i] = 0;
	memset(g, 0, sizeof g);
}

int dfs(int u, int cur, const int& v) {
	if (u == v) {
		rep (i, cur)
			printf("%d ", ans[i]);
		printf("%d\n", v);
		return 1;
	}
	inn[u] = 1; int cnt = 0; ans[cur] = u;
	rep (i, Ma) if (g[u][i] and !inn[i])
		cnt += dfs(i, cur + 1,  v);
	inn[u] = 0;
	return cnt;
}

int solve() {
	if (find(1) != find(n)) return 0;
	return dfs(1, 0, n);
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int k = 0;
	while (scanf("%d", &n) == 1) {
		init();
		int u, v;
		while (scanf("%d%d", &u, &v) == 2 and u)
			g[u][v] = g[v][u] = true, unio(u, v);
		printf("CASE %d:\n", ++k);
		printf("There are %d routes from the firestation to streetcorner %d.\n", solve(), n);
	}
    
    return 0;
}

Golygons

UVA - 225

题意：第一步走一步，第二步走两步..... 让你走出一个多边形，按字典序输出方案， 图像可以自交， 但不能经过障碍点， 且只能转90度

题解：注意条件，dfs即可, 可用位运算进行一些细节优化

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-07 09:29:40
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << "Debug: " << *it << " = " << a << endl;
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
istringstream it(_s);err(istream_iterator<string>(it), args);}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { int x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 120, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m, ans[Ma * 2];

bool vis[Ma * 2][Ma * 2], mz[Ma * 2][Ma * 2];

void init() {
	memset(vis, 0, sizeof vis);
	memset(mz, 0, sizeof mz);
}

const int dx[] = {1, 0, 0, -1},
		  dy[] = {0, 1, -1, 0};
const char aim[] = {'e', 'n', 's', 'w'};

bool judge(int x, int y, int xx, int yy, int dir, int cur) {
	if (mz[x + Ma][y + Ma] or mz[xx + Ma][yy + Ma]) return false;
	if ((xx != 0 or yy != 0 or cur + 1 != n) and vis[xx + Ma][yy + Ma])
		return false;
	while (!(x == xx and y == yy)) {
		x += dx[dir], y += dy[dir];
		if (mz[x + Ma][y + Ma]) return false;
	}
	return true;
}

inline bool check(int now, int pre) {
	int t = now ^ pre;
	return t != 3 and t != 0;
}

int dfs(int x, int y, int cur) {
	if (cur == n) {
		if (!(x == 0 and y == 0)) return 0;
		rep (i, cur) cout << aim[ans[i]]; cout << endl;
		return 1;
	}
	int cnt = 0; vis[x + Ma][y + Ma] = true;
	rep (i, 4) if (!cur or check(i, ans[cur - 1])) {
		int nx = x + dx[i] * (cur + 1), ny = y + dy[i] * (cur + 1);
		if (!judge(x, y, nx, ny, i, cur)) continue;
		ans[cur] = i;
		cnt += dfs(nx, ny, cur + 1);
	}
	vis[x + Ma][y + Ma] = false;
	return cnt;
}

signed main() {
	#if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T; cin >> T;
	while (T--) {
		cin >> n >> m;
		init(); int x, y;
		rep (i, m) {
			cin >> x >> y;
			mz[x + Ma][y + Ma] = true;
		}
		int t = dfs(0, 0, 0);
		cout << "Found " << t << " golygon(s)." << endl << endl;
	}
    
    return 0;
}

The Domino Effect

UVA - 211

题意：让你把多米诺放在给出棋盘中的方案，在对应格子中写入相应编号

题解：直接搜索即可，注意输出

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-08 09:45:01
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 10, inf = 0x3f3f3f3f, mod = 1e9 + 7;

inline void spe() {
	puts("\n\n\n");
}

int mz[Ma][Ma];

bool read() {
	rep (i, 7) rep (j, 8)
		if (scanf("%d", &mz[i][j]) != 1) return false;
	return true;
}

void print() {
	rep (i, 7) {
		rep (j, 8) printf("   %d", mz[i][j]);
		puts("");
	}
}

int ans[Ma * Ma], bone[Ma][Ma];
bool vis[30];

void init() {
	int cnt = 0;
	rep (i, 7) fep (j, i, 7)
		bone[i][j] = bone[j][i] = ++cnt;
}

const int ngo[] = {1, 8};

inline int gmz(int t) {
	return mz[t / 8][t % 8];
}

inline bool judge(int now, int nex) {
	if (nex >= 7 * 8 or ans[nex]) return false;
	if (nex - 1 == now) return now / 8 == nex / 8  and
						!vis[bone[gmz(now)][gmz(nex)]];
	return now / 8 + 1 == nex / 8 and
		   !vis[bone[gmz(now)][gmz(nex)]];
}

int dfs(int now) {
	if (now == 7 * 8) {
		puts("");
		rep (i, 7) {
			rep (j, 8) printf("  %2d", ans[i * 8 + j]);
			puts("");
		} return 1;
	}
	/*if (now == 38) {
	   	debug(ans[38], ans[30]);
		debug(gmz(38), gmz(30));
	}*/
	if (ans[now]) return dfs(now + 1);
	int cnt = 0;
	rep (i, 2) if (judge(now, now + ngo[i])) {
		ans[now] = ans[now + ngo[i]] = bone[gmz(now)][gmz(now + ngo[i])];
		vis[ans[now]] = true;
		cnt += dfs(now + 1);
		vis[ans[now]] = false;
		ans[now] = ans[now + ngo[i]] = 0;
	}	
	return cnt;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	init();
	int k = 0;
	while (read()) {
		memset(vis, 0, sizeof vis);
		if (k) spe();
		printf("Layout #%d:\n\n", ++k);
		print();
		puts("");
		printf("Maps resulting from layout #%d are:\n", k);
		printf("\nThere are %d solution(s) for layout #%d.\n", dfs(0), k);
	}
    
    return 0;
}

Cutting Chains

UVA - 818

题意：给你几个圆环，让你剪开其中的几个，再接上，使得所有圆环连成一条链

题解：ida*搜索打开的圆环，判下是否有环连接多余两个环，暴力判是否成链，最后看最终连通块是否多于打开圆环数加一

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-09 15:31:37
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << "Debug: " << *it << " = " << a << endl;
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

#define state(x) (1<<(x))

const int Ma = 20, inf = 0x3f3f3f3f, mod = 1e9 + 7;

bool g[Ma][Ma];
int mark[Ma], n;
bool vis[Ma];

bool read() {
	cin >> n;
	if (!n) return false;
	int a, b;
	memset(g, 0, sizeof g);
	memset(mark, 0, sizeof mark);
	while (cin >> a >> b) {
		if (a < 0) break;
		--a, --b;
		g[a][b] = g[b][a] = true;
		mark[a] |= state(b);
		mark[b] |= state(a);
	}
	return true;
}

bool dfs (int u, int fa, int open) {
	vis[u] = true;
	rep (i, n) {
		if ((open >> i) & 1) continue;
		if (g[u][i] == 0 or i == fa) continue;
		if (vis[i] or dfs(i, u, open)) return true;
	}
	return false;
}

bool check(int open) {
	for (int i = 0; i < n; i++) {
		if ((open >> i) & 1) continue;
		int t = mark[i] ^ (mark[i] & open);
		//debug(t);
		if (__builtin_popcount(t) > 2) return false;
	}
	int cnt = 0;
	memset(vis, 0, sizeof vis);
	rep (i, n) {
		if ((open >> i) & 1) continue;
		if (!vis[i]) {
			if (dfs(i, -1, open)) return false;
			++cnt;
		}
	}
	//debug(cnt, open, __builtin_popcount(open));
	return __builtin_popcount(open) >= cnt - 1;
}

bool dfs(int d, const int& maxd, int open, int pre) {
	if (d == maxd) {
		return check(open);
	}
	if (pre + d < maxd) return false;
	for (; pre >= 0; --pre) {
		if (dfs(d + 1, maxd, open | state(pre), pre)) return true;
	}
	return false;
}

signed main() {
	#if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int k = 0;
	while (read()) {
		int maxd;
		for (maxd = 0; !dfs(0, maxd, 0, n); ++maxd);
		cout << "Set " << ++k << ": Minimum links to open is " << maxd << endl;
	}
    
    return 0;
}

Pipeline Scheduling

UVA - 690

题意：你有五个工作单元，和10个程序，每个程序需要n个时间片来完成，同时给出了每个时间片需要的单元，同一个工作单元不能执行多于一个程序，问你执行完所有程序最少需要多少个时间片

题解：预处理可以安全的时间间隔，搜索时进行check，当用最小时间间隔也无法优于答案时进行最优性剪枝

code 
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
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-14 14:39:43
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

#define state(x) (1<<(x))

const int Ma = 25, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int n;
char mz[6][Ma];
int mark[5], ans;
int jump[Ma], cnt;

bool judge(int *t, int k) {
	rep (i, 5) if ((t[i] >> k) & mark[i]) return false;
	return true;
}

void init() {
	cnt = 0;
	rep (i, 5) {
		mark[i] = 0;
		rep (j, n) if (mz[i][j] == 'X')
			mark[i] |= state(j);
	}
	ans = inf;
	rep (i, n + 1) {
		if (judge(mark, i)) jump[cnt++] = i;
	}
}

void dfs(int* te, int d, int tot) {
	if (tot + jump[0] * (10 - d) > ans) return ;
	if (d == 10) {
		cmin(ans, tot);
		return ;
	}

	rep (i, cnt) {
		if (judge(te, jump[i])) {
			int temp[5];
			rep (j, 5) temp[j] = (te[j] >> jump[i]) | mark[j];
			dfs(temp, d + 1, tot + jump[i]);
		}
	}
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	while (scanf("%d", &n) == 1 and n) {
		rep (i, 5) scanf("%s", mz[i]);
		init();
		dfs(mark, 1, n);
		printf("%d\n", ans);
	}
    
    return 0;
}
```	
</details>

## Overlapping Squares

[UVA - 12113](https://vjudge.net/problem/UVA-12113)

题意：问你能否用2*2的方块堆出给出图形

题解：4*4中放置2 * 2的方块只有9种方案，暴力搜索即可, 注意放置2 * 2方块时的覆盖，有些不一样，搞了好久才明白

<details>
<summary>code</summary>
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-14 19:45:03
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 20, inf = 0x3f3f3f3f, mod = 1e9 + 7;

char mz[Ma][Ma], ju[Ma][Ma];

bool input() {
	rep (i, 5) {
		fgets(mz[i], Ma * Ma, stdin);
		if (mz[i][0] == '0') return false;
	}
	memset(ju, ' ', sizeof ju);
	return true;
}

bool judge() {
	rep (i, 5) rep (j, 9)
		if (ju[i][j] != mz[i][j]) return false;
	return true;
}

void print() {
	cout << "------------------" << endl;
	rep (i, 5) ju[i][Ma - 2] = 0;
	rep (i, 5) cout << ju[i] << endl;
}

void full(int r, int c) {
	ju[r][c + 1] = ju[r][c + 3] = 
	ju[r + 2][c + 1] = ju[r + 2][c + 3] = '_';
	ju[r + 1][c] = ju[r + 1][c + 4] = 
	ju[r + 2][c] = ju[r + 2][c + 4] = '|';
	ju[r + 1][c + 1] = ju[r + 1][c + 2] = ju[r + 1][c + 3] = 
	ju[r + 2][c + 2] = ' ';
}

bool dfs(int step) {
	if (judge()) return true;
	if (step >= 6) return false;
	char temp[Ma][Ma];
	memcpy(temp, ju, sizeof ju);
	rep (i, 3) rep (j, 3) {
		full(i, j * 2);
		if (dfs(step + 1)) return true;
		memcpy(ju, temp, sizeof temp);
	}
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int ca = 0;
	while (input()) {
		printf("Case %d: ", ++ca);
		if (dfs(0)) puts("Yes");
		else puts("No");
	}
    
    return 0;
}
</details>

## Egyptian Fractions (HARD version)

[UVA - 12558](https://vjudge.net/problem/UVA-12558)

题意：八数码问题种加入了一些不能用的数

题解：还是经典问题，套上八数码的IDA*后判一下特殊数据即可，题目保证了数据易于求解 <del>lrj,tql</del>

<details>
<summary>code</summary>
```cpp
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-26 20:13:43
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 1e3 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7;
cc_hash_table<ll, null_type> se;
int maxd; ll ans[Ma], v[Ma];

ll get_first(ll a, ll b) {
	return (b / a) + 1;
}

bool better(int d) {
	for (int i = d; i >= 0; i--) if (v[i] != ans[i])
		return ans[i] == -1 or v[i] < ans[i];
	return false;
}

bool dfs(int d, ll from, ll a, ll b) {
	if (d == maxd) {
		if (b % a or se.find(b / a) != se.end()) return false;
		v[d] = b / a;
		if (better(d)) memcpy(ans, v, sizeof(ll) * (d + 1));
		return true;
	}
	bool win = false;
	for (int i = max(from, get_first(a, b)); ; ++i) {
		if (b * (maxd - d + 1) <= i * a) break;
		if (se.find(i) != se.end()) continue;
		v[d] = i;
		ll bb = b * i, aa = a * i - b;
		ll g = __gcd(aa, bb);
		if (dfs(d + 1, i + 1, aa / g, bb / g)) win = true;
	}
	return win;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T; scanf("%d", &T);
	rep (ca, T) {
		ll a, b; int k; scanf("%lld%lld%d", &a, &b, &k);
		se.clear(); ll t;
		rep (i, k) scanf("%lld", &t), se.insert(t);
		maxd = 0;
		for (maxd = 1; memset(ans, -1, sizeof ans), !dfs(0, get_first(a, b), a, b);
			   	++maxd);
		printf("Case %d: %d/%d=", ca + 1, a, b);
		rep (i, maxd + 1) printf("1/%lld%c", ans[i], "+\n"[i == maxd]);
	}
    
    return 0;
}

Digit Puzzle

UVA - 12107

题意：让你求解字符，达成** X ** = * * * *，且只有唯一解 输出字典序最小的方案

题解：不能删除或添加，只能修改，直接搜即可，注意无前导0。 判断有无多解再次暴力一遍即可，枚举乘数check积

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-27 09:51:41
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 100, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int maxd;
char cs[4][Ma];

const char base[] = {'*', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

int tot;

void print() {
	printf(" %s %s %s\n", cs[0], cs[1], cs[2]);
}

bool judge() {
	int a = 0, b = 0;
	for (int i = 0; cs[0][i]; ++i) a *= 10, a += cs[0][i] - '0';
	for (int i = 0; cs[1][i]; ++i) b *= 10, b += cs[1][i] - '0';
	a *= b;
	for (int i = tot - 1; i >= 0; --i) {
		if (cs[2][i] != '*' and cs[2][i] - '0' != a % 10) return false;
		if (cs[2][i] == '*' and !a) return false;
		a /= 10;
	}
	return a == 0;
}

int check(int k1, int k2) {
	if (cs[k1][k2] == 0) k1 += 1, k2 = 0;
	if (k1 == 2) return judge();
	if (cs[k1][k2] != '*') return check(k1, k2 + 1);
	int cnt = 0;
	char bac = cs[k1][k2];
	fep (i, 1, 11) {
		if (i == 1 and k2 == 0) continue;
		cs[k1][k2] = base[i];
		cnt += check(k1, k2 + 1);
		if (cnt > 1) break;
	}
	cs[k1][k2] = bac;
	return cnt;
}

bool dfs(int d, int k1, int k2) {
	assert(maxd <= 8);
	if (d == maxd) {
		if (check(0, 0) == 1) return print(), true;
		else return false;
	}
	if (cs[k1][k2] == 0) k1 += 1, k2 = 0;
	if (k1 > 2) return false;
	char bac = cs[k1][k2];
	rep (i, 11) {
		if (i == 1 and k2 == 0) continue;
		cs[k1][k2] = base[i];
		if (dfs(d + (base[i] != bac), k1, k2 + 1)) return true;
	}
	cs[k1][k2] = bac;
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int qq = 0;
	while (scanf("%s%s%s", cs[0], cs[1], cs[2]) == 3) {
		tot = strlen(cs[2]);
		printf("Case %d:", ++qq);
		for (maxd = 0; !dfs(0, 0, 0); ++maxd);
	}
    
    return 0;
}

Cubic Eight-Puzzle

UVA - 1604

题意：立体八数码，只要求俯视图相同，多余三十步输出-1

题解：只要求三十步以内，建立初始节点，开始滚就行，注意不要往回滚，使用IDA*，当不同数量多于maxd - 当前深度时剪枝

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-29 10:33:01
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 100, inf = 0x3f3f3f3f, mod = 1e9 + 7;

enum {
	White,
	Red,
	Blue
};

struct Node {
	int top, front, left;
	Node (int top=White, int front=Red, int left=Blue) :
	   	top(top), front(front), left(left) {}
	Node gl() {
		return Node(left, front, top);
	}
	Node gf() {
		return Node(front, top, left);
	}
};

typedef Node eight[4][4];

int ans;
eight goal, be;
int r, c;
int id[Ma];

bool read() {
	if (scanf("%d%d", &c, &r) != 2 or c + r == 0) return false;
	--r, --c;
	rep (i, 3) rep (j, 3) {
		char s[Ma];
		scanf("%s", s);
		goal[i][j] = Node(id[s[0]]);
		be[i][j] = Node();
	}
	be[r][c] = Node(-1);
	return true;
}

int check() {
	int cnt = 0;
	rep (i, 3) rep (j, 3) {
		if (be[i][j].top != goal[i][j].top) ++cnt;
	}
	return cnt;
}

const int xz[] = {1, -1, 0, 0},
	  	  yz[] = {0, 0, 1, -1};

bool check(int x, int y) {
	return x >= 0 and x < 3 and y >= 0 and y < 3;
}

void dfs(int R, int C, int fa, int d) {
	int diff = check();
	if (d + diff >= ans) return ;
   	if (diff == 0) return cmin(ans, d), void();
	rep (i, 4) {
		if (i == fa) continue;
		int rr = R + xz[i], cc = C + yz[i];
		if (check(rr, cc)) {
			Node bf = be[rr][cc];
			be[rr][cc] = Node(-1);
			be[R][C] = (i > 1 ? bf.gl() : bf.gf());
			dfs(rr, cc, i ^ 1, d + 1);
			be[rr][cc] = bf;
			be[R][C] = Node(-1);
		}
	}
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	id['W'] = White, id['R'] = Red, id['B'] = Blue;
	id['E'] = -1;
	while (read()) {
		ans = 32;
		dfs(r, c, -1, 0);
		printf("%d\n", ans == 32 ? -1 : ans);
	}
    
    return 0;
}

Guarding the Chessboard

UVA - 11214

题意：用最少的皇后占据或进攻所有带标记点

题解：八皇后升级版，暴力搜即可，当一个点能走到之前之前不能到的地方就得搜

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-29 14:48:43
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 12, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int re[Ma * 2], er[Ma * 2], ha[Ma], li[Ma];

char mz[Ma][Ma];

int R, C;

bool read() {
	if (scanf("%d%d", &R, &C) != 2) return false;
	rep (i, R) scanf("%s", mz[i]);
	return true;
}

bool check(int r, int c) {
	return r >= 0 and r < R and c >= 0 and c < C and
		   (!ha[r] or !li[c] or !re[r + c] or !er[r - c + Ma]);
}

bool check() {
	rep (i, R) rep (j, C) if (mz[i][j] == 'X' and !ha[i] and !li[j] and
			!re[i + j] and !er[i - j + Ma]) return false;
	return true;
}

bool dfs(int d, const int& maxd, int r, int c) {
	if (d == maxd) return check();
	fep (i, r, R) fep (j, i == r ? c : 0, C) if (check(i, j)) {
		ha[i] += 1, li[j] += 1, re[i + j] += 1, er[i - j + Ma] += 1;
		if (dfs(d + 1, maxd, i, j + 1)) return true;
		ha[i] -= 1, li[j] -= 1, re[i + j] -= 1, er[i - j + Ma] -= 1;
	}
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int opp = 0;
	while (read()) {
		printf("Case %d: ", ++opp);
		int maxd;
		for (maxd = 1; memset(re, 0, sizeof re), memset(er, 0, sizeof er),
				memset(ha, 0, sizeof ha), memset(li, 0, sizeof li), 
				!dfs(0, maxd, 0, 0); maxd++);
		printf("%d\n", maxd);
	}
    
    return 0;
}

Planning mobile robot on Tree (EASY Version)

UVA - 12569

题意：机器人要去目标点，但路上有许多石头，每一步可以移动石头，也可以移动机器人，问你最小步数和路径

题解：因为n<=15, 所以可暴力。把所有石头和机器人的位置压缩为点建立隐式图，在图上搜索即可

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-29 16:11:25
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 20, inf = 0x3f3f3f3f, mod = 1e9 + 7;

#define state(x) (1<<x)

int n, m, s, t;

typedef tuple<int, int, int, int, int> node;
node st[(int)2e6];

vector<int> g[Ma];

cc_hash_table<int, null_type> look;

void init() {
	look.clear();
}

inline int Hash(node t) {
	return (get<0>(t) << 4) | get<1>(t);
}

inline bool try_to_insert(int id) {
	if (look.find(Hash(st[id])) != look.end()) return false;
	else return look.insert(Hash(st[id])), true;
}

void print(int now) {
	vector<pa> ans;
	while (~get<2>(st[now])) {
		ans.ep(mkp(get<3>(st[now]), get<4>(st[now])));
		now = get<2>(st[now]);
	}
	printf("%d\n", (int)ans.size());
	for (auto i = ans.rbegin(); i != ans.rend(); ++i)
		printf("%d %d\n", i->F + 1, i->S + 1);
}

bool bfs() {
	init();
	int front = 0, rear = 1;
	while (front < rear) {
		if (get<1>(st[front]) == t) return print(front), true;
		rap (i, g[get<1>(st[front])]) if (!(state(i) & get<0>(st[front])) and
										i != get<1>(st[front])) {
			//debug(i);
			st[rear] = mkt(get<0>(st[front]), i, front, get<1>(st[front]), i);
			if (try_to_insert(rear)) ++rear;
		}
		rep (i, n) if (state(i) & get<0>(st[front])) {
			rap (j, g[i]) if (!(state(j) & get<0>(st[front])) and
							  j != get<1>(st[front])) {
				//debug(i, j);
				st[rear] = mkt(get<0>(st[front]) ^ state(i) ^ state(j),
							   get<1>(st[front]), front, i, j);
				if (try_to_insert(rear)) ++rear;
			}
		}
		++front;
	}
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T; scanf("%d", &T);
	rep (qq, T) {
		scanf("%d%d%d%d", &n, &m, &s, &t);
		--s, --t;
		st[0] = mkt(0, s, -1, -1, s);
		rep (i, m) {
			int pp; scanf("%d", &pp);
			get<0>(st[0]) |= state(--pp);
		}
		rep (i, n) g[i].clear();
		rep (i, n - 1) {
			int u, v; scanf("%d%d", &u, &v);
			--u, --v;
			g[u].ep(v), g[v].ep(u);
		}
		printf("Case %d: ", qq + 1);
		if (!bfs()) puts("-1");
		puts("");
	}
    
    return 0;
}

Moving Pegs

UVA - 1533

题意：给你一个15个洞的跳棋盘，指定一个点为空，让你开始跳，使得最终只有初始点有球，其他全为空，问你最少步数和方案

题解：一开始不明白跳棋规则，死活卡在样例，跳棋能往周围六个方向跳，且必须隔着至少一个球，跳入空洞，且不能跳过空洞

明白规则后就变为在隐式图上的bfs了

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-30 09:18:40
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ';
    err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 1e6, inf = 0x3f3f3f3f, mod = 1e9 + 7;
#define state(x) (1<<(x))
typedef tuple<int, int, int, int> node;
node tp[Ma];

const int id[][5] = {
	{1, 3, 6, 10, 15},
	{2, 5, 9, 14},
	{4, 8, 13},
	{7, 12},
	{11}
};
const int len[] = {5, 4, 3, 2, 1};

tuple<int, int> getrc(int aim) {
	assert(aim > 0 and aim < 16);
	rep (i, 5) rep (j, len[i]) if (aim == id[i][j]) return {i, j};
	return {0, 0};
}

void print(int aim) {
	vector<pa> ans;
	while (~get<1>(tp[aim])) {
		ans.ep(mkp(get<2>(tp[aim]), get<3>(tp[aim])));
		aim = get<1>(tp[aim]);
	}
	printf("%d\n", (int)ans.size()); auto tt = --ans.rend();
	for (auto i = ans.rbegin(); i != ans.rend(); ++i) printf("%d %d%c", i->F, i->S, " \n"[i == tt]);
}

const int xz[] = {0, -1, 1, -1, 1, 0},
	  	  yz[] = {-1, 0, -1, 1, 0, 1};

inline int go(int r, int c, int rr, int cc, int w, int base) {
	while (r != rr or c != cc) {
		base |= state(id[r][c] - 1);
		r += xz[w], c += yz[w];
	}
	assert(r == rr and c == cc);
	base ^= state(id[rr][cc] - 1);
	return base;
}

bool check(int r, int c) {
	return r >= 0 and r < 5 and c >= 0 and c < len[r];
}

bool vis[Ma];

bool bfs(int n) {
	memset(vis, 0, sizeof vis);
	int front = 0, rear = 1;
	tp[front] = mkt(state(n - 1), -1, -1, n);
	vis[state(n - 1)] = true;
	while (front < rear) {
		int st = get<0>(tp[front]);
		if (__builtin_popcount(st) == 14 and !(st & state(n - 1))) return print(front), true;
		//debug(bitset<15>(st), __builtin_popcount(st), get<3>(tp[front]));
		//debug();
		for (int i = 0; i < 15; i++) if (!(st & state(i))) {
			int r, c; tie(r, c) = getrc(i + 1);
			rep (j, 6) {
				int rr = r + xz[j], cc = c + yz[j];
				bool first = false;
				while (check(rr, cc)) {
					if ((st & state(id[rr][cc] - 1))) {
						if (!first) break;
						int temp = go(r, c, rr, cc, j, st);
						if (!vis[temp]) {
							vis[temp] = true;
							tp[rear++] = mkt(temp, front, i + 1, id[rr][cc]);
						}
						break;
					} else first = true;
					rr += xz[j], cc += yz[j];
				}
			}	
		}
		++front;
	}
	return false;
}

signed main() {
    #if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T; scanf("%d", &T);
	while (T--) {
		int n; scanf("%d", &n);
		if (!bfs(n)) puts("IMPOSSIBLE");
	}
    
    return 0;
}

According to Bartjens

UVA - 817

题意：给你个数字，让你在其中加入+-*使得答案为2000，按字典序输出所有方案

题解：注意没有前导零，和之前哪个猜谜比较像，注意必须要有一个符号，所以2000=是IMPOSSIBLE 先写个表达式解析器，不断添加，check即可

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-30 16:23:55
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ';
    err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 12, inf = 0x3f3f3f3f, mod = 1e9 + 7;

const char op[] = {'*', '+', '-'};

char s[Ma], cal[Ma * 2];
int tot;

int h(int aim) {
	return tot - aim;
}

bool check(char t) {
	rep (i, 3) if (t == op[i]) return true;
	return false;
}

int parse(char* a, int len) {
	int mid = -1, ch = -1;
	//rep (i, len) putchar(a[i]);
	//putchar('\n');
	rep (i, len) {
		if ((i and a[i] == '-') or a[i] == '+') {
			mid = i;
			break;
		}
		if (a[i] == '*') ch = i;
	}
	if (mid != -1) {
		if (a[mid] == '+') return parse(a, mid) + parse(a + mid + 1, len - mid - 1);
		else return parse(a, mid) + parse(a + mid, len - mid);
	}
	if (ch != -1) return parse(a, ch) * parse(a + ch + 1, len - ch - 1);
	int ans = 0, aim = 1; if (a[0] == '-') aim = -1, ++a;
	rep (i, len - (aim == -1)) ans *= 10, ans += a[i] - '0';
	//debug(ans*aim, ans);
	return ans * aim;
}

bool check() {
	return parse(cal, strlen(cal)) == 2000;
}

int clen;
bool can;

void dfs(const int& maxd, int d, int from) {
	int pre = clen;
	if (d > 8 or from >= tot) return ;
	auto chec = [&]() {
		if (from >= tot or (s[from] == '0' and from != tot - 1)) return ;
		fep (i, from, tot) cal[clen++] = s[i];
		cal[clen] = 0;
		if (check()) can = true, printf("  %s=\n", cal);
		clen = pre;
		return ;
	};
	if(d)chec();
	fep (i, from, tot) {
		fep (j, from, i + 1) cal[clen++] = s[j];
		rep (j, 3) {
			cal[clen++] = op[j];
			dfs(maxd, d + 1, i + 1);
			--clen;
		}
		clen = pre;
		if (s[from] == '0') break;
	}
}

signed main() {
    #if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int qq = 0;
	//char tpp[100] = "2-6-8-3*692+64";
	//cout << parse(tpp, strlen(tpp)) << endl;
	while (scanf("%s", s) == 1 and s[0] != '=') {
		printf("Problem %d\n", ++qq);
		tot = strlen(s) - 1;
		can = false;
		clen = 0;
		dfs(8, 0, 0);
		if (!can) puts("  IMPOSSIBLE");
	}
    
    return 0;
}

Sticks

UVA - 307

题意：给你一堆砍过后的小木棍，问你最小可能的原始长度，使每根小木棍长度相同

题解：先将小木棍排序，枚举原始长度，每根木棍从小到大搜，从最大向前凑齐原始木棍，当某根木棍无法组成原始木棍时就可剪去，因为之后的木棍指挥比当前大，不可能组成，单调性剪枝

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-30 18:16:03
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ';
    err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 110, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int a[Ma], n;
bool vis[Ma];

bool dfs(const int aim, int pre, int f, int cur) {
	if (cur == n) return true;
	for (int i = f; i >= 0; i--) if (!vis[i]) {
		if (pre + a[i] < aim) {
			vis[i] = true;
			if (dfs(aim, pre + a[i], i - 1, cur + 1)) return true;
			vis[i] = false;
			while (i > 0 and a[i] == a[i - 1]) --i;
		} else if (pre + a[i] == aim) {
			vis[i] = true;
			if (dfs(aim, 0, n - 1, cur + 1)) return true;
			return vis[i] = false;
		}
		if (pre == 0) return false;
	}
	return false;
}

signed main() {
    #if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	while (scanf("%d", &n) == 1 and n) {
		int all = 0; memset(vis, 0, sizeof vis);
		rep (i, n) scanf("%d", a + i), all += a[i];
		sort(a, a + n);
		for (int i = n; i >= 1; i--) {
			if (all % i == 0 and a[n - 1] <= all / i and dfs(all / i, 0, n - 1, 0)) {
				printf("%d\n", all / i);
				break;
			}
		}
	}

    
    return 0;
}

Biggest Number

UVA - 11882

题意：给你一个矩阵，有障碍物和数字格，从一个数字格走到其他数字格的路径形成一个数字，问你能得到的最大整数

题解：以每个数字为开头进行搜索，当当前所有可能能到达的数字格的最大值小于答案时进行最优性剪枝

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-05-01 09:23:10
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ';
    err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 32, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int R, C;
char mz[Ma][Ma];
char ans[Ma], tpp[Ma];
int la, lt;
bool vis[Ma][Ma];

bool check(char* gz, char* so) {
	if (strlen(so) > strlen(gz)) return true;
	if (strlen(so) == strlen(gz) and strcmp(gz, so) < 0) return true;
	return false;
}

vector<char> tep;

const int xd[] = {1, -1, 0, 0},
	  	  yd[] = {0, 0, 1, -1};

bool check(int r, int c) {
	return r >= 0 and r < R and c >= 0 and c < C and !vis[r][c] and mz[r][c] != '#';
}

bool vvs[Ma][Ma];

void bfs(int r, int c) {
	memset(vvs, 0, sizeof vvs);
	queue<pa> q; q.emplace(mkp(r, c));
	vvs[r][c] = true; tep.clear();
	while (!q.empty()) {
		pa t = q.front(); q.pop();
		rep (i, 4) {
			int rr = t.F + xd[i], cc = t.S + yd[i];
			if (check(rr, cc) and !vvs[rr][cc]) {
				vvs[rr][cc] = true;
				tep.ep(mz[rr][cc]);
				q.emplace(mkp(rr, cc));
			}
		}
	}
}

void dfs(int r, int c) {
	if (check(ans, tpp)) la = lt, memcpy(ans, tpp, sizeof tpp);
	//debug("totpre", tpp, lt);
	{
		bfs(r, c);
		if (tep.size() + lt < la) return ;
		sort(seg(tep));
		int res = tep.size();
		rep (i, res) {
			tpp[lt++] = tep.back();
			tep.pop_back();
		}
		tpp[lt] = 0;
		if (check(tpp, ans)) return tpp[lt - res] = 0, lt -= res, void();
		tpp[lt - res] = 0;
		lt -= res;
	}
	rep (i, 4) {
		int rr = r + xd[i], cc = c + yd[i];
		if (check(rr, cc)) {
			vis[rr][cc] = true;
			tpp[lt++] = mz[rr][cc];
			tpp[lt] = 0;
			//debug(tpp, lt);
			dfs(rr, cc);
			tpp[--lt] = 0;
			vis[rr][cc] = false;
		}
	}
}

signed main() {
    #if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	while (scanf("%d%d", &R, &C) == 2 and R + C) {
		rep (i, R) scanf("%s", mz[i]);
		la = 0; memset(ans, 0, sizeof ans);
		memset(vis, 0, sizeof vis);
		rep (i, R) rep (j, C) if (mz[i][j] != '#') {
			vis[i][j] = true;
			lt = 1;
			memset(tpp, 0, sizeof tpp);
			tpp[0] = mz[i][j];
			dfs(i, j);
			vis[i][j] = false;
			debug(ans);
		}
		printf("%s\n", ans);
	}
    
    return 0;
}

Finding Seats Again

UVA - 11846

题意：每个小组有一个矩形座位，给出一个矩阵，其中数字是小组人数，让你给出可能座位方案

题解：搜索对象的选取，第一次我选择了每个数字格，以每个数字格的可能位置矩阵进行搜索但T了，分析了之后发现复杂度是大概是\(O(9^{2*n^2})\)， 转换搜索对象为每个矩阵后，复杂度只有\(O(n^4)\)左右

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-05-01 20:25:27
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ';
    err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 23, inf = 0x3f3f3f3f, mod = 1e9 + 7;

char mz[Ma][Ma];
int n, k;
int bj[Ma][Ma];

void print() {
	rep (i, n) {
		rep (j, n) putchar('A' + bj[i][j] - 1);
		puts("");
	}
}

bool check(int r, int c, int rr, int cc) {
	int cnt = 0;
	fep (i, r, rr + 1) fep (j, c, cc + 1) {
		if (bj[i][j]) return false;
		if (mz[i][j] == '.') continue;
		if (cnt) return false;
		cnt = mz[i][j] - '0';
	}

	return cnt == (rr - r + 1) * (cc - c + 1);
}

void full(int r, int c, int rr, int cc, int val) {
	fep (i, r, rr + 1) fep (j, c, cc + 1) bj[i][j] = val;
}

bool dfs(int id, int pos) {
	if (id == k) return print(), true;
	int r = pos / n, c = pos % n;
	if (bj[r][c]) return dfs(id, pos + 1);
	int mx = n;
	fep (i, r, n) fep (j, c, mx) {
		if ((i - r + 1) * (j - c + 1) > 9) break;
		if (bj[i][j]) {mx = j; break;}
		if (check(r, c, i, j)) {
			full(r, c, i, j, id + 1);
			if (dfs(id + 1, pos + 1)) return true;
			full(r, c, i, j, 0);
		}
	}

	return false;
}	

signed main() {
    #if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	while (scanf("%d%d", &n, &k) == 2 and n + k) {
		rep (i, n) scanf("%s", mz[i]);
		memset(bj, 0, sizeof bj);
		assert(dfs(0, 0));
	}
    
    return 0;
}

Gokigen Naname

UVA - 11694

题意：给出一张网格，交叉点上有数字，让你为每个格子画斜线，使得每个交叉点的数字等于和他相连的斜线条数，且不成环

题解：暴力搜索，直接判断，用并查集判环

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-05-02 16:02:06
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar getchar_unlocked
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ';
    err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

const int Ma = 15, inf = 0x3f3f3f3f, mod = 1e9 + 7;

char mz[Ma][Ma];
int n, fa[Ma * Ma], ans[Ma][Ma], val[Ma][Ma];

int find(int x) {return fa[x] = fa[x] == x ? x : find(fa[x]);}

void init() {rep (i, n + 2) rep (j, n + 2) fa[i * Ma + j] = i * Ma + j; memset(val, 0, sizeof val);}

void print() {
	rep (i, n) {
		rep (j, n) putchar(ans[i][j] ? '/' : '\\');
		putchar('\n');
	}
}

bool check(int cur) {
	int r = cur / n, c = cur % n;
	if (mz[r][c] != '.' and val[r][c] != mz[r][c] - '0') return false;
	if (r == n - 1) if (mz[n][c] != '.' and val[n][c] != mz[n][c] - '0') return false;
	if (c == n - 1) if (mz[r][n] != '.' and val[r][n] != mz[r][n] - '0') return false;
	if (r == n - 1 and c == n - 1) if (mz[n][n] != '.' and val[n][n] != mz[n][n] - '0') return false;
	return true;
}

bool dfs(int cur) {
	if (cur == n * n) return print(), true;
	int r = cur / n, c = cur % n;
	rep (k, 2) {
		pa a = k ? mkp(r, c + 1) : mkp(r, c), b = k ? mkp(r + 1, c) : mkp(r + 1, c + 1);
		int p1 = find(a.F * Ma + a.S), p2 = find(b.F * Ma + b.S);
		if (p1 != p2) {
			int ff[Ma * Ma];
			memcpy(ff, fa, sizeof fa);
			fa[p2] = p1;
			ans[r][c] = k;
			++val[a.F][a.S], ++val[b.F][b.S];
			if (check(cur) and dfs(cur + 1)) return true;
			memcpy(fa, ff, sizeof ff);
			--val[a.F][a.S], --val[b.F][b.S];
		}
	}
	return false;
}

signed main() {
    #if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		init();
		rep (i, n + 1) scanf("%s", mz[i]);
		assert(dfs(0));
	}
    
    return 0;
}

The Wall Pushers

UVA - 10384

题意：给你一个4*6的带墙矩阵，你要从初始格子移动出矩阵， 可以推动一层墙

题解：一开始我很sb的用给出信息反向建立原图，在原图上乱搞，wa了两次后感觉十分不对劲， 最后直接用原信息，使用二进制作为每个格子周围的墙，进行check即可，使用IDA*，当最近的出口的距离+d大于maxd的时候剪枝

注意推墙的时候会影响当前格子，推方向格子，和推方向格子再前一格的格子， 还有推不动边界墙

code 
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
/*************************************************************************
    > File Name: solve.cpp
    > Author: liupo
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-05-02 22:37:30
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define mkt make_tuple
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ';
    err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
cerr<<"DEBUG:";istringstream it(_s);\
err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
#define state(x) (1<<(x))

const int Ma = 12, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int mz[Ma][Ma]; bool vis[Ma][Ma];
bool win (int r, int c) {
	return r == 0 or r == 5 or c == 0 or c == 7;
}
bool check (int r, int c, bool cp=false) {
	if (cp) return r >= 0 and r <= 5 and c >= 0 and c <= 7;
	return r > 0 and r < 5 and c > 0 and c < 7;
}
const int dx[] = {0, -1, 0, 1},
	  	  dy[] = {-1, 0, 1, 0};
const char ai[] = {'W', 'N', 'E', 'S'};

int behind (int r, int c, int dir) {
	if (!(mz[r][c] & state(dir))) return 0;
	if ((dir == 0 and c == 1) or (dir == 1 and r == 1) or (dir == 2 and c == 6) or (dir == 3 and r == 4)) return -2;
	if (mz[r + dx[dir]][c + dy[dir]] & state(dir)) return -1;
	return 1;
}
int h(int r, int c) {
	int ans = inf;
	fep (i, 1, 7) {
		if (mz[1][i] & state(1)) cmin(ans, abs(r - 1) + abs(c - i));
		if (mz[4][i] & state(3)) cmin(ans, abs(4 - r) + abs(c - i));
	}
	fep (i, 1, 5) {
		if (mz[i][1] & state(0)) cmin(ans, abs(r - i) + abs(c - 1));
		if (mz[i][6] & state(2)) cmin(ans, abs(r - i) + abs(6 - c));
	}
	return ans;
}

char res[Ma * Ma];

void print(int cur) {
	res[cur] = 0;
	printf("%s\n", res);
}

void push(int r, int c, int dir) {
	mz[r][c] ^= state(dir);
	r += dx[dir], c += dy[dir];
	mz[r][c] ^= state(dir ^ state(1));
	mz[r][c] ^= state(dir);
	r += dx[dir], c += dy[dir];
	if(check(r, c)) mz[r][c] ^= state(dir ^ state(1));
}

bool dfs (int r, int c, int d, const int& maxd) {
	if (d == maxd) {
		if (win(r, c)) return print(d), true;
		return false;
	}
	//debug(r, c, d, maxd, bitset<4>(mz[r][c]));
	if (d + h(r, c) > maxd) return false;
	rep (i, 4) {
		int rr = r + dx[i], cc = c + dy[i];
		if (check(rr, cc, true) and !vis[rr][cc]) {
			int aim = behind(r, c, i);
			if (aim < 0) continue;
			vis[rr][cc] = true;
			int pre[Ma][Ma];
			memcpy(pre, mz, sizeof mz);
			if (aim == 1) push(r, c, i);
			res[d] = ai[i];
			if (dfs(rr, cc, d + 1, maxd)) return true;
			vis[rr][cc] = false;
			memcpy(mz, pre, sizeof pre);
		}
	}
	return false;
}

signed main () {
    #if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int x, y;
	while (scanf("%d%d", &x, &y) == 2 and x + y) {
		fep (i, 1, 5) fep (j, 1, 7) scanf("%d", &mz[i][j]);
		memset(vis, 0, sizeof vis);
		vis[y][x] = true;
		for (int maxd = 0; !dfs(y, x, 0, maxd); ++maxd);
	}
    
    return 0;
}

向着第九章进发！！GOGOGO🐱‍👤

Comments

⬆︎TOP