算法竞赛入门经典第七章例题(15/15)

终于搞完第七章了，能学算法了！

最近想培养下dp，快点冲到第九章，gogogo

暴力，码量和模拟相差无几🤕

Division

UVA725

题意: 输入一个n，让你得到\(abcde/fghij=n\) 的合法表达式

题解：直接枚举fghij即可，复杂度 \(O(\prod_{r=5}^{10}r)\)

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
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

const int Ma = 1e5;

int n;

bool check(int a, int b){
	gp_hash_table<int, null_type>se;
	if(a < Ma / 10 || b < Ma / 10)se.insert(0);
	while(a)se.insert(a % 10), a /= 10;
	while(b)se.insert(b % 10), b /= 10;
	return se.size() == 10;
}

void print(int c, int b){
	printf("%05d / %05d = %d\n", c, b, n);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	bool out = false, to = false;
	while(cin >> n && n){
		if(to)putchar('\n');
		else to = true;
		bool out = false;
		for(int i = 1; i < Ma; i++)
			if(n * i < Ma){
				if(check(n * i, i))
					out = true, print(n * i, i);
			}else break;
		if(!out)printf("There are no solutions for %d.\n", n);
	}

	return 0;
}

Maximum Product

UVA-11059

题意：给你n个元素，让你找出一个乘积最大的连续子序列，非正数则输出0

题解： n<=18, 直接枚举左右界即可, \(n^2\)暴力

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
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

const int Ma = 20;
int num[Ma];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, te = 0;
	while(cin >> n){
		long long ans = 0;
		for(int i = 0; i < n; i++)
			cin >> num[i];
		for(int i = 0; i < n; i++){
			for(int j = i; j < n; j++){
				long long temp = 1;
				for(int k = i; k <= j; k++)
					temp *= num[k];
				ans = max(temp, ans);
			}
		}
		cout << "Case #" << ++te << ": The maximum product is "<< ans <<".\n\n";
	}

	return 0;
}

Fractions Again?!

UVA-10976

题意：给你一个k，让你找到所有正整数x>=y， 使\(\frac{1}{k}=\frac{1}{x}+\frac{1}{y}\)

题解：枚举y在[1, 2k], 检查x， 由条件推得\(\frac{1}{k}=\frac{1}{y}+\frac{1}{y}\)， 可的y<=2k

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
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second

typedef pair<int, int> pa;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int k;
	while(cin >> k){
		vector<pa> v;
		for(int y = k + 1; y <= k * 2; y++){
			if(k * y % (y - k) == 0 && k * y / (y - k) >= y)
				v.emplace_back(pa(k * y / (y - k), y));
		}
		cout << v.size() << '\n';
		for(const auto& i : v)
			cout << "1/" << k << " = " << "1/" << i.F << " + 1/" << i.S << '\n';
	}

	return 0;
}

Prime Ring Problem

UVA - 524

题意：给出n，然你从1开始排列，使得形成相邻元素和为素数的环

题解：回溯check即可

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
#include<bits/stdc++.h>
using namespace std;

const int Ma = 20;
bool isp[Ma];

bool isprim(int x){
	for(int i = 2; i * i <= x; i++)
		if(x % i == 0)return false;
	return true;
}

void init(){
	for(int i = 2; i < Ma * 2; i++)
		isp[i] = isprim(i);
}

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

void dfs(int cur){
	if(cur == n && isp[A[0] + A[cur - 1]]){
		for(int i = 0; i < n; i++){
			cout << A[i];
			if(i != n - 1)cout << ' ';
		}
		cout << '\n';
	}else if(cur < n){
		for(int i = 2; i <= n; i++)if(!vis[i] && isp[A[cur - 1] + i]){
			A[cur] = i;
			vis[i] = true;
			dfs(cur + 1);
			vis[i] = false;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	init();
	int k = 0;
	while(cin >> n){
		if(k)cout << '\n';
		cout << "Case " << ++k << ":\n";
		memset(A, 0, sizeof(A));
		memset(vis, 0, sizeof(vis));
		A[0] = 1;
		dfs(1);
	}

	return 0;
}

Krypton Factor

UVA - 129

题意：保证字符串没有相邻重复的串, 用前L个字符构造长度为n的串

题解：回溯，check后缀即可，改变的只有最后一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;

const int Ma = 1e3;
int n, L, cnt;
int ans[Ma];

bool dfs(int cur){
	if(cnt++ == n){
		for(int i = 0; i < cur; i++){
			if(i % 64 == 0 && i)cout << '\n';
			else if(i % 4 == 0 && i)cout << ' ';
			cout << char('A' + ans[i]);
		}
		cout << '\n' << cur << '\n';
		return true;
	}else{
		for(int i = 0; i < L; i++){
			ans[cur] = i;
			bool can = true;
			for(int j = 1; can && j * 2 <= cur + 1; j++){
				bool equal = true;
				for(int k = 0; equal && k < j; k++)
					if(ans[cur - k] != ans[cur - j - k])equal = false;
				if(equal)can = false;
			}
			if(can && dfs(cur + 1))return true;
		}
	}
	return false;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while(cin >> n >> L && (n + L))
		cnt = 0, dfs(0);

	return 0;
}

Bandwidth

UVA - 140

题意：给出一个图，让你给出一个节点排列，使得带宽最小，定义带宽为图上相邻两点在排列上的最大距离

题解：最优性剪枝，注意输入与输出

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
#include<bits/stdc++.h>
using namespace std;

const int Ma = 1e5, inf = 0x3f3f3f3f;

vector<int> node[Ma];
string ans;
int best, all;
set<char>ju;
bool vis[Ma];
char xl[Ma], tp[Ma];
int pos[30];

void dfs(int cur, int bs){
	if(cur == all){
		if(bs >= best)return ;
		best = bs;
		ans.clear();
		for(int i = 0; i < all; i++)
			ans += xl[i], ans += ' ';
		ans += "-> ", ans += char('0' + best);
		return ;
	}else {
		for(const auto& i : ju) if(!vis[i - 'A']){
			xl[cur] = i;
			pos[i - 'A'] = cur;
			vis[i - 'A'] = true;
			int temp = bs, tt = 0;
			for(const auto& j : node[i - 'A'])if(vis[j])
				temp = max(temp, cur - pos[j]);
			else tt++;
			if(temp < best && tt < best)dfs(cur + 1, temp);
			vis[i - 'A'] = false;
		}
	}
}

int main(){
	while(~scanf("%s", tp) && tp[0] != '#'){
		best = inf;
		memset(vis, 0, sizeof(vis));
		for(int i = 0; i < 30; i++)
			node[i].clear(), pos[i] = 0;
		int now = 0;
		char me, my[Ma];
		ju.clear();
		while(*(tp + now)){
			sscanf(tp + now, "%c", &me);
			ju.emplace(me);
			++now;
			if(*(tp + now) == ':')++now;
			sscanf(tp + now, "%[^;]", my);
			now += strlen(my);
			if(tp[now] == ';')now++;
			int len = strlen(my);
			for(int i = 0; i < len; i++)
				node[me - 'A'].emplace_back(my[i] - 'A'),
				node[my[i] - 'A'].emplace_back(me - 'A'),
				ju.emplace(my[i]);
		}
		all = ju.size();
		dfs(0, 0);
		printf("%s\n", ans.data());
	}

	return 0;
}

Mobile Computing

UVA - 1354

题意：给出房间宽度和s个挂坠的相应重量， 让你给出尽量宽的天平宽度，使得天平平衡t

题解：搜索对象的选取，搜索节点左右子树，取结果的最大值

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
#include<bits/stdc++.h>
using namespace std;

const double eps = 1e-18;
const int Ma = 10;

double r, ans;
int s, w[Ma];
int sum[1 << Ma];
bool vis[1 << Ma];
struct Tree{
	double L, R;
	Tree(double l = 0, double r = 0) :
	L(l), R(r){}
};

vector<Tree> tree[1 << Ma];

void dfs(int bitset){
	if(vis[bitset])return ;
	vis[bitset] = true;
	bool child = false;
	for(int t = (bitset - 1) & bitset; t; t = (t - 1) & bitset){
		child = true;
		int ri = bitset ^ t;

		dfs(t), dfs(ri);
		double lb = 1.0 * sum[ri] / sum[bitset],
			   rb = 1.0 * sum[t] / sum[bitset];
		for(const auto& i : tree[t]){
			for(const auto& j : tree[ri]){
				Tree me;
				me.L = max(i.L + lb, j.L - rb);
				me.R = max(i.R - lb, j.R + rb);
				if(me.L + me.R < r)tree[bitset].emplace_back(me);
			}
		}
	}
	if(!child)tree[bitset].emplace_back(Tree());
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%lf%d", &r, &s);
		ans = -1.0;
		for(int i = 0; i < s; i++)
			scanf("%d", w + i);
		memset(sum, 0, sizeof(sum));
		memset(vis, 0, sizeof(vis));
		for(int i = 1; i < (1 << s); i++){
			tree[i].clear();
			for(int j = 0; j < s; j++)
				if((1 << j) & i)sum[i] += w[j];
		}

		dfs((1 << s) - 1);
		for(const auto& i : tree[(1 << s) - 1])if(i.L + i.R - r < 0)
			ans = max(ans, i.L + i.R);

		printf("%.16f\n", ans);
	}

	return 0;
}

Fill

UVA - 10603

题意：给你三个容量为a, b, c的杯子，只有第三个杯子是满的，问你能否使得一杯水恰好d L

题解：和八数码一样，重点在隐式图节点的建立。将a和b水杯的容量作为节点值，因为总水量不变。在隐式图上搜索即可

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
/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-03-29 17:43:46
 ************************************************************************/

#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 = 210, inf = 0x3f3f3f3f, mod = 1e9 + 7;

typedef int bot[3];

struct Node {
	bot v;
    int	dist;
	bool operator < (const Node b) const {
		return dist > b.dist;
	}
	int& operator [] (const int& t) {
		return v[t];
	}
};
bool vis[Ma][Ma];
int ans[Ma];

void update(const Node& t) {
	rep(i, 3) {
		int d = t.v[i];
		if (!~ans[d] or ans[d] > t.dist) ans[d] = t.dist;
	}
}

void solve(bot& base, int& d) {
	memset(ans, -1, sizeof ans);
	memset(vis, 0, sizeof vis);
	__gnu_pbds::priority_queue<Node> q;
	q.push({{0, 0, base[2]}, 0});
	vis[0][0] = true;
	while (!q.empty()) {
		auto u = q.top(); q.pop();
		update(u);
		if (~ans[d]) break;
		for (int i = 0; i < 3; i ++)
			for (int j = 0; j < 3; j ++) if (i != j) {
				if (u[i] == 0 or u[j] == base[j]) continue;
				int del = min(base[j], u[i] + u[j]) - u[j];
				Node t; memcpy(&t, &u, sizeof u);
				t[i] -= del; t[j] += del; t.dist += del;
				if (!vis[t[0]][t[1]]) {
					vis[t[0]][t[1]] = true;
					q.push(t);
				}
			}
	}
	while (d >= 0) {
		if (~ans[d]) {
			printf("%d %d\n", ans[d], d);
			return ;
		}
		--d;
	}
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T;
	scanf("%d", &T);
	while (T--) {
		bot base; int d;
		rep(i, 3) scanf("%d", &base[i]);
		scanf("%d", &d);
		solve(base, d);
	}
    
    return 0;
}

The Morning after Halloween

UVA - 1601

题意：有最多三个小写字母要回到对应大写字母的地方问你最少的步数

题解：将小写字母位置作为隐式图节点，因为“Any 2 × 2 area on any map has at least one sharp”， 所以大部分空地都与格子相邻，提前建好图，跑隐式图

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

#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 = 150, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int c, r, n;
int s[3], t[3];
vector<int> g[Ma];
const int dx[] = {1, -1, 0, 0, 0},
	  	  dy[] = {0, 0, 1, -1, 0};

int ID(int a, int b, int c) {
	return (a << 16) | (b << 8) | c;
}

int d[Ma][Ma][Ma];

bool conflict (int a, int b, int a1, int b1) {
	return a1 == b1 or (a1 == b and a == b1);
}

int bfs() {
	rep(i, 3) debug(s[i], t[i]);
	queue<int> q;
	q.emplace(ID(s[0], s[1], s[2]));
	memset(d, -1, sizeof d);
	d[s[0]][s[1]][s[2]] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;
		if (a == t[0] and b == t[1] and c == t[2]) return d[a][b][c];
		rap(i, g[a]) rap(j, g[b]){
			if (conflict(a, b, i, j)) continue;
			rap (k, g[c]) {
				if (conflict(a, c, i, k)) continue;
				if (conflict(b, c, j, k)) continue;
				if (~d[i][j][k]) continue;
				d[i][j][k] = d[a][b][c] + 1;
				q.emplace(ID(i, j, k));
			}
		}
	}

	return -1;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	while (scanf("%d%d%d\n", &c, &r, &n) == 3 and n) {
		char mz[20][20];
		rep(i, r) fgets(mz[i], 20, stdin);
		int cnt = 0, x[Ma], y[Ma], id[20][20];
		rep(i, r) rep(j, c) if (mz[i][j] != '#') {
			x[cnt] = i, y[cnt] = j, id[i][j] = cnt;
			if (islower(mz[i][j])) s[mz[i][j] - 'a'] = cnt;
			else if (isupper(mz[i][j])) t[mz[i][j] - 'A'] = cnt;
			++cnt;
		}
		rep(i, cnt) {
			g[i].clear();
			rep(j, 5) {
				int nx = x[i] + dx[j], ny = y[i] + dy[j];
				if (mz[nx][ny] != '#') g[i].ep(id[nx][ny]);
			}
		}
		if (n <= 2) g[cnt].clear(), g[cnt].ep(cnt), s[2] = t[2] = cnt++;
		if (n <= 1) g[cnt].clear(), g[cnt].ep(cnt), s[1] = t[1] = cnt++;
		printf("%d\n", bfs());
	}
    
    return 0;
}

Editing a Book

UVA - 11212

题意：通过cv操作使给出的序列变为升序， 可以操作连续一段区间， 问你需要最小操作数

题解：枚举剪切，使用IDA*进行优化，n=9时深度为8, 由于每次剪切最多影响三个数字的后缀，因此当 \(d + h() / 3 > 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
/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-03-31 13:26:05
 ************************************************************************/

#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 = 12, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int num[Ma], n;

int h() {
	int cnt = 0;
	for (int i = 0; i < n - 1; i++)
		if (num[i] + 1 != num[i + 1]) ++cnt;
	if (num[n - 1] != n) ++cnt;
	return cnt;
}

bool is_sorted() {
	for (int i = 0; i < n - 1; i++)
		if (num[i] >= num[i + 1]) return false;
	return true;
}

bool dfs(int d, int maxd) {
	if (d * 3 + h() > maxd * 3) return false;
	if (is_sorted()) return true;

	int b[Ma], a[Ma];
	memcpy(a, num, sizeof num);
	rep (i, n) fep (j, i, n - 1) {
		int cnt = 0;
		rep (k, n) if (k < i or j < k)
			b[cnt++] = num[k];
		fep(k, 0, cnt) {
			int cnt2 = 0;
			for (int p = 0; p < k; p++) num[cnt2++] = b[p];
			for (int p = i; p <= j; p++) num[cnt2++] = a[p];
			for (int p = k; p < cnt; p++) num[cnt2++] = b[p];
			if (dfs(d + 1, maxd)) return true;
			memcpy(num, a, sizeof a);
		}
	}
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int k = 0;
	while (~scanf("%d", &n) and n) {
		rep (i, n) scanf("%d", num + i);
		int maxd;
		for (maxd = 0; ; ++maxd)
			if (dfs(0, maxd)) break;
		printf("Case %d: %d\n", ++k, maxd);
	}
    
    return 0;
}

Zombie's Treasure Chest

UVA - 12325

题意: 给你两种无限数量的宝物和一个体积为N的宝箱，让你计算最多能装多大价值的宝物

题解：当N/S1比较小时，可以枚举宝物1即可，当N/S2比较小时，可以枚举宝物2即可 当两者都较大时，考虑S2 * V1与S1 * V2的大小，当前者较大时，S2最多拿S1 - 1个，反之S1最多只能拿S2 - 1个

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
/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-03-31 17:02:32
 ************************************************************************/

#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 = 1e5, inf = 0x3f3f3f3f, mod = 1e9 + 7;

ll gao(int n, int s1, int v1, int s2, int v2) {
	ll ans = 0;
	rep (i, n / s1 + 1)
		cmax(ans, 1ll * i * v1 + 1ll * (n - i * s1) / s2 * v2);
	return ans;
}

ll solve(int n, int s1, int v1, int s2, int v2) {
	ll ans = 0;
	if (1ll * v1 * s2 > 1ll * v2 * s1) swap(s1, s2), swap(v1, v2);
	rep (i, s2)
		cmax(ans, 1ll * i * v1 + 1ll * (n - i * s1) / s2 * v2);
	return ans;
}

signed main() {
	#if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int T, k = 0;
	cin >> T;
	while (T--) {
		cout << "Case #" << ++k << ": ";
		int n, s1, v1, s2, v2;
		cin >> n >> s1 >> v1 >> s2 >> v2;
		if (n / s1 < Ma) cout << gao(n, s1, v1, s2, v2) << endl;
		else if (n / s2 < Ma) cout << gao(n, s2, v2, s1, v1) << endl;
		else cout << solve(n, s1, v1, s2, v2) << endl;
	}
    
    return 0;
}

The Rotation Game

UVA - 1343

题意：通过旋转A~H，使中间八个数字相同

题解：搜索三次，中间全为1， 全为2和全为3， 总状态只有24!/(8!*16!)

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
/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-03-31 17:52:42
 ************************************************************************/

#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 a[Ma];

bool read() {
	rep(i, 24) if(scanf("%d", a + i) != 1 or !a[i]) return false;
	return true;
}

const int center[] = {6, 7, 8, 11, 12, 15, 16, 17};
const int rev[] = {5, 4, 7, 6, 1, 0, 3, 2};
int line[8][7] = {
  { 0, 2, 6,11,15,20,22},
  { 1, 3, 8,12,17,21,23},
  {10, 9, 8, 7, 6, 5, 4},
  {19,18,17,16,15,14,13},
};

bool is_final() {
	rep (i, 8)
		if (a[center[i]] != a[center[0]]) return false;
	return true;
}

char ans[1000];
int diff(int target) {
	int ans = 0;
	rep(i, 8)
		if (a[center[i]] != target) ++ans;
	return ans;
}

inline int h() {
	return min(min(diff(1), diff(2)), diff(3));
}

void move(int x) {
	int temp = a[line[x][0]];
	rep(i, 6) a[line[x][i]] = a[line[x][i + 1]];
	a[line[x][6]] = temp;
}

bool dfs(int d, int maxd) {
	if (is_final()) {
		ans[d] = 0;
		printf("%s\n", ans);
		return true;
	}
	if (d + h() > maxd) return false;
	rep (i, 8) {
		ans[d] = 'A' + i;
		move(i);
		if (dfs(d + 1, maxd)) return true;
		move(rev[i]);
	}
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	fep (i, 4, 8)
		rep(j, 7) line[i][j] = line[rev[i]][6 - j];
	while (read()) {
		if (is_final()) puts("No moves needed");
		else {
			for (int maxd = 1; ; ++maxd)
				if (dfs(0, maxd)) break;
		}
		printf("%d\n", a[6]);
	}
     
    return 0;
}

Power Calculus

UVA - 1374

题意：输入一个n，问你需要几次乘除才能从x得到\(x^n\)

题解：容易想到迭代加深，但会T，升为IDA*，考虑当前最大的指数乘以\(2^(maxd-d)\)仍然小于n，则剪枝

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
/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-03-31 20:25:16
 ************************************************************************/

#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 = 20, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int n, a[Ma];

bool dfs(int d, int maxd) {
	if (a[d] == n) return true;
	if (d == maxd) return false;
	int maxv = *max_element(a, a + d + 1);
	if ((maxv << (maxd - d)) < n) return false;
	for (int i = d; i >= 0; i--) {
		a[d + 1] = a[d] + a[i];
		if (dfs(d + 1, maxd)) return true;
		a[d + 1] = a[d] - a[i];
		if (dfs(d + 1, maxd)) return true;
	}
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	while (scanf("%d", &n) == 1 and n) {
		int maxd; a[0] = 1;
		for (maxd = 0; ; maxd++)
			if (dfs(0, maxd)) break;
		printf("%d\n", maxd);
	}
    
    return 0;
}

Lattice Animals

UVA - 1602

题意：让你求w * h的网格里的n连块有多少个

题解：打表，构造所有连通块，连通块都进行格式化，用set判重

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

#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 = 12, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int ans[Ma][Ma][Ma];

struct Cell {
	int x, y;
	Cell(int x=0, int y=0) : x(x), y(y) {};
	bool operator < (const Cell& b) const {
		return x < b.x or (x == b.x and y < b.y);
	}
};

typedef set<Cell> Polyomino;
set<Polyomino> poly[Ma];

inline Polyomino normalize(const Polyomino& p) {
	int minx = p.begin()->x, miny = p.begin()->y;
	rap (i, p) cmin(minx, i.x), cmin(miny, i.y);
	Polyomino p2;
	rap (i, p)
		p2.insert(Cell(i.x - minx, i.y - miny));
	return p2;
}

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

Polyomino roate(const Polyomino& p) {
	Polyomino pt;
	for (const auto& i : p)
		pt.insert(Cell(i.y, -i.x));
	return normalize(pt);
}

Polyomino filp(const Polyomino& p) {
	Polyomino pt;
	for (const auto& i : p)
		pt.insert(Cell(i.x, -i.y));
	return normalize(pt);
}

void check(const Polyomino& pt, const Cell& c) {
	Polyomino p = pt;
	p.insert(c);
	p = normalize(p);
	
	int n = p.size();
	rep (i, 4) {
		if (poly[n].count(p) != 0) return ;
		p = roate(p);
	}
	p = filp(p);
	rep (i, 4) {
		if (poly[n].count(p) != 0) return ;
		p = roate(p);
	}

	poly[n].insert(p);
}

void gao() {
	Polyomino s;
	s.insert(Cell());
	poly[1].insert(s);
	
	fep (n, 2, 11) {
		rap (p, poly[n - 1]) {
			rap (c, p) {
				rep (i, 4) {
					Cell newc(c.x + dx[i], c.y + dy[i]);
					if (!p.count(newc)) check(p, newc);
				}
			}
		}
	}

	fep (n, 1, 11)
		fep (w, 1, 11)
			fep (h, 1, 11) {
				int cnt = 0;
				rap (p, poly[n]) {
					int maxx = 0, maxy = 0;
					rap (c, p) {
						cmax(maxx, c.x);
						cmax(maxy, c.y);
					}
					if (min(maxx, maxy) < min(h, w) and max(maxx, maxy) < max(h, w))
						++cnt;
				}
				ans[n][w][h] = cnt;
			}
}

signed main() {
	#if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	gao();
	int n, w, h;
	while (cin >> n >> w >> h)
		cout << ans[n][w][h] << endl;
    
    return 0;
}

Square Destroyer

UVA - 1603

题意：让你把一个n边的2n(n+1)的正方形火柴矩阵破坏

题解：建立各个正方形，使用用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
/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-04-03 15:09:49
 ************************************************************************/

#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 = 100, inf = 0x3f3f3f3f, mod = 1e9 + 7;

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

int ans, n, sn, go;
ll square[Ma];

ll get(int r, int c, int l) {
	int h1 = r * go + c, h2 = h1 + l * go,
		s1 = h1 + n, s2 = s1 + l;
	ll temp = 0;
	//puts("------------------");
	rep (i, l) {
		//debug(h1, h2, s1, s2);
		temp |= state(s1) | state(s2) | state(h1) | state(h2);
		++h1, ++h2, s1 += go, s2 += go;	
	}
	return temp;
}

void get_square() {
	sn = 0, go = n * 2 + 1;
	fep (l, 1, n + 1)
		for (int i = 0; i + l <= n; i++)
			for (int j = 0; j + l <= n; j++)
				square[sn++] = get(i, j, l);
}

bool dfs(int d, int maxd, ll s) {
	if (d == maxd) {
		rep (i, sn) if ((square[i] & s) == square[i]) return false;
		return true;
	}
	ll del = s, fi = -1; int nu = 0;
	rep (i, sn) if ((square[i] & del) == square[i]) {
		++nu; del ^= square[i];
		if (!~fi) fi = square[i];
	}
	if (d + nu > maxd) return false;
	rep (i, 2 * n * (n + 1)) if (fi & state(i))
		if (dfs(d + 1, maxd, s ^ state(i))) return true;
	return false;
}

signed main() {
	#if SYNC==1
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
	int _;
	for (scanf("%d", &_); _--; printf("%d\n", ans)) {
		scanf("%d", &n);
		get_square();
		//rep (i, sn) {
		//	cout << bitset<sizeof(ll) * 8>(square[i]) << endl;
		//}
		ll base = state(2 * n * (n + 1)) - 1;
		int t; scanf("%d", &t);
		rep (i, t) {
			int k; scanf("%d", &k);
			base ^= state(k - 1);
		}
		for (ans = 0; !dfs(0, ans, base); ++ans);
	}
    
    return 0;
}

写完习题题解就能快乐的学习第八章了！

gogogo

Comments

⬆︎TOP