《算法竞赛入门经典》 第五章：C++与STL入门

发表于 | 分类于

5-2 UVa101 The Blocks Problem

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

const int MAXN = 30;
int n;
vector<int> pile[MAXN];

// 找木块a所在的pile和height，以引用的形式返回调用者
void find_block(int a, int& p, int& h) {
    for (p = 0; p < n; p++) {
        for (h = 0; h < pile[p].size(); h++) {
            if (pile[p][h] == a) {
                return;
            }
        }
    }
}

// 把第p堆高度为h的木块上方的所有木块移回原位
void clear_above(int p, int h) {
    for (int i = h + 1; i < pile[p].size(); i++) {
        int b = pile[p][i];
        pile[b].push_back(b);
    }
    pile[p].resize(h + 1);
}

// 把第p堆高度h及其上方的木块整体移动到p2堆的顶部
void pile_onto(int p, int h, int p2) {
    for (int i = h; i < pile[p].size(); i++) {
        pile[p2].push_back(pile[p][i]);
    }
    pile[p].resize(h);
}

void print() {
    for (int i = 0; i < n; i++) {
        printf("%d:", i);
        for (int j = 0; j < pile[i].size(); j++) {
            printf(" %d", pile[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int a, b;
    cin >> n;
    string s1, s2;
    for (int i = 0; i < n; i++) {
        pile[i].push_back(i);
    }
    while (cin >> s1 >> a >> s2 >> b) {
        int pa, pb, ha, hb;
        find_block(a, pa, ha);
        find_block(b, pb, hb);
        if (pa == pb) {
            continue;
        }
        if (s2 == "onto") {
            clear_above(pb, hb);
        }
        if (s1 == "move") {
            clear_above(pa, ha);
        }
        pile_onto(pa, ha, pb);
    }
    print();

    return 0;
}

5-3 UVa10815 Andy’s First Dictionary

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
#include<iostream>
#include<string>
#include<set>
#include<sstream>
using namespace std;

set<string> dict;
string s, buf;

int main() {
    while (cin >> s) {
        for (int i = 0; i < s.length(); i++) {
            if (isalpha(s[i])) {
                s[i] = tolower(s[i]);
            } else {
                s[i] = ' ';
            }
        }
        stringstream ss(s);
        while (ss >> buf) {
            dict.insert(buf);
        }
    }
    for (set<string>::iterator it = dict.begin(); it != dict.end(); it++) {
        cout << *it << "\n";
    }

    return 0;
}

5-4 UVa156 Ananagrams

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
#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

map<string, int> cnt;
vector<string> words;

string repr(string s) {
    string res = s;
    for (int i = 0; i < res.length(); i++) {
        res[i] = tolower(res[i]);
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int n = 0;
    string s;
    while (cin >> s) {
        if (s[0] == '#') {
            break;
        }
        words.push_back(s);
        string res = repr(s);
        if (!cnt.count(res)) {
            cnt[res] = 0;
        }
        cnt[res]++;
    }
    vector<string> res;
    for (int i = 0; i < words.size(); i++) {
        if (cnt[repr(words[i])] == 1) {
            res.push_back(words[i]);
        }
    }
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << "\n";
    }

    return 0;
}

5-5 UVa12096 The SetStack Computer

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
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;

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

typedef set<int> Set;
map<Set,int> IDcache; // 把集合映射成ID
vector<Set> Setcache; // 根据ID取集合

// 查找给定集合x的ID。如果找不到，分配一个新ID
int ID (Set x) {
  if (IDcache.count(x)) return IDcache[x];
  Setcache.push_back(x); // 添加新集合
  return IDcache[x] = Setcache.size() - 1;
}

int main () {
  int T;
  cin >> T;
  while(T--) {
    stack<int> s; // 题目中的栈
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
      string op;
      cin >> op;
      if (op[0] == 'P') s.push(ID(Set()));
      else if (op[0] == 'D') s.push(s.top());
      else {
        Set x1 = Setcache[s.top()]; s.pop();
        Set x2 = Setcache[s.top()]; s.pop();
        Set x;
        if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));
        if (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));
        if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }
        s.push(ID(x));
      }      
      cout << Setcache[s.top()].size() << endl;
    }
    cout << "***" << endl;
  }
  return 0;  
}

2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

5-6 UVa540 Team 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
#include <cstdio>
#include <map>
#include <queue>
using namespace std;

const int MAXT = 1000 + 10;

int main () {
    int t, kase = 1;
    while (scanf("%d", &t) == 1 && t) {
        printf("Scenario #%d\n", kase++);

        map<int, int> team;
        for (int i = 0; i < t; i++) {
            int n, x;
            scanf("%d", &n);
            while (n--) { scanf("%d", &x); team[x] = i; }
        }

        queue<int> q, q2[MAXT];
        for ( ; ; ) {
            int x;
            char cmd[10];
            scanf("%s", cmd);
            if (cmd[0] == 'S') { break; }
            else if (cmd[0] == 'E') {
                scanf("%d", &x);
                int t = team[x];
                if (q2[t].empty()) q.push(t);
                q2[t].push(x);
            }
            else if (cmd[0] == 'D') {
                int t = q.front();
                printf("%d\n", q2[t].front());
                q2[t].pop();
                if (q2[t].empty()) q.pop();
            }
        }
        printf("\n");
    }

    return 0;
}

5-7 UVa136 Ugly Numbers

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
// UVa136 Ugly Numbers
// Rujia Liu
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
const int coeff[3] = {2, 3, 5};

int main() {
  priority_queue<LL, vector<LL>, greater<LL> > pq;
  set<LL> s;
  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++) {
      LL x2 = x * coeff[j];
      if(!s.count(x2)) { s.insert(x2); pq.push(x2); }
    }
  }
  return 0;
}

   1    2
123412341

5-8 UVa400 Unix ls

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
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int MAXCOL = 60;
const int MAXN = 100 + 5;
string filenames[MAXN];

void print(const string& s, int len, char extra) {
    cout << s;
    for (int i = 0; i < len - s.length(); i++) {
        cout << extra;
    }
}

int main() {
    int n;
    while (cin >> n) {
        int M = 0;
        for (int i = 0; i < n; i++) {
            cin >> filenames[i];
            M = max(M, (int)filenames[i].length());
        }
        // 计算列数cols和行数rows
        int cols = (MAXCOL - M) / (M + 2) + 1;
        // (M+2)(M+2)......M，几个(M+2）加一
        int rows = (n - 1) / cols + 1;
        // 如果clos为3，n为12，那么结果为5，但其实只要4行就可以
        // (n - 1) / cols 避免行列填满的情况导致结果多1
        // +1是为了不够clos的部分也得给他们留一行
        print("", 60, '-');
        cout << "\n";
        sort(filenames, filenames + n);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int idx = c * rows + r;
                // 只能一行一行来，因为每一行需要一个回车
                // 从0行开始，0行0列，0行1列，0行2列，所以一开始r是0
                if (idx < n) print(filenames[idx], c == cols - 1 ? M : M + 2, ' ');
            }
            cout << "\n";
        }
    }

    return 0;
}

5-9 UVa1592 Database

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
// UVa1592 Database
// Rujia Liu
// 本程序只是为了演示STL各种用法，效率较低。实践中一般用C字符串和哈希表来实现。




using namespace std;

typedef pair<int,int> PII;

const int maxr = 10000 + 5;
const int maxc = 10 + 5;

int m, n, db[maxr][maxc], cnt;

map<string, int> id;
int ID(const string& s) {
  if(!id.count(s)) {
    id[s] = ++cnt;
  }
  return id[s];
}

void find() {
  for(int c1 = 0; c1 < m; c1++)
    for(int c2 = c1+1; c2 < m; c2++) {
      map<PII, int> d;
      for(int i = 0; i < n; i++) {
        PII p = make_pair(db[i][c1], db[i][c2]);
        if(d.count(p)) {
          printf("NO\n");
          printf("%d %d\n", d[p]+1, i+1);
          printf("%d %d\n", c1+1, c2+1);
          return;
        }
        d[p] = i;
      }
    }
  printf("YES\n");
}


int main() {
  string s;
  while(getline(cin, s)) {
    stringstream ss(s);
    if(!(ss >> n >> m)) break;
    cnt = 0;
    id.clear();
    for(int i = 0; i < n; i++) {
      getline(cin, s);
      int lastpos = -1;
      for(int j = 0; j < m; j++) {
        int p = s.find(',', lastpos+1);
        if(p == string::npos) p = s.length();
        db[i][j] = ID(s.substr(lastpos+1, p - lastpos - 1));
        lastpos = p;
      }
    }
    find();
  }
  return 0;
}

`c++

#include

#include

#include

#include

#include

#include
using namespace std;

typedef pair<int, int> PII;

const int MAXR = 10000 + 5;
const int MAXC = 10 + 5;

int m, n, db[MAXR][MAXC], cnt;
map<string, int> id;

int ID(const string& s) {
if (!id.count(s)) {
id[s] = ++cnt;
}
return id[s];
}

int main() {

return 0;

}

`10-11 UVa11181 ProbabilityGiven