例5-1 UVa10474 Where is the Marble?
排序后二分查找即可。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, q, st[10005];
void init(){
for(int i = 0; i < n; ++i)
st[i] = read();
sort(st, st + n);
}
void solve(){
int x;
for(int i = 0; i < q; ++i){
x = read();
int index = lower_bound(st, st + n, x) - st;
if(st[index] == x)
printf("%d found at %d\n", x, index + 1);
else
printf("%d not found\n", x);
}
}
int main(){
for(int T = 1; ; ++T){
n = read(), q = read();
if(!n && !q)break ;
printf("CASE# %d:\n", T);
init();
solve();
}
return 0;
}
例5-5 UVa12096 The SetStack Computer
将集合映射成数，然后进行操作。
非常好的练习STL的题。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
typedef set<int> Set;
map<Set, int> mp;
int n, stack[10005], top, tot;
Set st[2005];
int getID(Set *s){
if(!mp.count(*s)){
mp[*s] = tot, tot++;
return tot - 1;
}
return mp[*s];
}
void push(){
stack[top++] = 0;
}
void dup(){
stack[top] = stack[top - 1];
top++;
}
void _union(){
int xa, xb, id;
xa = stack[--top], xb = stack[--top];
Set ss;
set_union(st[xa].begin(), st[xa].end(), st[xb].begin(), st[xb].end(), inserter(ss, ss.begin()));
id = getID(&ss);
st[id] = ss;
stack[top++] = id;
}
void _inter(){
int xa, xb, id;
xa = stack[--top], xb = stack[--top];
Set ss;
set_intersection(st[xa].begin(), st[xa].end(), st[xb].begin(), st[xb].end(), inserter(ss, ss.begin()));
id = getID(&ss);
st[id] = ss;
stack[top++] = id;
}
void add(){
int xa, xb, id;
xa = stack[--top], xb = stack[--top];
Set ss = st[xb];
ss.insert(xa);
id = getID(&ss);
st[id] = ss;
stack[top++] = id;
}
void init(){
n = read();
top = tot = 1;
mp.clear();
Set s;
mp[s] = 0, st[0] = s;
}
void solve(){
char opr[12];
for(int i = 0; i < n; ++i){
scanf("%s", opr);
if(opr[0] == 'P')push();
if(opr[0] == 'D')dup();
if(opr[0] == 'U')_union();
if(opr[0] == 'I')_inter();
if(opr[0] == 'A')add();
printf("%d\n", st[stack[top - 1]].size());
}
printf("***\n");
}
int main(){
int T = read();
while(T--){
init();
solve();
}
return 0;
}
例5-7 UVa136 Ugly Numbers
用一个堆，每次取出最小的丑数，然后生成新的丑数。
本题在其他地方有多个变种，故不在此贴出代码。
答案：859963392
例5-8 UVa1592 Database
先对每一个字符串进行处理，将字符串映射为数后枚举，然后从上到下扫描每一行，对同一行的两个格子打包成一个pair，然后再对pair进行映射，映射为当前的行号。之后即可判断是否有符合条件的。
和集合栈计算机那道题有异曲同工之妙。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m, tab[10005][11];
char s[110];
map<string, int> mp1;
map<pair<int, int>, int> mp2;
void init(){
mp1.clear();
int tots = 0;
for(int i = 0; i < n; ++i){
fgets(s, 99, stdin);
int len = strlen(s);
for(; isspace(s[len - 1]); --len)
s[len - 1] = '\0';
for(int j = 0, k = 0, l = 0; j < len; j = k, ++l){
while(s[j] != ',' && s[j] != '\0')
++j;
s[j] = '\0';
string ss(s + k);
if(!mp1.count(ss))
tab[i][l] = mp1[ss] = ++tots;
else
tab[i][l] = mp1[ss];
k = j + 1;
}
}
}
void solve(){
int r1, r2, c1, c2;
for(int i = 0; i < m - 1; ++i)
for(int j = i + 1; j < m; ++j){
mp2.clear();
for(int k = 0; k < n; ++k){
pair<int,int> pp(tab[k][i], tab[k][j]);
if(!mp2.count(pp))
mp2[pp] = k + 1;
else{
r1 = mp2[pp], r2 = k + 1,
c1 = i + 1, c2 = j + 1;
goto printans;
}
}
}
printf("YES\n");
return ;
printans:
printf("NO\n%d %d\n%d %d\n", r1, r2, c1, c2);
}
int main(){
while(scanf("%d", &n) == 1){
m = read();
init();
solve();
}
return 0;
}
例5-12 UVa221 Urban Elevations
类似于扫描？
对每一个建筑物左右两端的$x$坐标构成的序列排序去重，然后由于每两个$x$坐标之间的建筑物只会有一段，故使用一个数组保存坐标右边这一段的高度。
然后对建筑物从前往后（即按照$y$坐标升序）判断是否可见即可。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
double eps = 1e-5, xx[2005], zz[2005];
struct City{
double x, y, lx, lz;
int id, vis;
};
struct cmp{
inline bool operator()(const City& c1, const City& c2){
if(c1.y - c2.y < eps && c1.y - c2.y > -eps)return c1.x < c2.x;
return c1.y < c2.y;
}
};
int n, len;
City c[1005];
void init(){
double tmp;
for(int i = 0; i < n; ++i)
scanf("%lf%lf%lf%lf%lf", &c[i].x, &c[i].y, &c[i].lx, &tmp, &c[i].lz),
c[i].id = i + 1, c[i].vis = 0,
xx[i << 1] = c[i].x, xx[i << 1 | 1] = c[i].x + c[i].lx;
sort(c, c + n, cmp());
sort(xx, xx + n + n);
len = unique(xx, xx + n + n) - xx;
fill(zz, zz + len, 0.0);
}
void solve(){
for(int i = 0; i < n; ++i){
int flag = 0, st = lower_bound(xx, xx + len, c[i].x) - xx;
for(int j = st; xx[j] < c[i].x + c[i].lx; ++j)
if(c[i].lz > zz[j])
flag = 1, zz[j] = c[i].lz;
if(flag)
c[i].vis = 1;
}
for(int i = 0; i < n; ++i)
swap(c[i].x, c[i].y);
sort(c, c + n, cmp());
int f = 0;
for(int i = 0; i < n; ++i)
if(c[i].vis){
if(f)printf(" ");
printf("%d", c[i].id);
if(!f)f = 1;
}
printf("\n");
}
int main(){
for(int T = 1; ; ++T){
n = read();
if(!n)break ;
else if(T > 1)printf("\n");
printf("For map #%d, the visible buildings are numbered as follows:\n", T);
init();
solve();
}
return 0;
}
5-2 UVa1594 Ducci Sequence
题目链接
直接模拟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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, d[20], dd[20];
void init(){
n = read();
}
void solve(){
bool ans = 0;
for(int i = 0; i < n; ++i)
d[i] = read();
for(int i = 0; i < 1001; ++i){
int flag = 1;
for(int j = 0; j < n; ++j)
if(d[j]){
flag = 0;
break;
}
if(flag){
ans = 1;
break;
}else {
for(int j = 0; j < n - 1; ++j)
dd[j] = abs(d[j] - d[j + 1]);
dd[n - 1] = abs(d[n - 1] - d[0]);
memcpy(d, dd, sizeof(d));
}
}
printf("%s\n", ans ? "ZERO" : "LOOP");
}
int main(){
int T = read();
while(T--){
init();
solve();
}
return 0;
}
5-3 UVa10935 Throwing cards away I
用队列模拟即可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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, que[505], l, r;
void init(){
for(int i = 0; i < n; ++i)
que[i] = i + 1;
l = 0, r = n;
}
void solve(){
printf("Discarded cards:");
while(r - l > 1){
int a = que[l++];
printf(" %d", a);
if(r - l >= 2)printf(",");
int b = que[l++];
que[r++] = b;
}
printf("\nRemaining card: %d\n", que[l]);
}
int main(){
while(n = read()){
init();
solve();
}
return 0;
}
5-4 UVa10763 Foreign Exchange
用multiset模拟即可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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n;
pair<int, int> p[500005];
multiset<pair<int, int> > s;
void init(){
for(int i = 0; i < n; i++)
p[i].first = read(), p[i].second = read();
}
void solve(){
if(n & 1)printf("NO\n");
else{
for(int i = 0; i < n; ++i){
pair<int, int> pp;
pp.first = p[i].second, pp.second = p[i].first;
if(!s.count(pp))
s.insert(p[i]);
else
s.erase(s.find(pp));
}
if(s.empty())printf("YES\n");
else printf("NO\n");
s.clear();
}
}
int main(){
while(n = read()){
init();
solve();
}
return 0;
}
5-5 UVa10391 Compound Words
用string类提供的各种方法即可。
从每个词开始向下遍历，看看下面的词是不是以自己为前缀。如果不是就停止遍历，如果是那就看以自己为前缀的那个词的后缀是不是一个词（用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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
string s[120005];
bool vis[120005] = {0};
int n;
set<string> ss;
void init(){
n = 0;
while(cin >> s[n])
n++, ss.insert(s[n - 1]);
}
void solve(){
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(s[j].find(s[i]) == 0){
string suff(s[j], s[i].length());
if(ss.count(suff))
vis[j] = 1;
}else break;
}
}
for(int i = 0; i < n; ++i)
if(vis[i])cout << s[i] << endl;
}
int main(){
init();
solve();
return 0;
}
5-6 UVa1595 Symmetry
先判断是否有这么一条竖线可以使得点的左右分布对称，再看是不是完全对称。
方法很多，我采用了一个比较简单的写法。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n;
pair<int, int> p[1005];
void init(){
n = read();
for(int i = 0; i < n; ++i)
p[i].first = read(), p[i].second = read();
sort(p, p + n);
}
void solve(){
int flag = 1, half;
if(n & 1)
half = p[n >> 1].first << 1;
else
half = p[(n >> 1) - 1].first + p[n >> 1].first ;
for(int i = 0; i < (n >> 1); ++i)
if(p[n - i - 1].first + p[i].first != half){
flag = 0;
break;
}
if(flag){
for(int i = (n >> 1); i < n; ++i)
p[i].second = -p[i].second;
sort(p + (n >> 1), p + n);
for(int i = (n >> 1); i < n; ++i)
if(p[i].second + p[n - i - 1].second != 0 && p[i].first * 2 != half){
flag = 0;
break;
}
}
printf("%s\n", flag ? "YES" : "NO");
}
int main(){
int T = read();
while(T--){
init();
solve();
}
return 0;
}
5-7 UVa12100 Printer Queue
用一个队列模拟即可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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int pcnt[11], n, m;
int que[10005][2], l, r;
void init(){
n = read(), m = read();
memset(pcnt, 0, sizeof(pcnt));
for(int i = 0; i < n; ++i)
que[i][1] = i,
pcnt[que[i][0] = read()]++;
l = 0, r = n;
}
void solve(){
int t;
for(t = 1; r > l; t++){
for(; ; ){
int cur = que[l][0], flag = 0;
for(int i = cur + 1; i < 10; ++i)
if(pcnt[i]){
flag = 1;
break;
}
if(flag)
que[r][0] = cur, que[r++][1] = que[l][1], l++;
else
break;
}
if(que[l][1] == m)break;
pcnt[que[l][0]]--, l++;
}
printf("%d\n", t);
}
int main(){
int T = read();
while(T--){
init();
solve();
}
return 0;
}
5-9 UVa1596 Bug Hunt
很神奇的模拟题。
注意细节即可。在bug里找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
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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
char s[1005][85];
int line;
struct Arr{
int size;
map<int, int> mp;
};
Arr arr[130];
int getVal(int id, int st){
if(isalpha(s[id][st + 1])){
int _val = getVal(id, st + 2);
char c = s[id][st + 1];
if(_val < 0 || arr[c].size < 0 || _val >= arr[c].size || !arr[c].mp.count(_val))
return -1;
else
return arr[c].mp[_val];
}else{
int x = 0;
for(st++; s[id][st] != ']'; ++st)
x = x * 10 + s[id][st] - '0';
return x;
}
}
bool getInitalized(int id){
char c = s[id][0];
arr[c].mp.clear();
int val = getVal(id, 1);
if(val < 0)return false;
arr[c].size = val;
//printf("%d\n", val);
return true;
}
void solve(){
for(int i = 0; i < 127; ++i)
arr[i].size = -1;
int ans;
for(ans = 0; ans < line; ++ans){
char *sp = strchr(s[ans], '=');
if(sp != NULL){
int index = getVal(ans, 1);
char c = s[ans][0];
if(index < 0 || arr[c].size < 0 || index >= arr[c].size)
break;
else{
if(isalpha(*(sp + 1))){
char cc = *(sp + 1);
int x = getVal(ans, sp - s[ans] + 2);
if(x < 0 || arr[cc].size < 0 || x >= arr[cc].size || !arr[cc].mp.count(x))
break;
else
arr[c].mp[index] = arr[cc].mp[x];
}else{
int x = 0;
for(int st = sp - s[ans] + 1; isdigit(s[ans][st]); ++st)
x = x * 10 + s[ans][st] - '0';
arr[c].mp[index] = x;
}
}
}else{
if(!getInitalized(ans))
break ;
}
}
printf("%d\n", ans == line ? 0 : (ans + 1));
}
int main(){
for(; ; ){
line = 0;
for(; ; ){
fgets(s[line], 82, stdin);
if(s[line][0] == '.')
break;
line++;
}
if(!line)break;
solve();
}
return 0;
}