算法竞赛入门经典第六章例题(22/22)

终于做完第六章了！！ 马上做完习题就能学怎么暴力了！！！ 快乐！

数据结构这里没有涉及线段树， 树状数组之类的结构， 但学完这一章也能闲时看看， 学一学就行。 基础差不多稳固， 只差习题加深稳固下了👽。

Concurrency Simulator

UVA - 210

题意: 让你模拟线程并行, 只包含赋值语句，输出语句，lock, unlock， 和end, 变量初始值为零，给你五种语句的运行需要时间和每个程序的配额，和n个程序

题解: 直接模拟，只有一个cpu， 先读入程序，用队列模拟就绪队列，双端队列模拟堵塞队列， 注意样列有误，得有个样列数，，，uva题面又没有，，被wa到怀疑人生，，，看了udebug才发现，，

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
/*********************************************************
Flie Name: 210.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月02日 星期五 09时53分31秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

int n, pm;
int Cost[10];
map<char, int>var;

struct Ask{
	char aim;
	int val;
	int mod;
	int id;
	Ask(char a, int v, int m, int i) : aim(a), val(v), mod(m), id(i + 1) {}
	int run(){
		if(mod == 0)
			var[aim] = val;
		else if(mod == 1)
			printf("%d: %d\n", id, var[aim]);
		return mod;
	}
};

queue<Ask>Program[100000];

void readPro(int id){
	char s[1000000];
	while(fgets(s, sizeof(s), stdin), !(strchr(s, '=') == nullptr && s[0] == 'e')){
		char aim;
		int val;
		int mod;
		if(strchr(s, '=') != nullptr)
			mod = 0, sscanf(s, "%c = %d", &aim, &val);
		else if(s[0] == 'p')mod = 1, sscanf(s + 6, "%c", &aim);
		else if(s[0] == 'l')mod = 2;
		else mod = 3;
		Program[id].push(Ask(aim, val, mod, id));
	}
}

void run(){
	deque<int>ready;
	queue<int>block;
	for(int i = 0; i < n; i++)
		if(!Program[i].empty())ready.emplace_back(i);
	bool bk = false;
	while(!ready.empty()){
		int now = ready.front();
		int rt = pm;
		ready.pop_front();
		bool can = true;
		while(can && rt > 0){
			int mod = Program[now].front().run();
			if(mod == 2){
				if(bk){
					can = false, block.push(now);
					break;
				}
				else bk = true;
			}
			if(mod == 3){
				bk = false;
				if(!block.empty()){
					ready.emplace_front(block.front());
					block.pop();
				}
			}
			rt -= Cost[mod];
			Program[now].pop();
			if(Program[now].empty())can = false;
		}
		if(can)ready.emplace_back(now);
	}
}

int main(){
	bool blank = false;
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		if(blank)putchar('\n');
		else blank = true;
		var.clear();
		for(int i = 0, t; i < 5; i++){
			scanf("%d", &t);
			Cost[i] = t;
		}
		scanf("%d\n", &pm);
		for(int i = 0; i < n; i++)
			readPro(i);
		run();
	}
    
    return 0;
}

Rails

UVA - 514

题意：让你模拟火车进站出站，按1～n的顺序进站，问你能否以给定顺序出站

题解：利用栈进行模拟，看能否达成给定顺序，刘大爷的代码没能处理uva上的数据(估计是看着太简单了随手写的，没想到uva输入这么沙雕2333)， 最后的坑点自然是uva的日常 ---- 结尾也得用空行

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
/*********************************************************
Flie Name: 514.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月02日 星期五 14时42分45秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int Ma = 1010;
int car[Ma];

bool read(int n){
	rep(i, n){
		scanf("%d", car + i);
		if(car[0] == 0)return false;
	}
	return true;
}

int main(){
	int n;
	bool blank = false;
	while(~scanf("%d", &n) && n){
		assert(n <= 1000);
		while(read(n)){
			stack<int>s;
			int A = 1, B = 0;
			bool can = true;
			while(can && B < n){
				if(A == car[B])A++, B++;
				else if(!s.empty() && s.top() == car[B])B++, s.pop();
				else if(A <= n)s.push(A++);
				else can = false;
			}
			puts(can ? "Yes" : "No");
		}
                putchar('\n');
	}
    
    return 0;
}

Matrix Chain Multiplication

UVA - 442

题意：给你一堆矩阵， 问你能否完成下面的表达式，能的话输出所需的乘法次数，否则输出error

题解：矩阵能进行乘法的条件是A矩阵的列数必须等于B矩阵的行数，否则输出error即可， 能乘时增加的乘法数量是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
/*********************************************************
Flie Name: 442.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月02日 星期五 15时35分28秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

struct Matrix{
	int l, k;
	Matrix(int a = 0, int b = 0) : l(a), k(b) {}
}M[26];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	rep(i, n){
		string s;
		cin >> s;
		cin >> M[s[0] - 'A'].l >> M[s[0] - 'A'].k;
	}
	string expr;
	while(cin >> expr){
		bool error = false;
		int ans = 0;
		stack<Matrix>st;
		for(auto i : expr){
			if(isalpha(i))st.emplace(M[i - 'A']);
			else if(i == ')'){
				auto b = st.top(); st.pop();
				auto a = st.top(); st.pop();
				if(a.k != b.l){
					error = true;
					break;
				}
				ans += a.l * a.k * b.k;
				st.emplace(a.l, b.k);
			}
		}
		if(error)cout << "error\n";
		else cout << ans << '\n';
	}
    
    return 0;
}

Broken Keyboard (a.k.a. Beiju Text)

UVA - 11988

题意：给你一个字符串，其中包含home键和end键，按下后光标会来到最前面或最后面，让你解析出在home和end影响下的字符串

题解：按题意模拟即可，但若直接数组模拟，会产生移动整个数组等影响，十分费时间，"在数组中移动元素是十分低效的，如果有可能，可以使用链表" -- 刘大爷原话。为此我们采用链表实现，用pos储存光标位置，进行模拟, 用数组实现链表即可

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
/*********************************************************
Flie Name: 11988.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月02日 星期五 18时36分18秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int Ma = 1e5 + 100;

int main(){
	char s[Ma];
	int next[Ma];
	while(~scanf("%s", s + 1)){
		int cur = 0, last = 0;
		int len = strlen(s + 1);
		next[0] = 0;
		for(int i = 1; i <= len; i++){
			if(s[i] == '[')cur = 0;
			else if(s[i] == ']')cur = last;
			else {
				next[i] = next[cur];
				next[cur] = i;
				if(cur == last)last = i;
				cur = i;
			}
		}
		for(int i = next[0]; i != 0; i = next[i])\
			putchar(s[i]);
		putchar('\n');
	}
    
    return 0;
}

Boxes in a Line

UVA - 12657

题意：给你一堆标号一到n的盒子， 又给你几个操作：

  1. 1 x y ： 把x盒子移动到y盒子左边
  2. 2 x y ： 把x盒子移动到y盒子右边
  3. 3 x y ： 把x盒子和y盒子互换
  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
/*********************************************************
Flie Name: 12657.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月02日 星期五 19时52分40秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
//using namespace std;

const int Ma = 1e5 + 100;
bool inv;
int left[Ma], right[Ma];

void Connect(int a, int b){
	left[b] = a;
	right[a] = b;
}

int main(){
	int n, m;
	int k = 0;
	while(~scanf("%d%d", &n, &m)){
		memset(left, 0, sizeof(left));
		memset(right, 0, sizeof(right));
		inv = true;
		for(int i = 0; i <= n; i++)
			Connect(i, i + 1);
		while(m--){
			int aim, x, y;
			scanf("%d", &aim);
			if(aim == 4)inv = !inv;
			else {
				scanf("%d%d", &x, &y);
				if(aim == 3 && right[y] == x)std::swap(x, y);
				if(aim != 3 && !inv)aim = 3 - aim;
				int lx = left[x], rx = right[x],
					ly = left[y], ry = right[y];
				if(aim == 1){
					if(ly == x)continue;
					Connect(lx, rx);
					Connect(ly, x);
					Connect(x, y);
				}else if(aim == 2){
					if(ry == x)continue;
					Connect(lx, rx);
					Connect(y, x);
					Connect(x, ry);
				}else if(aim == 3){
					if(rx == y){
						Connect(lx, y);
						Connect(x, ry);
						Connect(y, x);
						continue;
					}
					Connect(lx, y);
					Connect(y, rx);
					Connect(ly, x);
					Connect(x, ry);
				}
			}
		}
		long long ans = 0;
		int t = 0;
		for(int i = 1; i <= n; i++ ){
			t = right[t];
			if(i & 1)ans += t;
		}
		if(!inv && !(n & 1))ans = (long long)n * (n + 1) / 2 - ans;
		printf("Case %d: %lld\n", ++k, ans);
	}
    
    return 0;
}

Dropping Balls

UVA - 679

题意：在二叉树上模拟小球下落，小球到达一个节点如果当前节点开关为关则往左走，否则往右走，给你d层二叉树，和I个球，问你最后一个球停在了哪里

题解：容易想到直接模拟，但 1 <= I <= 524288， 显然会t掉. 下面想到如果小球是奇数个落到节点上，那么它应该往左走，否则往右走，根据这个模拟，避免了I的影响，只需模拟n层，复杂度合理

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
/*********************************************************
Flie Name: 679.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月03日 星期六 09时35分16秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

int main(){
	int T;
	scanf("%d\n", &T);
	while(T--){
		int n, m, k = 1;
		scanf("%d%d", &n, &m);
		for(int i = 1; i < n; i++){
			if(m & 1)k = 2 * k, m = (m + 1) / 2;
			else k = 2 * k + 1, m = m / 2;
		}
		printf("%d\n", k);
	}
	scanf("%d", &T);
    
    return 0;
}

Trees on the level

UVA - 122

题意：输入一棵二叉树，让你按层次遍历输出所有节点的值

题解：容易想到数组无法存下，则建立链树，读入建立树后用bfs进行层次遍历即可，可用内存池或数组实现二叉树避免内存泄漏问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
/*********************************************************
Flie Name: 122内存池版.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 08时50分10秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int maxVal = 10000;
struct Node{
	Node *left, *right;
	int date;
	bool Had;
	Node() : left(nullptr), right(nullptr), Had(false) {};
}node[maxVal];

queue<Node*>freenodes;

void init(){
	for(int i = 0; i < maxVal; i++)
		freenodes.emplace(&node[i]);
}

Node *root;

bool fail;
Node* newNode(){
	Node* u = freenodes.front(); 
	freenodes.pop();
	u->left = u->right = nullptr;
	u->Had = false;
	return u;
}

void destory(Node *u){
	freenodes.emplace(u);
}

void addNode(int v, char *head){
	int len = strlen(head);
	Node* now = root;
	for(int i = 0; i < len - 1; i++)
		if(head[i] == 'L'){
			if(now->left == nullptr)now->left = newNode();
			now = now->left;
		}else if(head[i] == 'R'){
			if(now->right == nullptr)now->right = newNode();
			now = now->right;
		}
	if(now->Had)fail = true;
	now->date = v;
	now->Had = true;
}

vector<int>ans;

bool bfs(){
	queue<Node*>q;
	ans.clear();
	q.emplace(root);
	while(!q.empty()){
		Node* now = q.front();
		q.pop();
		if(!now->Had)return false;
		ans.emplace_back(now->date);
		if(now->left)q.emplace(now->left);
		if(now->right)q.emplace(now->right);
	}
	return true;
}

bool read_input(){
	char s[maxVal];
	fail = false;
	root = newNode();
	while(true){
		if(scanf("%s", s) != 1)return false;
		if(!strcmp(s, "()"))break;
		if(fail)continue;
		int t;
		sscanf(s + 1, "%d", &t);
		addNode(t, strchr(s, ',') + 1);
	}
	return true;
}

void clearTree(Node* u){
	if(u == nullptr)return;
	clearTree(u->left);
	clearTree(u->right);
	destory(u);
}

void outPut(){
	int len = ans.size();
	for(int i = 0; i < len; i++)
		printf("%d%c", ans[i], " \n"[i == len - 1]);
}

int main(){
	init();
	while(read_input()){
		if(fail || !bfs())puts("not complete");
		else outPut();
		clearTree(root);
	}
    
    return 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
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
/*********************************************************
Flie Name: 122数组实现.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 08时50分10秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int maxVal = 1000;

int date[maxVal];

int Left[maxVal], Right[maxVal];
bool Had[maxVal];

const int root = 1;
int cnt = 0;

bool fail;

void newTree(){
	Left[root] = Right[root] = 0;
	Had[root] = false;
	cnt = root;
}
int newNode(){
	int u = ++cnt;
	Left[u] = Right[u] = 0;
	Had[u] = false;
	return u;
}

void addNode(int v, char *head){
	int len = strlen(head);
	int now = root;
	for(int i = 0; i < len - 1; i++)
		if(head[i] == 'L'){
			if(!Left[now])Left[now] = newNode();
			now = Left[now];
		}else if(head[i] == 'R'){
			if(!Right[now])Right[now] = newNode();
			now = Right[now];
		}
	if(Had[now])fail = true;
	date[now] = v;
	Had[now] = true;
}

vector<int>ans;

bool bfs(){
	queue<int>q;
	ans.clear();
	q.emplace(root);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		if(!Had[now])return false;
		ans.emplace_back(date[now]);
		if(Left[now])q.emplace(Left[now]);
		if(Right[now])q.emplace(Right[now]);
	}
	return true;
}

bool read_input(){
	char s[maxVal];
	fail = false;
	newTree();
	while(true){
		if(scanf("%s", s) != 1)return false;
		if(!strcmp(s, "()"))break;
		if(fail)continue;
		int t;
		sscanf(s + 1, "%d", &t);
		addNode(t, strchr(s, ',') + 1);
	}
	return true;
}

void clearTree(int* u){
}

void outPut(){
	int len = ans.size();
	for(int i = 0; i < len; i++)
		printf("%d%c", ans[i], " \n"[i == len - 1]);
}

int main(){
	while(read_input()){
		if(fail || !bfs())puts("not complete");
		else outPut();
		//clearTree(root);
	}
    
    return 0;
}

Tree

UVA - 548

题意：给一颗带权二叉树的中序遍历和后序遍历，问你到根权和最小的叶子是哪个，如果有多个，则叶子本身权值更小

题解：按中序遍历和后序遍历建树，并在过程中不断更新答案

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
/*********************************************************
Flie Name: 548.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 12时29分20秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int Ma = 10100;
int in_order[Ma], post_order[Ma], lch[Ma], rch[Ma];
int n, best, best_sum;

bool read_list(int *a){
	string tem;
	if(!getline(cin, tem))return false;
	istringstream it(tem);
	int t;
	n = 0;
	while(it >> t)a[n++] = t;
	return n > 0;
}

int build(int L1, int R1, int L2, int R2, int sum){
	if(L1 > R1)return 0;
	int root = post_order[R2];
	int mid = L1;
	while(in_order[mid] != root)mid++;
	lch[root] = build(L1, mid - 1, L2, L2 + mid - L1 - 1, sum + root);
	rch[root] = build(mid + 1, R1, L2 + mid - L1, R2 - 1, sum + root);
	if(lch[root] == 0 && rch[root] == 0
	&& (sum + root < best_sum || (sum + root == best_sum && root < best)))
		best = root, best_sum = sum + root;
	return root;
}

int main(){
	while(read_list(in_order)){
		read_list(post_order);
		best_sum = 0x3f3f3f3f;
		build(0, n - 1, 0, n - 1, 0);
		cout << best << '\n';
	}
    
    return 0;
}

Not so Mobile

UVA - 839

题意：给你一个天平，问你是否平衡

题解：按输入建立天平，判断是否平衡

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
/*********************************************************
Flie Name: 839.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 14时14分36秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

int Build(int& W){
	int w1, d1, w2, d2;
	scanf("%d%d%d%d", &w1, &d1, &w2, &d2);
	bool b1 = true, b2 = true;
	if(w1 == 0)b1 = Build(w1);
	if(w2 == 0)b2 = Build(w2);
	W = w1 + w2;
	return b1 && b2 && w1 * d1 == w2 * d2;
}

int main(){
	int T;
	scanf("%d\n", &T);
	while(T--){
		int W;
		if(Build(W))puts("YES");
		else puts("NO");
		if(T)putchar('\n');
	}
    
    return 0;
}

The Falling Leaves

UVA - 699

题意: 按先序遍历输入一颗树，没有节点的地方为-1, 问你让这些节点全落在同一层， 落在同一点数值相加，问这一层的数值情况

题解：按输入建树，模拟节点位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*********************************************************
Flie Name: 699.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 15时52分29秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int Ma = (1 << 8);
int sum[Ma];

void Build(int pos){
	int v;
	cin >> v;
	if(v == -1)return;
	sum[pos] += v;
	Build(pos - 1);
	Build(pos + 1);
}

bool init(){
	memset(sum, 0, sizeof(sum));
	int v;
	cin >> v;
	if(v == -1)return false;
	int mid = Ma / 2;
	sum[mid] += v;
	Build(mid - 1), Build(mid + 1);
	return true;
}

int main(){
	int test = 0;
	while(init()){
		int p = 0;
		while(sum[p] == 0)p++;
		cout << "Case " << ++test << ":\n" << sum[p];
		while(sum[++p])cout << ' ' << sum[p];
		cout << "\n\n";
	}
    
    return 0;
}

Quadtrees

UVA - 297

题意：给你两棵32*32图像的四分树的先序遍历，让你合并两棵四分树，问你最后会有多少个黑色块

题解：黑色为黑色，灰色是节点后有黑色，白色为全白，因此，只有灰色节点需要递归往后，根据这个，可只按先序遍历将画面填好即可

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
/*********************************************************
Flie Name: 297.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 16时50分24秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int Ma = 1024 + 1000, len = 32;
bool buf[len][len];
int cnt;
char s[Ma];

void Draw(const char* s, int& pos, int c, int r, int Len){
	char aim = s[pos++];
	if(aim == 'p'){
		Draw(s, pos, c, r + Len / 2, Len / 2);
		Draw(s, pos, c, r, Len / 2);
		Draw(s, pos, c + Len / 2, r, Len / 2);
		Draw(s, pos, c + Len / 2, r + Len / 2, Len / 2);
	}else if(aim == 'f'){
		for(int i = c; i < c + Len; i++)
			for(int j = r; j < r + Len; j++)
				if(!buf[i][j])cnt++, buf[i][j] = true;
	}
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		memset(buf, 0, sizeof(buf));
		cnt = 0;
		for(int i = 0; i < 2; i++){
			scanf("%s", s);
			int p = 0;
			Draw(s, p, 0, 0 , len);
		}
		printf("There are %d black pixels.\n", cnt);
	}
    
    return 0;
}

Oil Deposits

UVA - 572

题意：给你一片油田地，问你有几块油田

题解：直接搜

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
/*********************************************************
Flie Name: 572.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 18时44分13秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
using namespace std;

const int Ma = 1e2 + 10;
char pic[Ma][Ma];
bool vis[Ma][Ma];
int n, m;

void dfs(int r, int c){
	if(r < 0 || r >= n || c < 0 || c >= m)return;
	if(vis[r][c] || pic[r][c] != '@')return;
	vis[r][c] = true;
	for(int i = -1; i < 2; i++)
		for(int j = -1; j < 2; j++)
			if(i != 0 || j != 0)dfs(r + i, c + j);
}

int main(){
	while(~scanf("%d%d", &n, &m) && n){
		memset(vis, 0, sizeof(vis));
		for(int i = 0 ; i< n; i++)
			scanf("%s", pic[i]);
		int cnt = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				if(pic[i][j] == '@' && !vis[i][j])cnt++, dfs(i, j);
		printf("%d\n", cnt);
	}
    
    return 0;
}

Ancient Messages

UVA - 1103

题意：给你一副十六进制组成的图，问你那有哪些古代符号

题解：根据古代符号的内部白色块个数，对给出图进行遍历即可。先将图转化为二进制

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
/*********************************************************
Flie Name: 1103.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月05日 星期一 20时10分59秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

const int Ma = 2e2 + 10;
char buf[Ma][Ma];
bool Graph[Ma][Ma];
bool vis[Ma][Ma];
char Ans[] = {'W', 'A', 'K', 'J', 'S', 'D'};
int rmv[] = {0, 0, 1, -1}, 
	cmv[] = {1, -1, 0, 0};
int cnt, n, m;

bool judge(int x, int y){
	return x >= 0 && x < n && y >= 0 && y < m;
}

void dfs(int r, int c, bool mod){
	if(!judge(r, c))return;
	if(!Graph[r][c] && !vis[r][c] && mod){
		dfs(r, c, false);
		cnt++;
		return;
	}
	if(vis[r][c])return;
	if(Graph[r][c] != mod)return;
	vis[r][c] = true;
	rep(i, 4){
		int x= r + rmv[i], y = c + cmv[i];
		if(vis[x][y])continue;
		dfs(x, y, mod);
	}
}

int main(){
	int test = 0;
	while(~scanf("%d%d", &n, &m) && n){
		Mem(Graph);
		Mem(vis);
		for(int i = 0; i < n; i++)scanf("%s", buf[i]);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(isdigit(buf[i][j])){
					rep(k, 4)if((1 << (3 - k)) & (buf[i][j] - '0'))Graph[i][j * 4 + k] = true;
				}else if(islower(buf[i][j])){
					rep(k, 4)if((1 << (3 - k)) & (buf[i][j] - 'a' + 10))Graph[i][j * 4 + k] = true;
				}else assert(false);
			}
		}
		m = 4 * m;
		rep(i, n){
			if(!Graph[i][0] && !vis[i][0])dfs(i, 0, false);
			if(!Graph[i][m - 1] && !vis[i][m - 1])dfs(i, m - 1, false);
		}
		rep(i, m){
			if(!Graph[0][i] && !vis[0][i])dfs(0, i, false);
			if(!Graph[n - 1][i] && !vis[n - 1][i])dfs(n - 1, i, false);
		}
		printf("Case %d: ", ++test);
		priority_queue<char, vector<char>, greater<char> >pq;
		rep(i, n)rep(j, m){
			if(Graph[i][j] && !vis[i][j]){
				cnt = 0;
				dfs(i, j, true);
				pq.emplace(Ans[cnt]);
			}
		}
		while(!pq.empty()){
			printf("%c", pq.top());
			pq.pop();
			if(pq.empty())putchar('\n');
		}
	}
    
    return 0;
}

Abbott's Revenge

UVA - 816

题意：给你一个迷宫， 输入起点，离开时的朝向， 终点，让你求一条最短路，输入为节点跟着路标，第一个字符为进入方向，后面为可出去方向

题解：对人进行模拟，bfs搜索，并记录路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
/*********************************************************
Flie Name: 816.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月06日 星期二 10时55分58秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

typedef pair<int, int> pa;

int Dr[] = {-1, 0, 1, 0},
	Dc[] = {0, 1, 0, -1};
const char* dirs = "NESW";
const char* turns = "FLR";
int dir_id(char aim){return strchr(dirs, aim) - dirs;}
int turn_id(char aim){return strchr(turns, aim) - turns;}

struct Node{
	int dir;
	int r, c;
	Node(int dd = 0, int rr = 0, int cc = 0) : dir(dd), r(rr), c(cc){}
	bool operator == (const Node b){return r == b.r && c == b.c;}
};

Node Begin, End;
bool has_edge[10][10][4][3];

Node walk(Node u, int turn){
	int dir = u.dir;
	if(turn == 1)dir = (dir + 3) % 4;
	if(turn == 2)dir = (dir + 1) % 4;
	return Node(dir, u.r + Dr[dir], u.c + Dc[dir]);
}

void readBase(){
	char tem;
	cin >> Begin.r >> Begin.c >> tem;
	int dir = dir_id(tem);
	Begin.r += Dr[dir];
	Begin.c += Dc[dir];
	Begin.dir = dir;
	cin >> End.r >> End.c;
}

void readMap(){
	int r, c;
	while(cin >> r && r){
		cin >> c;
		string tem;
		while(cin >> tem, tem != "*"){
			int len = tem.length();
			int id = dir_id(tem[0]);
			for(int i = 1; i < len; i++)
				has_edge[r][c][id][turn_id(tem[i])] = true;
		}
	}
}

int d[10][10][4];
Node p[10][10][4];

bool inside(int x, int y){return x > 0 && x < 10 && y > 0 && y < 10;}

void Output(Node u);

void bfs(){
	queue<Node>q;
	memset(d, -1, sizeof(d));
	q.emplace(Begin);
	d[Begin.r][Begin.c][Begin.dir] = 0;
	while(!q.empty()){
		Node tem = q.front();
		q.pop();
		if(tem == End){Output(tem); return;}
		int r = tem.r, c = tem.c, dir = tem.dir;
		for(int i = 0; i < 3; i++){
			if(has_edge[r][c][dir][i]){
				Node tt = walk(tem, i);
				if(inside(tt.r, tt.c) && d[tt.r][tt.c][tt.dir] < 0){
					d[tt.r][tt.c][tt.dir] = d[tem.r][tem.c][tem.dir] + 1;
					p[tt.r][tt.c][tt.dir] = tem;
					q.emplace(tt);
				}
			}
		}
	}
	cout << "  No Solution Possible\n";
	return;
}

void Output(Node u){
	vector<Node>ans;
	for(;;){
		ans.emplace_back(u);
		if(d[u.r][u.c][u.dir] == 0)break;
		u = p[u.r][u.c][u.dir];
	}
	ans.emplace_back(Begin.dir, Begin.r - Dr[Begin.dir], Begin.c - Dc[Begin.dir]);
	int len = ans.size();
	int cnt = 0;
	for(int i = len - 1; i >= 0; i--){
		if(cnt % 10 == 0)cout << " ";
		cout << " (" << ans[i].r << "," << ans[i].c << ")";
		if(++cnt % 10 == 0)cout << '\n';
	}
	if(len % 10 != 0)cout << '\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string name;
	while(cin >> name && name != "END"){
		cout << name << '\n';
		Mem(has_edge);
		readBase();
		readMap();
		bfs();
	}
    
    return 0;
}

Ordering Tasks

UVA - 10305

题意：给任务排序，每个任务有一个前置任务

题解：拓扑排序

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
/*********************************************************
Flie Name: 10305.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月07日 星期三 17时08分23秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

bool G[110][110];
int vis[110];
int n, m, t;
int ans[110];

bool dfs(int j){
	vis[j] = -1;
	for(int i = 1; i <= n; i++) if(G[j][i]){
		if(vis[i] < 0)return false;
		else if(!vis[i] && !dfs(i))return false;
	}
	vis[j] = 1;
	ans[--t] = j;
	return true;
}

bool topo(){
	Mem(vis);
	t = n;
	for(int i = 1; i <= n; i++)
		if(!vis[i] && !dfs(i))return false;
	return true;
}

void Output(){
	for(int i = 0; i < n; i++)
		printf("%d%c", ans[i], " \n"[i == n - 1]);
}

int main(){
	while(~scanf("%d%d", &n, &m) && n){
		Mem(G);
		for(int i = 0; i < m; i++){
			int a, b;
			scanf("%d%d", &a, &b);
			G[a][b] = true;
		}
		if(topo())Output();
		else assert(false);
	}
    
    return 0;
}

Play on Words

UVA - 10129

题意：给你n个单词，问你能否把这些单词排成一个序列，使每个单词地一个字母和上一个单词最后一个字母相同。

题解：将单词首字母和结尾字母建立一条有向边。问题有解， 当且仅当图为欧拉路径，且判断是否能联通。

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
/*********************************************************
Flie Name: 10129.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月07日 星期三 18时16分28秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

const int Ma = 1e5 + 100;
string tem[Ma];
int word[30];
int fa[30];

void init(){
	for(int i = 0; i < 30; i++)
		fa[i] = i;
}

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

void Con(int a, int b){
	int pa = fin(a), pb = fin(b);
	if(pa == pb)return ;
	fa[pb] = pa;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--){
		Mem(word);
		init();
		int n;
		cin >> n;
		set<int>happen;
		rep(i, n){
			cin >> tem[i];
			word[tem[i][0] - 'a']--;
			word[*tem[i].rbegin() - 'a']++;
			happen.insert(tem[i][0] - 'a');
			happen.insert(*tem[i].rbegin() - 'a');
			Con(tem[i][0] - 'a', *tem[i].rbegin() - 'a');
		}
		bool can = true;
		int t = fin(*happen.begin());
		for(int i : happen)
			if(fin(i) != t)can = false;
		bool rb = false, fb = false;
		for(int i = 0; can && i <= 26; i++){
			if(abs(word[i]) > 1)can = false;
			else if(word[i] == 1){
				if(!rb)rb = true;
				else can = false;
			}else if(word[i] == -1){
				if(!fb)fb = true;
				else can = false;
			}
		}
		cout << (can ? "Ordering is possible.\n" : "The door cannot be opened.\n");
	}

    return 0;
}

Undraw the Trees

UVA - 10562

题意： 给你n棵树，让你把树转化为括号表示法

题解：递归遍历并输出

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
/*********************************************************
Flie Name: 10562.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年08月08日 星期四 10时33分20秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

const int Ma = 2e2 + 10;
char buf[Ma][Ma];

int n;

void dfs(int r, int c){
	putchar(buf[r][c]);
	putchar('(');
	if(r + 1 < n && buf[r + 1][c] == '|'){
		int fc = c;
		while(fc - 1 >= 0 && buf[r + 2][fc - 1] == '-')fc--;
		while(buf[r + 2][fc] == '-' && buf[r + 3][fc] != '\0'){
			if(!isspace(buf[r + 3][fc]))dfs(r + 3, fc);
			fc++;
		}
	}
	putchar(')');
}

void solve(){
	n = 0;
	while(fgets(buf[n], Ma, stdin), buf[n++][0] != '#');
	putchar('(');
	if(--n){
		int len = strlen(buf[0]);
		for(int i = 0; i < len; i++) if(buf[0][i] != ' '){
			dfs(0, i);
			break;
		}
	}
	puts(")");
}

int main(){
	int T;
	fgets(buf[0], Ma, stdin);
	sscanf(buf[0], "%d", &T);
	while(T--)
		solve();
    
    return 0;
}

Sculpture

UVA - 12171

题意：给你一个雕塑，问你雕塑的表面积和体积

题解：将雕塑画到三维空间中，进行一次floodfill， 得出雕塑体积和空气内表面积, 得进行离散化处理空间问题

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

const int Ma = 110, inf = 1001;
int flower[Ma][Ma][Ma];

struct Com{
	int x0, y0, z0, x1, y1, z1;
	Com(int xx, int yy, int zz, int x, int y, int z)
	: x0(xx), y0(yy), z0(zz) {
		x1 = x0 + x, y1 = y0 + y, z1 = z0 + z; 
	}
};

std::vector<Com> com;
int X[Ma], Y[Ma], Z[Ma];
int lx, ly, lz;

void discretize(int* x, int& len, int n){
	sort(x, x + n);
	len = unique(x, x + n) - x;
}

int ID(int *x, int v, int len){
	return lower_bound(x, x + len, v) - x;
}

int dix[] = {1, -1, 0, 0, 0, 0},
	diy[] = {0, 0, 1, -1, 0, 0},
	diz[] = {0, 0, 0, 0, 1, -1};

struct Cell{
	int x, y, z;
	Cell(int xx = 0, int yy = 0, int zz = 0)
	: x(xx), y(yy), z(zz){}
	bool valid() const {
		return x >= 0 && x < lx - 1 && y >= 0 && y < ly - 1 && z >= 0 && z < lz - 1;
	}
	bool visited() const {return flower[x][y][z] == 2;}
	bool dicvis() const {return flower[x][y][z] == 1;}
	void setVis() {flower[x][y][z] = 2;}
	Cell neighbor(int dir){
		return Cell(x + dix[dir], y + diy[dir], z + diz[dir]);
	}
	int edge(int* wh, int w){
		return wh[w + 1] - wh[w];
	}
	int vol(){
		return edge(X, x) * edge(Y, y) * edge(Z, z);
	}
	int area(int dir){
		if(dix[dir] != 0)return edge(Y, y) * edge(Z, z);
		if(diy[dir] != 0)return edge(X, x) * edge(Z, z);
		return edge(X, x) * edge(Y, y);
	}
};

void floodfill(int& val, int& sum){
	Cell c;
	queue<Cell>q;
	c.setVis();
	q.push(c);
	while(!q.empty()){
		Cell t = q.front();
		sum += t.vol();
		q.pop();
		for(int i = 0; i < 6; i++){
			Cell m = t.neighbor(i);
			if(!m.valid())continue;
			if(m.dicvis())val += m.area(i);
			else if(!m.visited())m.setVis(), q.push(m);
		}
	}
	sum = inf * inf * inf - sum;
}

void fill(int x1, int y1, int z1, int x2, int y2, int z2){
	for(int x = x1; x < x2; x++)
		for(int y = y1; y < y2; y++)
			for(int z = z1; z < z2; z++)
				flower[x][y][z] = 1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--){
		memset(flower, 0, sizeof(flower));
		com.clear();
		int n, cnt = 0;
		X[cnt] = Y[cnt] = Z[cnt] = 0;
		cnt++;
		X[cnt] = Y[cnt] = Z[cnt] = inf;
		cin >> n;
		for(int i = 0; i < n; i++){
			int x0, y0, z0, x, y, z;
			cin >> x0 >> y0 >> z0 >> x >> y >> z;
			com.push_back(Com(x0, y0, z0, x, y, z));
			cnt++;
			X[cnt] = x0, Y[cnt] = y0, Z[cnt] = z0;
			cnt++;
			X[cnt] = x0 + x, Y[cnt] = y0 + y, Z[cnt] = z0 + z;
		}
		cnt++;
		discretize(X, lx, cnt);
		discretize(Y, ly, cnt);
		discretize(Z, lz, cnt);

		for(int j = 0; j < n; j++){
			Com i = com[j];
			fill(ID(X, i.x0, lx), ID(Y, i.y0, ly), ID(Z, i.z0, lz),
			 	 ID(X, i.x1, lx), ID(Y, i.y1, ly), ID(Z, i.z1, lz));
		}
		int val = 0, sum = 0;
		floodfill(val, sum);
		cout << val << ' ' << sum << '\n';
	}

	return 0;
}

Self-Assembly

UVA - 1572

题意：给你n种正方形，只有正和负能拼接，问你能否得到一个无限大的结构

题解：根据题意分析，根据正方形建边，当图中存在有向环时，则通过旋转和翻转，一定能得到无限大的结构，进行拓扑排序，找环即可。

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
/*********************************************************
Flie Name: 1572.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年09月13日 星期五 10时33分44秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

bool G[52][52];

int Id(char a, char b){
	return (a  - 'A') * 2 + (b == '+' ? 1 : 0);
}

void connect(char a1, char a2, char b1, char b2){
	if(a1 == '0' || b1 == '0')return ;
	G[Id(a1, a2) ^ 1][Id(b1, b2)] = true;
}

int vis[52];

bool dfs(int ind){
	vis[ind] = -1;
	rep(i, 52)if(G[ind][i]){
		if(vis[i] < 0)return true;
		else if(!vis[i] && dfs(i))return true;
	}
	vis[ind] = 1;
	return false;
}

bool find_cycle(){
	rep(i, 52)if(!vis[i])
		if(dfs(i))return true;
	return false;
}

int main(){
	int n;
	while(~scanf("%d", &n)){
		Mem(G);
		Mem(vis);
		rep(k, n){
			char s[8];
			scanf("%s", s);
			rep(i, 4)rep(j, 4)if(i != j)
				connect(s[i * 2], s[i * 2 + 1], s[j * 2], s[j * 2 + 1]);
		}
		if(find_cycle())puts("unbounded");
		else puts("bounded");
	}
    
    return 0;
}

Ideal Path

UVA - 1599

题意：给你n个点，m条边，和每条边的颜色，问你1到n的最短路，且经过边上的颜色字典序最小

题解：刘大爷说明的是走两遍bfs，一遍跑最短路，一遍跑最小字典序。并提出一遍bfs的方法给我读者思考，通过从终点往起点搜，找到到达一个点的更多选择后了选择字典序更小的那个，这对最短路无影响，同时确定了最短路的颜色字典序最小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
#include<bits/stdc++.h>
using namespace std;

const int Ma = 1e5 + 100;

struct InputOutputStream {
    enum { SIZE = 1000001 };
    char ibuf[SIZE], *s, *t, obuf[SIZE], *oh;
    bool eof;

    InputOutputStream() : s(), t(), oh(obuf), eof(false) {}
    ~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }

    inline char read() {
        if (s == t) t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin);
        return s == t ? -1 : *s++;
    }

    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        static char c;
        static bool iosig;
        for (c = read(), iosig = false; !isdigit(c); c = read()) {
            if (c == -1) {eof = true; return *this;}
            iosig |= c == '-';
        }
        for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
        if (iosig) x = -x;
        return *this;
    }

    inline void print(char c) {
        if (oh == obuf + SIZE) {
            fwrite(obuf, 1, SIZE, stdout);
            oh = obuf;
        }
        *oh++ = c;
    }

    template <typename T>
    inline void print(T x) {
        static int buf[23], cnt;
        if (x != 0) {
            if (x < 0) print('-'), x = -x;
            for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
            while (cnt) print((char)buf[cnt--]);
        } else print('0');
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }
} io;

struct Node{
	int u, v, c, nex;
}node[Ma * 4];

int head[Ma], cnt;

int dis[Ma], pre[Ma];

void init(int n){
	for(int i = 0; i <= n; i++)
		head[i] = -1, dis[i] = 0, pre[i] = -1;
	cnt = 0;
}

void add(int u, int v, int c){
	node[cnt].v = v, node[cnt].c = c, node[cnt].u = u;
	node[cnt].nex = head[u], head[u] = cnt++;
}

void rebfs(int n){
	bool vis[n + 1];
	memset(vis, 0, sizeof(vis));
	queue<int> q;
	q.emplace(n);
	vis[n] = true;
	while(!q.empty()){
		int t = q.front();
		if(t == 1)break;
		q.pop();
		for(int i = head[t]; ~i; i = node[i].nex){
			const auto& temp = node[i];
			if(!vis[temp.v]){
				dis[temp.v] = dis[t] + 1;
				pre[temp.v] = i;
				vis[temp.v] = true;
				q.emplace(temp.v);
			}else if(dis[temp.v] == dis[t] + 1){
				int x = i, y = pre[temp.v];
				//assert(x > 0 && y > 0);
				while(node[x].u != n && node[x].c == node[y].c && x != y)
					/*assert(x > 0 && y > 0),*/ x = pre[node[x].u], y = pre[node[y].u];
				if(node[x].c < node[y].c)pre[temp.v] = i, q.emplace(temp.v);
			}
		}
	}
	io << dis[1] << '\n';
	int x = 1;
	while(x != n){
		io << node[pre[x]].c;
		x = node[pre[x]].u;
		if(x != n)io << ' ';
		else io << '\n';
	}
}


int main(){
	int n, m;
	while((io >> n >> m), !io.eof){
		init(n);
		for(int u, v, c, i = 0; i < m; i++){
			io >> u >> v >> c;
			add(u, v, c);
			add(v, u, c);
		}
		rebfs(n);
	}

	return 0;
}

System Dependencies

UVA - 506

题意：模拟liunx的包管理系统，安装和卸载软件，解决依赖问题

题解：安装如果没有显式声明的话无法通过显式卸载卸载，还有依赖的检查，注意这些进行模拟，UVA的样列又（我为什么要说又）出错了，样例最后的那个HTML和TCPIP的删除顺序反了, 说的多组输入也只有一组，，uva标准风格，，

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
/*********************************************************
Flie Name: 506.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年10月12日 星期六 15时06分28秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

map<string, int>name;
vector<string> pname;

const int Ma = 1e5;

int statu[Ma];

map<int, vector<int>>depend, dependi;
vector<int>installer;

void install(int id, int level){
	if(!statu[id]){
		for(const auto& i : depend[id])
			install(i, 2);
		cout << "   Installing " << pname[id] << '\n';
		statu[id] = level;
		installer.emplace_back(id);
	}else if(level == 1)
		cout << "   " << pname[id]  << " is already installed.\n";
}

bool need(int id){
	for(const auto i : dependi[id])
		if(statu[i])return true;
	return false;
}

void remove(int id, int level){
	if(statu[id] == level && !need(id)){
		cout << "   Removing " << pname[id] << '\n';
		statu[id] = 0;
		installer.erase(remove(seg(installer), id), installer.end());
		for(const auto& i : depend[id])
			remove(i, 2);
	}else if(statu[id] == 0 && level == 1)
		cout << "   " << pname[id] << " is not installed.\n";
	else if(level == 1 && need(id))
		cout << "   " << pname[id] << " is still needed.\n";
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	try{
		while(true){
			name.clear();
			pname.clear();
			depend.clear();
			dependi.clear();
			installer.clear();
			memset(statu, 0, sizeof(statu));
			string com = "", line = "";
			while(getline(cin, line)){
				cout << line << '\n';
				stringstream ss(line);
				ss >> com;
				if(com[0] == 'E')break;
				else if(com[0] == 'D'){
					string aim;
					ss >> aim;
					if(!name.count(aim))
						name[aim] = name.size(), pname.emplace_back(aim);
					string temp;
					while(ss >> temp){
						if(!name.count(temp))
							name[temp] = name.size(), pname.emplace_back(temp);
						depend[name[aim]].emplace_back(name[temp]);
						dependi[name[temp]].emplace_back(name[aim]);
					}
				}else if(com[1] == 'N'){
					string aim;
					ss >> aim;
					if(!name.count(aim))
						name[aim] = name.size(), pname.emplace_back(aim);
					install(name[aim], 1);
				}else if(com[0] == 'R') {
					string aim;
					ss >> aim;
					if(!name.count(aim))
						name[aim] = name.size(), pname.emplace_back(aim);
					remove(name[aim], 1);
				}else 
					for(const auto& i : installer)
						cout << "   " << pname[i] << '\n';
			}
			if(com == "")throw -1;
		}
	}catch(...){
		
	}
    
    return 0;
}

Paintball

UVA - 11853

题意：有n个敌人，每个敌人有一个坐标和一个攻击半径，问你你能否安全从左边到达右边，能的话输出最北的进出口

题解： 把敌人作为路径， 从上到下进行一次dfs， 如果能连通，则不可能通过，否则能，且与边界交界的 最南的那点就是最北的进出口

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
/*********************************************************
Flie Name: 11853.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年10月15日 星期二 20时24分02秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
using namespace std;

const double eps = 1e-6;

struct Node{
	double x, y;
	double rang;
	int indx;
	Node(double _x, double _y, double _r, int _i) :
		x(_x), y(_y), rang(_r), indx(_i) {}
	bool inme(double a, double b){
		double lx = fabs(a - x), ly = fabs(b - y);
		return lx * lx + ly * ly - rang * rang < eps;
	}
};

const double mx = 1000.00;
const int Ma = 1e4;
vector<Node>v;
bool vis[Ma];

bool inhere(const Node& temp){
	return temp.y + temp.rang - mx > eps;
}

bool wet(const Node& a, const Node& b){
	double lx = a.x - b.x, ly = a.y - b.y;
	double dis = lx * lx + ly * ly;
	double ra = a.rang + b.rang;
	//cout << a.indx << ' ' << b.indx << ' ' << ra << ' ' << ra * ra << ' ' << dis << endl;
	return (dis - ra * ra) < eps;
}

double le, ri;

void update(const Node& temp){
	if(temp.x - temp.rang < eps)
		le = min(le, temp.y - sqrt(temp.rang * temp.rang - temp.x * temp.x));
	if(temp.x + temp.rang - mx > eps)
		ri = min(ri, temp.y - sqrt(temp.rang * temp.rang - (mx - temp.x) * (mx - temp.x)));
}

bool dfs(const Node& temp){
	if(vis[temp.indx])return false;
	vis[temp.indx] = true;
	if(temp.y - temp.rang < eps)return true;
	for(const auto& i : v){
		if(&i == &temp)continue;
		else if(!vis[i.indx] && wet(temp, i) && dfs(i))return true;
	}
	update(temp);
	return false;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	while(cin >> n){
		le = ri = mx;
		memset(vis, 0, sizeof(vis));
		v.clear();
		for(int i = 0; i < n; i++){
			double a, b, c;
			cin >> a >> b >> c;
			v.emplace_back(Node(a, b, c, i));
		}
		bool win = true;
		for(const auto& i : v)
			if(!vis[i.indx] && inhere(i) && dfs(i)){
				win = false;
				break;
			}
		cout.setf(ios::fixed);
		cout.precision(2);
		if(win)cout << "0.00 " << le << " 1000.00 " << ri << '\n';
		else cout << "IMPOSSIBLE\n";
	}

    return 0;
}

爽，再更完习题就能学暴力了！

Comments

⬆︎TOP