语言漩涡

thirtiseven 的博客

0%

POJ 很好很有层次感 题单 部分题解

Posted on Edited on

POJ 1753 Flip Game

“很好很有层次感”题单的第一题。 题意是黑白翻转棋，每次翻转一个，必须同时翻转上下左右的一个棋子，求最小的翻转个数。

枚举翻转次数，dfs，找到就输出。 数组设成6*6的，只处理中心的4*4，不需要判断越界也避免了越界问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstring>

bool table[6][6] = {0};
int ans;
bool find = 0;

void output_table() {
	for(int i = 1; i < 5; i++) {
		std::cout << "\n";
		for(int j = 1; j < 5; j++) {
			std::cout << table[i][j];
		}
	}
}

void turn(int a, int b) {
	table[a][b] = !table[a][b];
	table[a-1][b] = !table[a-1][b];
	table[a][b-1] = !table[a][b-1];
	table[a+1][b] = !table[a+1][b];
	table[a][b+1] = !table[a][b+1];
}

bool is_sort() {
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= 4; j++) {
			if(table[i][j] != table[1][1]) {
				return 0;
			}
		}
	}
	return 1;
}

void dfs(int a, int b, int depth) {
	if(depth == ans){
		find = is_sort();
		return;
	}
	if(a == 5 || find) {
		return;
	}	
	turn(a, b);
	if(b < 4) {
		dfs(a, b+1, depth + 1);
	} else {
		dfs(a+1, 1, depth + 1);
	}
	turn(a, b);
	if(b < 4) {
		dfs(a, b+1, depth);
	} else {
		dfs(a+1, 1, depth);
	}
}

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false); 
	memset(table, 0, sizeof(table));
	char temp[10];
	for(int i = 0; i < 4; i++) {
		std::cin >> temp;
		for(int j = 0; j < 4; j++) {
			if(temp[j] == 'b') {
				table[i+1][j+1] = 0;
			} else if(temp[j] == 'w') {
				table[i+1][j+1] = 1;
			} else {
				continue;
			}
		}
	}
	for(ans = 0; ans <= 16; ans++){
		dfs(1, 1, 0);
		if(find) {
			std::cout << ans << std::endl;
			return 0;
		}
	}
	//output_table();
	std::cout << "Impossible" << std::endl;
	return 0;
}

poj2965 The Pilots Brothers' refrigerator

枚举次数，DFS 和poj1753类似，区别是开关影响不同，本题是那行的横纵列都要改变状态。另一个区别是要记录每次改变的方法。使用结构体或者两个数组存储。 注意再改变状态的时候点（a,b)改变了两次，要再一次改回来。

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
#include <iostream>
#include <cstring>

bool table[6][6] = {0};
int ans;
bool find = 0;

struct solution{
	int row, col;
}N[20];

void output_table() {
	for(int i = 1; i < 5; i++) {
		std::cout << "\n";
		for(int j = 1; j < 5; j++) {
			std::cout << table[i][j];
		}
	}
}

void turn(int a, int b) {
	for(int i = 1; i < 5; i++) {
		table[i][b] = !table[i][b];
	}
	for(int i = 1; i < 5; i++) {
		table[a][i] = !table[a][i];
	}
	table[a][b] = !table[a][b];
}

bool is_open() {
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= 4; j++) {
			if(table[i][j] == 1) {
				return 0;
			}
		}
	}
	return 1;
}

void dfs(int a, int b, int depth) {
	if(depth == ans){
		find = is_open();
		if(find == 1) {
			std::cout << ans << std::endl;
			for(int i = 0; i < ans; i++) {
				std::cout << N[i].row << " " << N[i].col << std::endl;
			}
			return;
		}
		return;
	}
	if(a == 5 || find) {
		return;
	}	
	turn(a, b);
	N[depth].row = a;
	N[depth].col = b;
	if(b < 4) {
		dfs(a, b+1, depth + 1);
	} else {
		dfs(a+1, 1, depth + 1);
	}
	turn(a, b);
	if(b < 4) {
		dfs(a, b+1, depth);
	} else {
		dfs(a+1, 1, depth);
	}
}

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false); 
	memset(table, 0, sizeof(table));
	char temp[10];
	for(int i = 0; i < 4; i++) {
		std::cin >> temp;
		for(int j = 0; j < 4; j++) {
			if(temp[j] == '-') {
				table[i+1][j+1] = 0;
			} else if(temp[j] == '+') {
				table[i+1][j+1] = 1;
			} else {
				continue;
			}
		}
	}
	for(ans = 0; ans <= 16; ans++){
		dfs(1, 1, 0);
	}	
	return 0;
}

POJ 1328 Rader Installation

区间选点问题，贪心解决。 现将区间排序，排序的方法是按区间的右端排序。 每次取区间的右端，如果下一组区间包含取到的区间右端，判断下一组，否则取区间右端。 有一次wa，是因为判断是否为-1的值在循环之后没有置0.

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
#include <iostream>
#include <algorithm>
#include <cmath>

struct extent {  
	double l, r;    
}line[1100];

bool cmp(extent a, extent b) {
	return a.r < b.r;
}

int main(int argc, char *argv[]) {  
	int n, d, cnt_case = 0, ok;
	while(std::cin >> n >> d) {
		ok = 1;
		if(n == 0 && d == 0) {
			break;
		}
		double x, y;
		for(int i = 0; i < n; i++) {
			std::cin >> x >> y;
			double temp = double(d * d) - y * y;
			if(temp < 0 || d < 0) {
				ok = 0;
			} else {
				line[i].l = x - sqrt(temp);
				line[i].r = x + sqrt(temp);
			}			
		}
		if(!ok) {
			cnt_case ++;
			std::cout << "Case " << cnt_case << ": -1"<< std::endl;
		} else {
			std::sort(line, line + n, cmp);
			int ans = 1;
			double temp = line[0].r;
			for(int i = 1; i < n; i++) {
				if(temp < line[i].l) {
					ans++;
					temp = line[i].r;
				}				
			}
			cnt_case ++;
			std::cout << "Case " << cnt_case << ": " << ans << std::endl;
		}		
	}
	return 0;
}

poj 2109 Power of Cryptography

p的范围...相当可怕，本来以为...要上高精度...然后二分...结果... 看代码吧...

double，一个神奇的类型。 （当然啦这题高精度和二分也能过...但是我这么懒...怎么会写呢... （逃

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <cmath>

int main(int argc, char *argv[]) {  
	double n, p;
	while(std::cin >> n >> p) {
		std::cout <<  pow(p, 1/n) << std::endl;
	}
	return 0;
}

poj 2586 Y2K Accounting Bug

某个微什么公司，每个月的亏损或者盈利是固定的，每五个月统计一次，所以一年统计了八次，这八次统计...全是亏的...然后要求最高的盈利。

网上说贪心... 其实这才几个月啊...可以自己贪心一下，把那个分段的东西搞出来 换言之，模拟（逃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

int main(int argc, char *argv[]) {  
	int s, d, ans;
	while(std::cin >> s >> d) {
		if(4 * s < d) {
			ans = 10 * s - 2 * d;
		} else if(3 * s < 2 * d) {
			ans = 8 * s - 4 * d;
		} else if(2 * s < 3 * d) {
			ans = 6 * s - 6 * d;
		} else if(s < 4 * d) {
			ans = 3 * s - 9 * d;
		} else {
			ans = -1;
		}
		if(ans > 0) {
			std::cout << ans << std::endl;
		} else {
			std::cout << "Deficit" << std::endl;
		}
	}
	return 0;
}

poj 3295 Tautology

哇呜我好牛逼...竟然一次过... 就是一个逻辑版的波兰计算器 压进来弹出去什么的搞一波...具体不说了... 今年第一次用goto！ （我还记得小时候学编程所有循环都是goto...后来我脑子就坏掉了 什么都用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <stack>

std::stack<int> expr;
int p, q, r, s, t;
char expr_input[105]; 

bool solve() {
	int top = 0;
	int len = strlen(expr_input);
	for(int i = len - 1;i >= 0;i--) {
		switch (expr_input[i]) {
			case 'p': expr.push(p); break; 
			case 'q': expr.push(q); break; 
			case 'r': expr.push(r); break; 
			case 's': expr.push(s); break; 
			case 't': expr.push(t); break; 
			case 'K': 
				{
					int a = expr.top();  
					expr.pop();  
					int b = expr.top();  
					expr.pop();  
					expr.push(a&&b); 
					break; 
				}
			case 'A':
				{
					int a = expr.top();  
					expr.pop();  
					int b = expr.top();  
					expr.pop();  
					expr.push(a||b); 
					break; 
				}
			case 'N':
				{
					int a = expr.top();  
					expr.pop();    
					expr.push(!a); 
					break; 
				}
			case 'C':
				{
					int a = expr.top();  
					expr.pop();  
					int b = expr.top();  
					expr.pop();  
					expr.push((!a)||b); 
					break; 
				}
			case 'E':
				{
					int a = expr.top();  
					expr.pop();  
					int b = expr.top();  
					expr.pop();  
					expr.push(a==b); 
					break; 
				}
		}
	}
	return expr.top();
}

int main(int argc, char *argv[]) { 
	while(std::cin >> expr_input && expr_input[0] != '0') {
		int ok = 1;
		for(p=0; p<=1; p++) for(q=0; q<=1; q++) for(r=0; r<=1; r++) for(s=0; s<=1; s++) for(t=0; t<=1; t++) {
			if(!solve()) {
				ok = 0;
				goto out_of_siege;
			}
		}
		out_of_siege:
		if(ok) {
			std::cout << "tautology" << std::endl;
		} else {
			std::cout << "not" << std::endl;

		}
	}
	return 0;
}

poj 1860 Currency Exchange

dis数组写成int了 神他妈WA一下午...

bellman_ford求正环，人生第一条图论题...

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
#include <iostream>

#define maxn 410
#define inf 0x3f3f3f3f

struct edge{
	int u, v;
	double rate, com;
}side[maxn];

double dis[maxn];

int edge_num, node_num, source;
double value;

void init() {
	for(int i = 1; i <= edge_num; i++) { 
		dis[i] = 0;
	}  
	dis[source] = value;
}

int bellman_ford() {
	init();
	for(int i = 0; i < edge_num; i++) {  
		for(int j = 1; j <= 2 * node_num; j++) {  
			if(dis[side[j].v] < (dis[side[j].u] - side[j].com) * side[j].rate){  
				dis[side[j].v] = (dis[side[j].u] - side[j].com) * side[j].rate;  
			}  
		}  
	}  
	for(int j = 1; j <= 2 * node_num; j++) {  
		if(dis[side[j].v] < (dis[side[j].u] - side[j].com) * side[j].rate){  
			return 1;  
		}  
	}  
	return 0;  
} 

int main(int argc, char *argv[]) {  
	//std::ios::sync_with_stdio(false);
	std::cin >> edge_num >> node_num >> source >> value;
	for(int i = 1; i <= 2 * node_num; i += 2) {
		//std::cout << "BIU!\n";
		std::cin >> side[i].u >> side[i].v >> side[i].rate >> side[i].com >> side[i+1].rate >> side[i+1].com;
		side[i+1].u = side[i].v;
		side[i+1].v = side[i].u;
	}
	if(bellman_ford()) {
		std::cout << "YES\n";  
	} else { 
		std::cout << "NO\n"; 
	}
	return 0;
}

POJ1062 昂贵的赠礼 dijkstra

http://poj.org/problem?id=1062 肝爆，现在早上三点了。 最短路，有个条件是等级差...枚举等级区间... 第一条dijkstra...用了大佬的模板... 不说了不说了 睡觉

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
#include <iostream>
#include <cstring>
#include <vector> 
#include <queue> 
#include <algorithm>
#include <cmath>

#define inf 1000000000 
#define maxn 110 

int m, n;
bool vis[maxn];

class dijkstra {
private:
	struct heapnode {
		int u;
		int d;
		heapnode(int u, int d) :u(u), d(d) {}
		bool operator < (const heapnode &b) const {
			return d > b.d;
		}
	};
	
	struct edge {
		int v, w;
		edge(int v, int w) :v(v), w(w) { }
	};
	
	std::vector<edge> g[maxn];
	
public:
	int d[maxn];
	int val[maxn];
	std::priority_queue<heapnode> q;
	void clear(int size) {
		for(int i = 0; i <= size; i++) {
			g[i].clear();
		}
		for(int i = 1; i <= size; i++) {
			d[i] = inf;
		}
		memset(vis, 0, sizeof(vis));
	}
	
	void addedge(int u, int v, int w) {
		g[u].push_back(edge(v, w));
	}
	
	int run(int s) {
		int u;
		int min_cost = inf;	
		for(int i = 1; i <= n; i++) {  
			d[i] = inf;
		}	
		d[s] = 0;
		q.push(heapnode(s, 0));
		while (!q.empty()) {
			u = q.top().u;
			q.pop();
			if(!vis[u]) {
				vis[u] = 1;
				for (std::vector<edge>::iterator e = g[u].begin(); e != g[u].end(); e++) {
					if (d[e->v] > d[u] + e->w && !vis[e->v]) {
						d[e->v] = d[u] + e->w;
						q.push(heapnode(e->v, d[e->v]));
					}
				}
			}
		}
		for(int i = 1; i <= n; i++) {
			d[i] += val[i];
			min_cost = std::min(min_cost,d[i]);
		}
		return min_cost;
	}
};

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	dijkstra bob;
	int level[maxn];
	int ans = inf;
	std::cin >> m >> n;
	bob.clear(n);
	for(int id = 1; id <= n; id++) {
		int substitute;
		std::cin >> bob.val[id] >> level[id] >> substitute;
		for(int i = 0; i < substitute; i++) {
			int to, value;
			std::cin >> to >> value;
			bob.addedge(id, to, value);
		}
	}
	for(int i = 0; i <= m; i++) {
		for(int j = 1; j <= n; j++) {
			if(level[j] < level[1] - m + i || level[j] > level[1] + i) {
				vis[j] = 1;
			} else {
				vis[j] = 0;
			}
		}
		int dij = bob.run(1);
		ans = std::min(ans, dij);
	}
	std::cout << ans << std::endl;
	return 0; 
}