算法竞赛入门经典第五章例题(12/12)

因为此章主讲stl用法，所以会多用stl

Where is the Marble?

UVA-10474

题意：给你n个大理石，有m个询问，问你写着x的大理石存不存在，如果存在，输出其编号，反之输出not found

题解：直接做，

stl：sort, lower_bound

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
/*************************************************************************
    > File Name: a.cpp
    > Author: ghost_lzw
    > Mail: lanzongwei@gmail.com 
    > Created Time: Fri May 17 21:34:12 2019
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n, q, tot = 0;
	while(~scanf("%d%d", &n, &q) && n){
		int bone[10100];
		for(int i = 0; i < n; i++)
			scanf("%d", bone + i);
		sort(bone, bone + n);
		printf("CASE# %d:\n", ++tot);
		while(q--){
			int s, t;
			scanf("%d", &s);
			t = lower_bound(bone, bone + n, s) - bone;
			if(t == n || bone[t] != s)printf("%d not found\n", s);
			else printf("%d found at %d\n", s, t + 1);
		}
	}
	
	return 0;
}

The Blocks Problem

UVA - 101

题意：有n块木块，你要完成数条命令，move的onto把a和b上方的木块归位，把a放在b上,over把a上方归位，把a放在b堆上，pile的是不对a上面进行操作，onto和over对b来说都一样

题解：注意要忽略那些a， b都在同一个堆里面的命令，，，因为这个wa到怀疑人生，，

stl：vector

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
/*********************************************************
Flie Name: 101.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月05日 星期五 10时29分52秒
*********************************************************/
#include<bits/stdc++.h>
//#define Bug
using namespace std;

const int Ma = 26;
vector<int>num[Ma];
int N;

inline void init(int n){
	for(int i = 0; i < n; i++)
		num[i].clear(), num[i].emplace_back(i);
}

void mv(int w, int _w){
	int le = num[w].size();
	int q = _w + 1;
	for(int i = _w + 1; i < le; i++)
		num[num[w][q]].emplace_back(num[w][q]), num[w].erase(num[w].begin() + q);
}

pair<int, int> find(int q){
	for(int i = 0; i < N; i++)
		if(num[i].size() > 0){
			for(int j = 0; j < num[i].size(); j++)
				if(num[i][j] == q)return make_pair(i, j);
		}
}

void pile(int a, int b, string aim, bool op){
	pair<int, int> _a = find(a), _b = find(b);
	if(a == b || _a.first == _b.first)return;
	if(aim == "onto")mv(_b.first, _b.second);
	if(op)mv(_a.first, _a.second);
	num[_b.first].insert(num[_b.first].end(), num[_a.first].begin() + _a.second, num[_a.first].end());
	num[_a.first].erase(num[_a.first].begin() + _a.second, num[_a.first].end());
}

ostream& operator << (ostream &out, const vector<int>v){
	for(int i = 0; i < v.size(); i++)
		out << ' ' << v[i];
	return out;
}

void check(){
	for(int i = 0; i < N; i++)
		cout << i << ':' << num[i] << '\n';
}

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	while(cin >> N){
		init(N);
		string com, aim;
		do{
			getline(cin, com);
			istringstream it(com);
			string tt;
			it >> aim;
			int a, b;
			it >> a >> tt >> b;
			if(aim == "move")pile(a, b, tt, true);
			else if(aim == "pile")pile(a, b, tt, false);
			#ifdef Bug
			check();
			cout << "--------\n";
			#endif
		}while(aim != "quit");
		check();
		//cout << "quit" << endl;
	}

    return 0;
}

Andy's First Dictionary

UVA-10815

题意：给你一个段文字，让你构造字典，然后按字典序输出所有单词

题解：set存，并输出

stl: set

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
/*********************************************************
Flie Name: 10815.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月05日 星期五 16时32分18秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

int main(){
	set<string>s;
	string tem;
	while(cin >> tem){
		int le = tem.length();
		for(int i = 0; i < le; i++)
			tem[i] = isalpha(tem[i]) ? tolower(tem[i]) : ' ';
		istringstream it(tem);
		while(it >> tem)
			s.insert(tem);
	}
	set<string>::iterator it = s.begin();
	for(; it != s.end(); it++)
		cout << *it << endl;

    return 0;
}

Ananagrams

UVA-156

题意：给你一段文字，让你找出不能通过字母重排得到文中另外的单词

题解：将单词标准化存入map计数，为一的计入答案

stl：map

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: 156.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月05日 星期五 17时32分02秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

map<string, int>m;
vector<string>v;

string cal(string a){
	int le = a.length();
	for(int i = 0; i < le; i++)
		a[i] = tolower(a[i]);
	sort(a.begin(), a.end());
	return a;
}

int main(){
	string a;
	while(cin >> a && a != "#")
		m[cal(a)]++, v.emplace_back(a);
	vector<string>ans;
	for(auto i : v)
		if(m[cal(i)] == 1)ans.emplace_back(i);
	sort(ans.begin(), ans.end());
	for(auto i : ans)
		cout << i << '\n';
    
    return 0;
}

The SetStack Computer

UVA-12096

题意：有一个空栈，你要完成以下操作： PHSH：将空集合压入栈 DUP： 将pop栈顶，然后复制后压入两个相同集合 UNION：pop两个集合，求并集再压入 INTESECT：pop两个集合，求交集再压入 ADD：pop两个集合，将第一个加入第二个后压入

题解：考虑给集合分配一个id，便可用set来表示集合， 方便模拟解决，接着利用stl的set_union和set_intersection可方便求解

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: 12096.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月05日 星期五 17时54分25秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

typedef set<int> Set;
map<Set, int>M;
vector<Set>S;

#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x.begin())

int ID(Set s){
	if(M.count(s))return M[s];
	S.push_back(s);
	return M[s] = S.size() - 1;
}

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n;
	cin >> n;
	while(n--){
		int N;
		cin >> N;
		stack<int>s;
		while(N--){
			string com;
			cin >> com;
			switch(com[0]){
				case 'P': s.push(ID(Set()));
							 break;
				case 'D': s.push(s.top());
							break;
				default :
							Set x1 = S[s.top()]; s.pop();
							Set x2 = S[s.top()]; s.pop();
							Set x;
							if(com[0] == 'U')set_union(ALL(x1), ALL(x2), INS(x));
							if(com[0] == 'I')set_intersection(ALL(x1), ALL(x2), INS(x));
							if(com[0] == 'A') {
								x = x2;
								x.insert(ID(x1));
							}
							s.push(ID(x));
							break;
			}
			cout << S[s.top()].size() << '\n';
		}
		cout << "***" << '\n';
	}
    
    return 0;
}

Team Queue

UVA-540

题意：给你t个团队，来排队列，新进来一个人，如果队里面有他的队友，那么就会插到他队友身后，如果没有队友，他就会去队伍末尾，吸纳在让你完成让人经队和队首退队的操作

题解：利用队列来管理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
/*********************************************************
Flie Name: 540.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月08日 星期一 18时52分23秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

const int Ma = 1010;

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n;
	int ca = 0;
	while(cin >> n, n){
		cout << "Scenario #" << ++ca << '\n';
		map<int, int>M;
		for(int i = 0; i < n; i++){
			int aim;
			cin >> aim;
			while(aim--){
				int t;
				cin >> t;
				M[t] = i;
			}
		}
		string com;
		queue<int>q, q2[Ma];
		while(cin >> com && com[0] != 'S'){
			if(com[0] == 'E'){
				int t;
				cin >> t;
				if(q2[M[t]].empty())q.push(M[t]);
				q2[M[t]].push(t);
			}else {
				cout << q2[q.front()].front() << '\n';
				q2[q.front()].pop();
				if(q2[q.front()].empty())q.pop();
			}
		}
		cout << '\n';
	}

    return 0;
}

Ugly Numbers

UVA-136

题意：输出第1500个丑数

题解：用优先队列维护数，然后对每个数乘2， 3， 5进入队列，当轮到到第1500个时输出即可

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
/*********************************************************
Flie Name: 136.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月08日 星期一 19时20分06秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
	priority_queue<ll, vector<ll>, greater<ll> > pq;
	set<ll>s;
	ll a[] = {2, 3, 5};
	pq.push(1);
	s.insert(1);
	for(int i = 1; ; i++){
		ll x = pq.top(); pq.pop();
		if(i == 1500){
			cout << "The 1500'th ugly number is " << x << ".\n";
			break;
		}
		for(int j = 0; j < 3; j++)
			if(!s.count(x * a[j]))s.insert(x * a[j]), pq.push(x * a[j]);
	}
    
    return 0;
}

Unix ls

UVA-400

题意：给你一堆文件名，让你字典序排序后按列优先输出，假设最长字符有M个字符，那么最右列有M个字符，其他都为M+2个字符，用最少的行数（用过unix或者liunx的都明白吧）

题解：假设把最长的那个字符串拿出来，那么列就全为M+2的长度，就能算出列的数量，加上最长那个，再算出行数，也加上最长的那个，在按这个行数列数输出答案

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
/*********************************************************
Flie Name: 400.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月09日 星期二 15时48分08秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

const int maxcol = 60;
string fl[110];

void print(const string& tem, int len, char aim){
	cout << tem;
	for(int i = tem.length(); i < len; i++)
		cout << aim;
}

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n;
	while(cin >> n){
		print("", 60, '-');
		cout << '\n';
		int ma = 0;
		for(int i = 0; i < n; i++){
			cin >> fl[i];
			ma = max(int(fl[i].length()), ma);
		}
		int col = (maxcol - ma) / (ma + 2) + 1, row = (n - 1) / col + 1;
		sort(fl, fl + n);
		for(int i = 0; i < row; i++){
			for(int j = 0; j < col; j++){
				if(j * row + i < n)print(fl[j * row + i], j == col - 1 ? ma : ma + 2, ' ');
			}
			cout << '\n';
		}
	}
    
    return 0;
}

Database

UVA-1592

题意：给你n行m个数据，只有当任意两行两列的的数据不相同才是yes，否则就算no，并输出是哪两行两列

题解： 枚举任意列组合，得到的值存在map，当遇到相同的则就算当前行列，和map中存的之前行； 运用给字符串id的技巧达到优化目的

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
/*************************************************************************
    > File Name: 1592.cpp
    > Author: ghost_lzw
    > Mail: lanzongwei@gmail.com 
    > Created Time: Wed Jul 10 16:23:27 2019
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;

map<string, int>s;
map<pair<int, int>, int>M;
int ze[10010][12];

int cal(string& tem){
	if(!s.count(tem))s[tem] = s.size();
	return s[tem];
}

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n, m;
	while(cin >> n >> m){
		s.clear();
		cin.ignore();
		bool can = true;
		for(int i = 0; i < n; i++){
			string aim;
			getline(cin, aim);
			for(int now = 0, j = 0; j < m; j++){
				int t = aim.find(",", now);
				if(t == string::npos)t = aim.length();
				string tem = aim.substr(now, t - now);
				ze[i][j] = cal(tem);
				now = t + 1;
			}
		}
		for(int i = 0; i < m && can; i++){
			for(int j = i + 1; j < m && can; j++){
				M.clear();
				for(int k = 0; k < n && can; k++){
					if(M.count(make_pair(ze[k][i], ze[k][j]))){
						can = false;
						cout << "NO\n";
						cout << M[make_pair(ze[k][i], ze[k][j])] + 1 << ' ' << k + 1 << '\n';
						cout << i + 1 << ' ' << j + 1 << '\n';
					}
					else M[make_pair(ze[k][i], ze[k][j])] = k;
				}
			}
		}
		if(can)cout << "YES\n";
	}
	
	return 0;
}

PGA Tour Prize Money

UVA - 207

题意：一对人打高尔夫球，给出排名对应的奖金比例和总奖金，和每个人及其得分，犯规的统统不计入奖金，会先打前36杆决出前70强，打下36杆，一旦犯规直接退出比赛

题解：直接模拟，注意细节， 1.并列时得加T，并且是在都有奖金的情况下，打星队伍也没有奖金，

2.前36杆最后分数并列的人加起来超过70后全都会晋级

3.pdf上的是错的，不能直接复制

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
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
/*********************************************************
Flie Name: 207.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月11日 星期四 12时05分13秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

const int Ma = 100, inf = 0x3f3f3f3f;
double pr[Ma];

struct Play{
    char name[25];
    char rank[15];
    int s[4] = {-1, -1, -1, -1}, tot;
    double qi = -1;
    int cal(int n){
        return accumulate(s, s + n, 0);
    }
    int xi = 2;
    bool xin(){
        if(xi == 2){
            xi = (strchr(name, '*') ? 0 : 1 );
            return xi;
        }
        return xi;
    }
    int look(){
        for(int i = 0; i < 4; i++)
            if(s[i] >= inf)return i;
        return 3;
    }
    void init(){
        for(int i = 0; i < 4; i++)
            s[i] = -1;
        qi = -1;
        xi = 2;
    }
}py[150];

bool cop(Play a, Play b){
    if(a.cal(2) < inf && b.cal(2) < inf)return a.cal(2) < b.cal(2);
    return a.look() > b.look();
}

bool cmp(Play a, Play b){
    if(a.look() != b.look())return a.look() > b.look();
    if(a.tot != b.tot)return a.tot < b.tot;
    return strcmp(a.name, b.name) < 0;
}

void solve(int n){
    int k = 0, rk = 0, rrk = 0;
    while(k < n){
        if(py[k].tot >= inf)break;
        int cnt = 0, kk = k, krk = rk + 1;
        double all = 0;
        while(py[kk].tot < inf && py[k].tot == py[kk].tot){
            if(py[kk].xin())all += pr[rrk + cnt++];
            ++rk, ++kk;
        }
        all /= cnt;
        for(int i = k; i < kk; i++){
            sprintf(py[i].rank, "%d%c", krk, (cnt > 1 && py[i].xin() && rrk <= 69 ? 'T' : ' '));
            if(py[i].xin())py[i].qi = all;
            if(rrk > 69)py[i].qi = -1;
        }
        k = kk;
        rrk += cnt;
    }
}

void print(int i){
    printf("%-21s", py[i].name);
    if(py[i].tot < inf)printf("%-10s", py[i].rank);
    else printf("          ");
    for(int j = 0; j < 4; j++){
        if(py[i].s[j] >= 0 && py[i].s[j] < inf)printf("%-5d", py[i].s[j]);
        else printf("     ");
    }
    if(py[i].tot < inf)printf(py[i].qi >= 0 ? "%-10d" : "%d", py[i].tot);
    else printf("DQ");
    if(py[i].qi >= 0)printf("$%9.2f\n", py[i].qi);
    else puts("");
}

void outp(int n){
    solve(n);
    for(int i = 0; i < n; i++){
        print(i);
    }
}

int main(){
    int T;
    cin >> T;
    while(T--){
        double mon;
        cin >> mon;
        for(int i = 0; i < 70; i++){
            cin >> pr[i];
            pr[i] = pr[i] / 100.0 * mon;
        }
        int n;
        cin >> n;
        cin.ignore();
        for(int i = 0; i < n; i++){
            py[i].init();
            fgets(py[i].name, 20, stdin);
            string tem;
            for(int j = 0; j < 4; j++){
                if(!scanf("%d", &py[i].s[j])){
                    py[i].s[j] = inf + 10 +  (4 - j);
                    break;
                }
            }
            char tcc[50];
            fgets(tcc, 40, stdin);
        }
        sort(py, py + n, cop);
        int now = 0;
        for(int i = 0; i < 70 && now < min(n, 70); i++){
            if(py[now].cal(2) >= inf)break;
            py[now].tot = py[now].cal(4);
            while(now + 1 < n && py[now].cal(2) == py[now + 1].cal(2))++now, py[now].tot = py[now].cal(4);
            ++now;
        }
        sort(py, py + now, cmp);
        puts("Player Name          Place     RD1  RD2  RD3  RD4  TOTAL     Money Won");
        puts("-----------------------------------------------------------------------");
        outp(now);
        if(T)puts("");
    }

    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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define gets(s) fgets(s, sizeof(s), stdin)

const int n_tre = 70;
double pr[n_tre + 10];

struct Play{
    int rd[4];
    int rnd;
    char name[25];
    bool ama;//业余
    bool dq;//失格
    int r36, r72;
}py[150];

bool cmpp(const Play& a, const Play& b){
    if(a.r36 < 0 && b.r36 < 0)return false;
    if(a.r36 < 0)return false;
    if(b.r36 < 0)return true;
    return a.r36 < b.r36;
}

bool cmp2(const Play& a, const Play& b){
    if(a.dq && b.dq){
        if(a.rnd != b.rnd)return b.rnd < a.rnd;
        if(a.r72 != b.r72)return a.r72 < b.r72;
        return strcmp(a.name, b.name) < 0;
    }
    if(a.dq)return  false;
    if(b.dq)return  true;
    if(a.r72 != b.r72)return a.r72 < b.r72;
    return strcmp(a.name, b.name) < 0;
}

void print_result(int &n, double &mon){
    puts("Player Name          Place     RD1  RD2  RD3  RD4  TOTAL     Money Won");
    puts("-----------------------------------------------------------------------");
    int i = 0, pos = 0;
    while(i < n){
        if(py[i].dq){
            printf("%s           ", py[i].name);
            REP(j, py[i].rnd) printf("%-5d", py[i].rd[j]);
            REP(j, 4 - py[i].rnd) printf("     ");
            printf("DQ\n");
            i++;
            continue;
        }
        int j = i;
        int m = 0;
        bool money = false;
        double tot = 0.0;
        while(j < n && py[i].r72 == py[j].r72){
            if(!py[j].ama){
                m++;
                if(pos < n_tre){
                    money = true;
                    tot += pr[pos++];
                }
            }
            j++;
        }

        int rnak = i + 1;
        double amount = mon * tot / m;
        while(i < j){
            printf("%s ", py[i].name);
            char t[5];
            sprintf(t, "%d%c", rnak, m > 1 && money && !py[i].ama ? 'T' : ' ');
            printf("%-10s", t);
            REP(k, 4) printf("%-5d", py[i].rd[k]);

            if(!py[i].ama && money){
                printf("%-10d", py[i].r72);
                printf("$%9.2f\n", amount / 100.0);
            } else{
                printf("%d\n", py[i].r72);
            }
            i++;
        }
    }
}

int main() {
    char s[40];
    int T;
    gets(s);
    sscanf(s, "%d", &T);
    while(T--){
        gets(s);
        gets(s);
        double mon;
        sscanf(s, "%lf", &mon);
        REP(i, n_tre){
            gets(s);
            sscanf(s, "%lf", &pr[i]);
        }
        int n;
        gets(s);
        sscanf(s, "%d", &n);
        assert(n <= 144);
        REP(i, n){
            gets(s);
            strncpy(py[i].name, s, 20);
            py[i].name[20] = 0;
            py[i].ama = false;
            if(strchr(py[i].name, '*'))py[i].ama = true;

            py[i].dq = false; py[i].r36 = py[i].r72 = 0;
            REP(j, 4){
                char  t[5];
                REP(k, 3)t[k] = s[k + 3 * j + 20];
                t[3] = '\0';
                if(!sscanf(t, "%d", &py[i].rd[j])) {
                    py[i].dq = true;
                    py[i].rnd = j;
                    if(j < 2)py[i].r36 = -1;
                    break;
                }else{
                    py[i].r72 += py[i].rd[j];
                    if(j < 2) py[i].r36 += py[i].rd[j];
                }
            }
        }
        sort(py, py + n, cmpp);
        assert(py[n_tre - 1].r36 >= 0);
        for(int i = n_tre - 1; i < n; i++)
            if(i == n - 1 || py[i].r36 != py[i + 1].r36){
                n = i + 1;
                break;
            }
        sort(py, py + n, cmp2);

        print_result(n, mon);

        if(T)putchar('\n');
    }
    return 0;
}

The Letter Carrier's Rounds

UVA-814

题意：模拟邮箱传输，给出MTA列表，和发送人，发送地址，内容，让你按发送格式输出，并输出相应返回值，如果没有合法收件人则不输出内容

题解：直接模拟，注意输出细节,打错单词wa了

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;

void seprate(string &s, string &mt, string &user){
    int t = s.find("@");
    user = s.substr(0, t);
    mt = s.substr(t + 1);
}

int main(){
    string t, s;
    int n;
    set<string>add;
    while(cin >> s && s != "*"){
        cin >> s >> n;
        while(n--)cin >> t, add.insert(t + "@" + s);
    }

    while(cin >> s && s != "*"){
        vector<string> mta;
        map<string, vector<string> >dest;
        set<string> vis;
        while(cin >> t && t != "*"){
            string mt, user;
            seprate(t, mt, user);
            if(vis.count(t))continue;
            vis.insert(t);
            if(!dest.count(mt))mta.emplace_back(mt), dest[mt] = vector<string>();
            dest[mt].emplace_back(t);
        }
        getchar();
        string data;
        while(getline(cin, t) && t != "*")data += "     " + t + '\n';

        string mta1, user1;
        seprate(s, mta1, user1);
        for(auto temp : mta){
            cout << "Connection between " << mta1 << " and " << temp << '\n';
            cout << "     HELO " << mta1 << '\n';
            cout << "     250\n";
            cout << "     MAIL FROM:<" << s << ">\n";
            cout << "     250\n";
            bool okay = false;
            for(auto tt : dest[temp]){
                cout << "     RCPT TO:<" << tt << ">\n";
                if(add.count(tt))okay = true, cout << "     250\n";
                else cout << "     550\n";
            }
            if(okay){
                cout << "     DATA\n     354\n";
                cout << data;
                cout << "     .\n     250\n";
            }
            cout << "     QUIT\n";
            cout << "     221\n";
        }
    }

    return 0;
}

Urban Elevations

UVA-221

题意：给你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
/*********************************************************
Flie Name: 221.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年07月15日 星期一 14时37分27秒
*********************************************************/
#include<bits/stdc++.h>
using namespace std;

struct City{
	int id;
	double x, y, w, d, h;
	bool operator < (const City b){
		return x < b.x || (x == b.x && y < b.y);
	}
}ct[120];

int n;
double x[240];

bool cover(int i, double mx){
	return ct[i].x <= mx && ct[i].x + ct[i].w >= mx;
}

bool look(int i, double mx){
	if(!cover(i, mx))return false;
	for(int j = 0; j < n; j++)
		if(ct[j].y < ct[i].y && ct[j].h >= ct[i].h && cover(j, mx))return false;
	return true;
}

int main(){
	int k = 0;
	while(~scanf("%d", &n) && n){
		for(int i = 0; i < n; i++){
			scanf("%lf%lf%lf%lf%lf", &ct[i].x, &ct[i].y, &ct[i].w, &ct[i].d, &ct[i].h);
			x[i * 2] = ct[i].x;
			x[i * 2 + 1] = ct[i].x + ct[i].w;
			ct[i].id = i + 1;
		}
		sort(x, x + 2 * n);
		int m = unique(x, x + 2 * n) - x;
		sort(ct, ct + n);
		if(k++)putchar('\n');
		printf("For map #%d, the visible buildings are numbered as follows:\n%d", k, ct[0].id);
		for(int i = 1; i < n; i++)
			for(int j = 0; j < m - 1; j++)
				if(look(i, (x[j + 1] + x[j]) / 2)){
					printf(" %d", ct[i].id);
					break;
				}
		putchar('\n');
	}
    
    return 0;
}

Comments

⬆︎TOP