算法竞赛入门经典第六章习题(14/14)

习题， 第六章的最后部分了

我能去学暴力了！

学完暴力就能学竞赛篇了！幸福！

Parentheses Balance

UVA - 673

题解：给你一堆括号序列，问你能否达成括号匹配

题解：可能有空行，注意， 用栈进行模拟

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	map<char, char>ju;
	ju[')'] = '(';
	ju[']'] = '[';
	int T;
	cin >> T;
	cin.ignore();
	while(T--){
		stack<char> st;
		string temp;
		getline(cin, temp);
		bool can = true;
		for(const auto& i : temp)
			if(ju.count(i)){
				if(!st.empty() && st.top() == ju[i])
					st.pop();
				else {
					can = false;
					break;
				}
			}else st.emplace(i);
		if(can && st.empty())cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

S-Trees

UVA - 712

题意： 给你n个变量，组成n层二叉树， 给出n+1层节点的值， 再来q个询问， 每个询问给每个变量一个值， 每个节点取0时向左走，取1时向右走，问你q的询问后的答案

题解： 直接模拟，对每个询问，每次下一层节点范围减半，记录叶子节点答案即可

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k = 0;
	while(cin >> n && n){
		cout << "S-Tree #" << ++k << ":\n";
		int pos[12];
		for(int i = 0; i < n; i++){
			string temp;
			cin >> temp;
			pos[i] = temp[1] - '0' - 1;
		}
		string aim;
		cin >> aim;
		int len = aim.length();
		int q;
		cin >> q;
		string ans;
		for(int i = 0; i < q; i++){
			string ask;
			cin >> ask;
			int le = 0, ri = len;
			for(int i = 0; i < n; i++){
				int mid = (le + ri) / 2;
				if(ask[pos[i]] == '0')ri = mid;
				else le = mid;
			}
			//cout << "le == " << le << endl;
			ans += aim[le];
		}
		cout << ans << '\n';
		cout << '\n';
	}

	return 0;
}

Tree Recovery

UVA - 536

题意：让你根据先序遍历和中序遍历输出后序遍历的结果

题解： 直接模拟建立输出

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

string pre, in, post;

void build(int pbe, int pen, int ibe, int ien){
	if(ibe == ien)return ;
	int center = in.find(pre[pbe]);
	assert(center != string::npos);
	build(pbe + 1, pen, ibe, center);
	build(pbe + 1 + center - ibe, pen, center + 1, ien);
	post += pre[pbe];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while(cin >> pre >> in){
		post.clear();
		build(0, pre.length(), 0, in.length());
		cout << post << '\n';
	}

	return 0;
}

Knight Moves

UVA - 439

题意：给你一个起点一个终点， 问你国际象棋中的骑士要走几步才能从起点走到终点

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

typedef pair<int, int> pa;

const int Ma = 8;

bool vis[Ma][Ma];

int mx[] = {1, -1, 1, -1, 2, 2, -2, -2},
	my[] = {2, 2, -2, -2, 1, -1, 1, -1};

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

struct Node{
	pa man;
	int cnt;
	bool operator == (const pa b) const {
		return man == b;
	}
};

int bfs(pa be, pa en){
	queue<Node>q;
	q.emplace(Node{be, 0});
	Node temp;
	vis[be.first][be.second] = true;
	while(!q.empty()){
		temp = q.front(); q.pop();
		if(temp == en)break;
		for(int i = 0; i < 8; i++){
			int x = temp.man.first + mx[i],
				y = temp.man.second + my[i];
			if(judge(x, y) && !vis[x][y])vis[x][y] = true, q.emplace(Node{pa(x, y), temp.cnt + 1});
		}
	}
	return temp.cnt;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string be, en;
	while(cin >> be >> en){
		memset(vis, 0, sizeof(vis));
		pa b, e;
		b.first = be[0] - 'a', b.second = be[1] - '1';
		e.first = en[0] - 'a', e.second = en[1] - '1';
		cout << "To get from "<< be << " to " << en << " takes " <<
		bfs(b, e) << " knight moves.\n";
	}

	return 0;
}

Patrol Robot

UVA - 1600

题意：给你一个n * m 的图，且你能飞过k长度的障碍， 问你能否从左上角到右下角

题解：一开始看着自然会想用三维标记到节点剩余步数的所有状态，直接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
#include <bits/stdc++.h>
using namespace std;

const int Ma = 22;
int mz[Ma][Ma];
int n, m;
bool vis[Ma][Ma][Ma];

struct Node{
	int x, y, cnt, pre;
	bool over(){
		return x == n - 1 && y == m - 1;
	}
};

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

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

int bfs(int k){
	queue<Node>q;
	q.push(Node{0, 0, 0, 0});
	vis[0][0][0] = true;
	Node temp;
	while(!q.empty()){
		temp = q.front();
		if(temp.over())break;
		q.pop();
		if(temp.pre > k)continue;
		for(int i = 0; i < 4; i++){
			int x = temp.x + xz[i], y = temp.y + yz[i];
			if(judge(x, y) && !vis[x][y][(mz[x][y] ? temp.pre + 1 : 0)])
				vis[x][y][(mz[x][y] ? temp.pre + 1 : 0)] = true,
				q.emplace(Node{x, y, temp.cnt + 1, (mz[x][y] ? temp.pre + 1 : 0)});
		}
	}
	return (q.empty() ? -1 : temp.cnt);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--){
		memset(vis, 0, sizeof(vis));
		cin >> n >> m;
		int k;
		cin >> k;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				cin >> mz[i][j];
		cout << bfs(k) << endl;
	}

	return 0;
}

Equilibrium Mobile

UVA - 12166

题意： 给你一个深度不超过16的天平，问你至少要修改多少个秤砣的重量才能使得天平平衡

题解：如果不修改一个节点，那么天平的质量就是定的，记录不修改每个节点天平的重量，取其中节点最多的那种。 会爆int， 得用longlong

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

int cnt, mx_cnt;
typedef long long ll;
map<ll, int>cot;
string aim;

ll build(int le, int ri, int dp){
	ll ans = 0;
	if(aim[le] == '['){
		int now = 1 + le;
		int tt = 0;
		while(tt || aim[now] != ','){
			if(aim[now] == '[')tt++;
			else if(aim[now] == ']')tt--;
			now++;
		}
		//cout << "pre = " << le + 1 << ' ' << now - 1 << endl;
		ans += build(le + 1, now - 1, dp + 1);
		//cout << "post = " << now + 1 << ' ' << ri - 1 << endl;
		ans += build(now + 1, ri - 1, dp + 1);
	}else {
		stringstream ss(aim.substr(le, ri - le + 1));
		//cout << aim.substr(le, ri - le + 1) << endl;
		ss >> ans;
		cnt++, cot[ans << dp]++,
		mx_cnt = max(mx_cnt, cot[ans << dp]);
	}
	
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--){
		cnt = mx_cnt = 0;
		cot.clear();
		cin >> aim;
		build(0, aim.length() - 1, 1);
		cout << cnt - mx_cnt << '\n';
	}

	return 0;
}

Petri Net Simulation

UVA - 804

题意： 让你模拟petri网的变迁，

题解：具体描述参考原题面， 直接模拟即可，最后输出结束或死后每个有taken的地方，和有多少个taken

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

const int Ma = 110;

struct NT{
	map<int, int> pre, next;
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k = 0;
	while(cin >> n && n){
		cout << "Case " << ++k << ": ";
		vector<int> np(n);
		for(int i = 0 ; i < n; i++)
			cin >> np[i];
		int t;
		cin >> t;
		vector<NT> nt(t);
		for(int i = 0; i < t; i++){
			int aim;
			while(cin >> aim && aim){
				if(aim > 0)nt[i].next[aim - 1]++;
				else nt[i].pre[-aim - 1]++;
			}
		}
		int round;
		cin >> round;
		bool dead = false;
		int i;
		for(i = 0; !dead && i < round;){
			dead = true;
			for(const auto& j : nt){
				bool judge = true;
				for(const auto& q : j.pre)
					if(np[q.first] < q.second)judge = false;
				if(!judge)continue;
				else {
					i++;
					dead = false;
					for(const auto& q : j.pre)
						np[q.first] -= q.second;
					for(const auto& q : j.next)
						np[q.first] += q.second;
					if(i == round)break;
				}
			}
			
		}
		if(dead)cout << "dead after ";
		else cout << "still live after ";
		cout << i << " transitions\nPlaces with tokens:";
		for(int i = 0; i < n; i++)
			if(np[i] > 0)
				cout << ' ' << i + 1 << ' ' << '(' << np[i] << ')';
		cout << "\n\n";
	}

	return 0;
}

Spatial Structures

UVA - 806

题意： 让你把一张图像的四分树表示和点阵表示相互转换

题解: 按题意模拟即可，注意输出数字时每十二个一行，和全为1时的处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

const int Ma = 72;
int Pic[Ma][Ma];
vector<int>ans;

int Pow(int n){
	if(n == -1)return 0;
	int sum = 1;
	while(n)sum *= 5, n--;
	return sum;
}

int J(int a){
	return a > 0 ? 1 : 0;
}

int build(int len, int xp, int yp, int indx, int bit, int pre){
	int pp = pre + indx * Pow(bit);
	//cout << len << ' ' << xp << ' ' << yp << ' ' << pp << ' ' << Pic[xp][yp] << endl;
	if(len == 1)return bit == -1 ? Pic[yp][xp] : Pic[yp][xp] * pp;
	int p1 = build(len / 2, xp, yp, 1, bit + 1, pp);
	int p2 = build(len / 2, xp + len / 2, yp, 2, bit + 1, pp);
	int p3 = build(len / 2, xp, yp + len / 2, 3, bit + 1, pp);
	int p4 = build(len / 2, xp + len / 2, yp + len / 2, 4, bit + 1, pp);
	int ju = J(p1) + J(p2) + J(p3) + J(p4);
	//cout << "son " << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << endl; 
	if(ju == 4){
		return bit == -1 ? 1 : pp;
	}else {
		if(J(p1))ans.emplace_back(p1);
		if(J(p2))ans.emplace_back(p2);
		if(J(p3))ans.emplace_back(p3);
		if(J(p4))ans.emplace_back(p4);
		return 0;
	}
}

void solvePic(int n){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			scanf("%1d", &Pic[i][j]);
	/*	for(int i = 0; i < n; i++, cout << '\n')
		for(int j = 0; j < n; j++)
			cout << Pic[i][j];*/
	if(build(n, 0, 0, 0, -1, 0))ans.emplace_back(0);
	sort(ans.begin(), ans.end());
	int cnt = 0;
	for(auto i = ans.begin(); i != ans.end(); i++){
		if(cnt)cout << ' ';
		cout << *i;
		if(cnt == 11)cnt = 0, cout << '\n';
		else cnt++;
	}
	if(cnt && ans.size() > 0)cout << '\n';
	cout << "Total number of black nodes = " << ans.size() << '\n';
}

void Full(int t, int n){
	int bit = 0;
	int len = n, xp = 0, yp = 0;
	for(;;){
		int pos = t % 5;
		if(pos == 0){
			for(int i = 0; i < len; i++)
				for(int j = 0; j < len; j++)
					Pic[yp + i][xp + j] = 1;
			break;
		}
		else if(pos == 2)xp += len / 2;
		else if(pos == 3)yp += len / 2;
		else if(pos == 4)xp += len / 2, yp += len / 2;
		t /= 5;
		len /= 2;
	}
}

void solveNum(int n){
	memset(Pic, 0, sizeof(Pic));
	int t;
	while(cin >> t && ~t)
		Full(t, n);
	for(int i = 0; i < n; i++, cout << '\n')
		for(int j = 0; j < n; j++)
			cout << (Pic[i][j] ? '*' : '.');
}

int main(){
	//ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k = 0;
	bool im = false;
	while(cin >> n && n){
		if(im)cout << '\n';
		else im = true;
		cout << "Image " << ++k << '\n';
		ans.clear();
		if(n > 0)solvePic(n);
		else solveNum(-n);
	}

	return 0;
}

"Accordian" Patience

UVA - 127

题意：给你52张牌， 让你按题目所述规则进行模拟合并牌堆， 并输出牌堆的牌的数量

题解：按题意模拟, 注意末尾pile的单复数问题

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

struct Card{
	char suit, rank;
	Card(char temp[]):suit(temp[0]), rank(temp[1]){}
	bool operator == (const Card& b) const {
		return suit == b.suit || rank == b.rank;
	}
};

stack<Card> card[53];
int len;
int cnt;

void init(){
	len = 52, cnt = 0;
	while(!card[0].empty())
		card[0].pop();
}

inline char rCard(){
	static char temp[3];
	scanf("%s", temp);
	card[cnt++].emplace(Card(temp));
	return temp[0];
}

bool judge(int le, int& pos){
	if(card[pos].empty())return 0;
	int ju = 0, pre = pos;
	for(; pos > 0 && ju < le; )
		if(!card[--pos].empty())ju++;
	//cout << ju << ' ' << pos << ' ' << pre <<  endl;
	if(ju == le && card[pos].top() == card[pre].top()){
		card[pos].emplace(card[pre].top());
		card[pre].pop();
		return true;
	}else {
		pos = pre;
		return false;
	}
}

int main(){
	while(init(), rCard() != '#'){
		for(int i = 1; i < 52; i++){
			while(!card[i].empty())
				card[i].pop();
			rCard();
		}
		for(int i = 0; i < len; i++)
			while(judge(3, i) || judge(1, i));
		queue<int>ans;
		for(int i = 0; i < 52; i++)
			if(!card[i].empty())ans.emplace(card[i].size());
		printf("%d %s remaining:", ans.size(), ans.size() == 1 ? "pile" : "piles");
		while(!ans.empty())
			printf(" %d", ans.front()), ans.pop();
		putchar('\n');
	}

	return 0 ;
}

10-20-30

UVA - 246

题意： 给你52张牌，每次依次往七个牌堆上放牌， 牌堆没牌就消失了， 让你按

  1. the first two and last one,
  2. the first one and the last two, or
  3. the last three cards.

加起来能等于10, 20, 30就按顺序收入手牌底的规则进行模拟，如果没手牌就输了，没牌堆了就赢了， 陷入循环就陷入恋爱循环了

题解：按题意模拟， 对状态进行编码，以便检查是否陷入循环

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

const int Ma = 55;
deque<int>pai;

inline bool rCard(){
	int temp;
	scanf("%d", &temp);
	if(!temp)return false;
	pai.emplace_back(temp);
	for(int i = 1; i < 52; i++)
		scanf("%d", &temp), pai.emplace_back(temp);
	return true;
}

deque<int> card[8];
list<deque<int>*> piles;
set<string> stu;

void init(){
	piles.clear(), stu.clear();
	for(int i = 0; i < 7; i++){
		card[i].clear();
		card[i].emplace_back(pai.front());
		piles.emplace_back(card + i);
		pai.pop_front();
	}
}

void encode(string& aim){
	for(const auto& i : piles){
		for(const auto& j : *i)
			aim += char(j);
		aim += '|';
	}
	for(const auto& i : pai)
		aim += char(i);
}

void Pgg(deque<int>& q){
	int n = q.size();
	if(n < 3)return ;

	if((q[0] + q[1] + q[n - 1]) % 10 == 0){
		pai.emplace_back(q[0]),
		pai.emplace_back(q[1]),
		pai.emplace_back(q[n - 1]),
		q.pop_front(), q.pop_front(), q.pop_back();
		Pgg(q);
		return ;
	}

	if((q[0] + q[n - 1] + q[n - 2]) % 10 == 0){
		pai.emplace_back(q[0]),
		pai.emplace_back(q[n - 2]),
		pai.emplace_back(q[n - 1]),
		q.pop_front(), q.pop_back(), q.pop_back();
		Pgg(q);
		return ;
	}

	if((q[n - 1] + q[n - 2] + q[n - 3]) % 10 == 0){
		pai.emplace_back(q[n - 3]),
		pai.emplace_back(q[n - 2]),
		pai.emplace_back(q[n - 1]),
		q.pop_back(), q.pop_back(), q.pop_back();
		Pgg(q);
		return ;
	}
}

bool runTurn(int time){
	assert(piles.size() <= 7);
	if(piles.empty()){
		printf("Win : %d\n", time);
		return false;
	}

	if(pai.empty()){
		printf("Loss: %d\n", time);
		return false;
	}

	string now;
	assert(now.empty());
	encode(now);
	if(stu.count(now)){
		printf("Draw: %d\n", time);
		return false;
	}else stu.emplace(now);

	deque<int>& q = *piles.front();
	piles.emplace_back(piles.front());
	piles.pop_front();
	q.emplace_back(pai.front());
	pai.pop_front();

	Pgg(q);
	if(q.empty())piles.pop_back();
	return true;
}

int main(){
	while(pai.clear(), rCard()){
		assert(pai.size() == 52);
		init();
		assert(pai.size() == 52 - 7);
		int t = 7;
		while(runTurn(t++));
	}

	return 0;
}

Tree Reconstruction

UVA - 10410

题意：让你根据bfs序和dfs序，保证遍历时有更小的节点可走时走更小的节点

题解：按dsf序为主进行递归便利，用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
#include <bits/stdc++.h>
using namespace std;

const int Ma = 1e3 + 100;
int dfs[Ma];
int wb[Ma];
list<int>ans[Ma];

void init(int n){
	for(int i = 0; i <= n; i++)
		ans[i].clear();
}

int gao(int le, int ri){
	int root = dfs[le], last = le + 1, val = dfs[last];
	for(++le; le < ri; le++){
		if(val < dfs[le] && wb[val] + 1 == wb[dfs[le]])
			val = dfs[le],
			ans[root].emplace_back(gao(last, le)),
			last = le;
	}
	if(last < ri)ans[root].emplace_back(gao(last, ri));
	return root;
}

/*6
1 2 3 4 5 6
1 2 4 5 3 6*/

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	while(cin >> n){
		init(n);
		for(int b, i = 0; i < n; i++)
			cin >> b, wb[b] = i;
		for(int i = 0; i < n; i++)
			cin >> dfs[i];
		gao(0, n);
		for(int i = 1; i <= n; i++){
			cout << i << ':';
			for(const auto& j : ans[i])
				cout << ' ' << j;
			cout << '\n';
		}
	}

	return 0;
}

A Dicey Problem

UVA - 810

题意：把一个頭子放在起点，问你他能否滚回来，能的话输出路径，否则输出无方案， 一个頭子能滚到一个格子当且仅当他的头顶（是头顶！）和那个格子的数一样或者格子上显示的-1

题意：读好条件， 直接模拟， 这里用链表存了下路径，直接存也行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct MenPool{
	vector<T*> v;
	T* newmem(){
		v.emplace_back(new T());
		return v.back();
	}
	void disaper(){
		for(const auto& i : v)
			delete i;
		v.clear();
	}
	~MenPool(){
		disaper();
	}
};

const int Ma = 11;
int mz[Ma][Ma];
unordered_set<string> stu;
typedef pair<int, int> pa;
#define F first
#define S second

struct Node{
	pa im;
	Node* pre;
	Node(){}
	Node(pa _i, Node* _p) : 
	im(_i), pre(_p) {}
};

MenPool<Node> pool;

int n, m, sr, sc;

int cz[] = {0, 0, 1, 0, -1, 2},
	rz[] = {0, 1, 0, -1, 0, 2};

int dm[] = {6, 5, 4, 3, 2, 1};

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

int wdm(int x){
	return dm[x - 1];
}

int py(int x, int y){
	return fr[x - 1][y - 1];
}

struct Tou{
	int tz[6], r, c;
	Node* pre;
	Tou(int h = 1, int f = 2, int _r = 0, int _c = 0, Node* _p = nullptr) : 
		r(_r), c(_c) {
		pre = pool.newmem();
		pre->im = pa(r + 1, c + 1);
		pre->pre = _p;
		tz[5] = h, tz[0] = wdm(h);
		tz[1] = f, tz[3] = wdm(f);
		int t = py(h, f);
		tz[2] = t, tz[4] = wdm(t);
	}
	Tou(Tou& b, int fx){
		if(fx == 0)*this = b;
		if(fx == 1)*this = Tou(b.tz[3], b.tz[5], b.r + 1, b.c, b.pre);
		if(fx == 2)*this = Tou(b.tz[4], b.tz[1], b.r, b.c + 1, b.pre);
		if(fx == 3)*this = Tou(b.tz[1], b.tz[0], b.r - 1, b.c, b.pre);
		if(fx == 4)*this = Tou(b.tz[2], b.tz[1], b.r, b.c - 1, b.pre);
	}
	bool over(){
		return r == sr && c == sc;
	}
	int top(){
		return tz[5];
	}
};

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

string encode(const Tou& t){
	string temp;
	for(int i = 0; i < 6; i++)
		temp += t.tz[i];
	temp += t.r;
	temp += t.c;
	return temp;
}

bool CVis(string s){
	if(stu.count(s))return false;
	else stu.emplace(s);
	return true;
}

void bfs(Tou& tt){
	queue<Tou> q;
	Tou temp = tt;
	q.emplace(tt);
	
	while(!q.empty()){
		temp = q.front();
		//cout << temp.r << ' ' << temp.c << endl;
		if(temp.over() && temp.pre->pre)break;
		q.pop();
		for(int i = 1; i <= 4; i++){
			//cout << "in " << i << " turn\n";
			if(judge(temp.r + rz[i], temp.c + cz[i])){
				Tou tt = Tou(temp, i);
				//cout << "temp = " << temp.top() << ' ' << mz[tt.r][tt.c] << endl;
				if((mz[tt.r][tt.c] == -1 || temp.top() == mz[tt.r][tt.c]) && CVis(encode(tt))){
					q.emplace(tt);
				}
			}
		}
	}
	if(q.empty())cout << "  No Solution Possible\n";
	else {
		vector<pa>ans;
		Node* txx = temp.pre;
		ans.emplace_back(txx->im);
		while(txx){
			//cout << temp.pfx << endl;
			txx = txx->pre;
			if(txx)ans.emplace_back(txx->im);
		}
		int len = ans.size();
		for(int i = len - 1; i >= 0; i--){
			if((len - i - 1) % 9 == 0)cout << "  ";
			cout << '(' << ans[i].F << ',' << ans[i].S << ')' << ",\n"[i == 0];
			if(i && (len - i) % 9 == 0)cout << "\n";
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string name;
	while(cin >> name && name != "END"){
		cout << name << '\n';
		stu.clear();
		pool.disaper();
		int he, fa;
		cin >> n >> m >> sr >> sc >> he >> fa;
		sr--, sc--;
		Tou me(he, fa, sr, sc, nullptr);
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				cin >> mz[i][j];
		bfs(me);
	}

	return 0;
}

Spreadsheet Calculator

UVA - 215

题意：给你一个n×m的excel表格，让你计算出每个格子的值，如果计算不出来(公式调用了未定义的值)， 则只需输出所有无法计算的公式格子

题解：直接模拟， 注意递归判值，如果调用了一个正在计算过程中的格子，则无法计算, 照常，注意输出和最后一个样列后面也得有空行，这次题面提出来了

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

const int inf = 0x3f3f3f3f;
int n, m;

struct Cell{
	int ex;
	int val;
	string expre;
	Cell(){}
	Cell(string temp) : expre(temp), val(0), ex(0){}
};

Cell cell[21][11];
int vul[21][11];

int cacu(int r, int c){
	if(cell[r][c].ex == 1)return cell[r][c].val;
	if(cell[r][c].ex == -1)return inf;
	cell[r][c].ex = -1;
	Cell &now = cell[r][c];
	string& exp = now.expre;
	int sign = 1, len = exp.length();
	for(int i = 0; i < len; i++){
		if(exp[i] == '-')sign = -1;
		else if(exp[i] == '+')sign = 1;
		else if(isdigit(exp[i])){
			string::size_type sz;
			now.val += sign * stoi(exp.substr(i), &sz);
			i += sz - 1;
		}else if(isupper(exp[i])){
			int an = cacu(exp[i] - 'A', exp[i + 1] - '0');
			if(an == inf)return inf;
			now.val += sign * an;
			i++;
		}else assert(false);
	}
	cell[r][c].ex = 1;
	return cell[r][c].val;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while(cin >> n >> m && n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				string temp;
				cin >> temp;
				cell[i][j] = Cell(temp);
			}
		}
		bool flag = true;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				vul[i][j] = cacu(i, j);
				if(cell[i][j].ex == 1)continue;
				flag = false;
				cout << char(i + 'A') << char(j + '0') << ": " << cell[i][j].expre << '\n';
			}
		}

		if(flag){
			cout << ' ';
			for(int i = 0; i < m; i++)
				cout << "     " << i;
			cout << '\n';
			for(int i = 0; i < n; i++){
				cout << char(i + 'A');
				for(int j = 0; j < m; j++){
					cout << setw(6) << vul[i][j];
				}
				cout << '\n';
			}
		}
		cout << '\n';
	}

	return 0;
}

Inspector's Dilemma

UVA - 12118

题意： 给你有v个点的完全图， 和e条必须经过的边，和每条边长多少。起点和终点随意， 问你走完这e条边的花费是多少

题解： 这e条边一定会形成m个联通块，要走完这些边，必定要经历所有的联通图， 所以这些块间都得加上一条边。 对每个联通块来说， 最优就是每条边都得走一次， 那么就是一个欧拉道路或回路， 如果不是， 那么我们通过加边来使这个块变成欧拉道路。 那么，我们只需要找出m个联通块， 然后 ， 在每个联通块里看他是不是欧拉道路或回路， 如果不是，那么我们加一条边， 就能消除两个奇点。

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

typedef pair<int, int> pa;
#define F first
#define S second

const int Ma = 1e3 + 100;
std::vector<int> g[Ma];
bool vis[Ma];

void dfs(int d, int& n){
	vis[d] = true;
	n += (g[d].size() & 1);
	for(const auto& i : g[d]) if(!vis[i])
		dfs(i, n);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, e, t, k = 0;
	while(cin >> n >> e >> t && n){
		for(int i = 0; i < n; i++)
			g[i].clear(), vis[i] = false;
		cout << "Case " << ++k << ": ";
		for(int u, v, i = 0; i < e; i++){
			cin >> u >> v;
			u--, v--;
			g[u].emplace_back(v), g[v].emplace_back(u);
		}
		int ans  = 0, cnt = 0;
		for(int i = 0; i < n; i++) if(!vis[i] && !g[i].empty()){
			int num = 0;
			dfs(i, num);
			if(num > 2)ans += (num - 2) / 2;
			cnt++;
		}
		cout << (ans + max(cnt - 1, 0) + e) * t << '\n';
	}

	return 0;
}

😆第六章！完了！暴力！我要学暴力！

Comments

⬆︎TOP