【题解】 —算法竞赛入门经典第二版 【第五章例题】【9/12】

发表于 | 更新于 | 分类于

UVa 10474 Where is the Marble?【排序】【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
// UVa10474 Where is the Marble?
// Rujia Liu
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 10000;

int main() {
  int n, q, x, a[maxn], kase = 0;
  while(scanf("%d%d", &n, &q) == 2 && n) {
    printf("CASE# %d:\n", ++kase);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a+n); // 排序
    while(q--) {
      scanf("%d", &x);
      int p = lower_bound(a, a+n, x) - a; // 在已排序数组a中寻找x
      if(a[p] == x) printf("%d found at %d\n", x, p+1);
      else printf("%d not found\n", x);
    }
  }
  return 0;
}

UVa 101 The Blocks Problem【模拟】【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
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> pile[30];

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

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 ;
}

void clear_above(int p, int h)
{
    for(int i = h+1; i < pile[p].size(); ++i)
    {
        int tt = pile[p][i];
        pile[tt].push_back(tt);
    }
    pile[p].resize(h+1);
}

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]);
        puts("");
    }
}

int main()
{
    int a, b;
    string s1, s2;
    scanf("%d",&n);
    init();
    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;
}

UVa 10815 Andy’s First Dictionary【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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <sstream>
#include <cctype>
using namespace std;
set<string> dict;  //string集合
int main()
{
    string s, buf;
    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 << endl;
    return 0;
}

UVa 156 Ananagrams【map】【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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;

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

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

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

UVa 12096 The SetStack Computer【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
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

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

int t, n;
char op[10];
vector<set<int> > ccc;
map<set<int>, int> aaa;
int ID(set<int> x)
{
    if(aaa.count(x))
        return aaa[x];
    ccc.push_back(x);
    return aaa[x] = ccc.size() - 1;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        stack<int> s;
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", op);
            if(op[0] == 'P') s.push(ID(set<int>()));
            else if(op[0] == 'D') s.push(s.top());
            else
            {
                set<int> x1 = ccc[s.top()]; s.pop();
                set<int> x2 = ccc[s.top()]; s.pop();
                set<int> 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 << ccc[s.top()].size() << endl;
        }
        puts("***");
    }
    return 0;
}

UVa 540 Team Queue【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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

char com[10];
int t, n, x, tt;
int main()
{
    int cas = 0;
    while(cin >> t && t)
    {
        printf("Scenario #%d\n", ++cas);

        map<int, int> team;
        for(int i = 1; i <= t; ++i)
        {
            cin >> n;
            while(n--)
            {
                cin >> x;
                team[x] = i;
            }
        }

        queue<int> zong, fen[MAX];
        while(cin >> com)
        {
            char op = com[0];
            if(op == 'S') break;
            if(op == 'E')    //入队
            {
                int yy;
                cin >> yy;
                tt = team[yy];
                if(fen[tt].empty()) zong.push(tt);
                fen[tt].push(yy);
            }
            else            //出队
            {
                tt = zong.front(); //整队
                cout << fen[tt].front() << endl;
                fen[tt].pop();
                if(fen[tt].empty()) zong.pop();
            }
        }
        puts("");
    }
    return 0;
}

UVa 136 Ugly Numbers【priority_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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long LL;
const int coeff[3] = {2, 3, 5};
int main()
{
    priority_queue<LL, vector<LL>, greater<LL> > pq; //greater使大数往后排
    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;
}

UVa 400 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
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 105;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int n, mlen;
int maxc = 60;
string s[MAX];

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

int main()
{
    while(~scanf("%d",&n))
    {
        mlen = 0;
        for(int i = 0; i < n; ++i)
        {
            cin >> s[i];
            mlen = max(mlen, (int)s[i].length());
        }
        //计算C和R
        int col = (maxc - mlen) / (mlen + 2) + 1;
        int row = (n - 1) / col + 1;
//        cout << mlen << "--" << col << "--" << row << endl;
        print("", 60, '-');
        puts("");
        //排序
        sort(s, s + n);
//        for(int i = 0; i < n; ++i)
//            cout << s[i] <<endl;
        int idx;
        for(int r = 0; r < row; ++r)
        {
            for(int c = 0; c < col; ++c)
            {
                idx = c * row + r;
                if(idx < n)
                    print(s[idx], c == col - 1 ? mlen: mlen + 2, ' ');
            }
            puts("");
        }
    }
    return 0;
}

UVa 1592 Datebase【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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int n, m, cnt;
int a[MAX][15];
string t, tem, s;
map<string, int> mapa;
int main()
{
END:
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        mapa.clear();
        cnt = 1;
        for(int i = 1; i <= n; ++i)
        {
            int cou = 1;
            getline(cin, t);
            tem = "";
            for(int j = 0; j < t.size(); ++j)
            {
                if(t[j] == ',')
                {
                    if(!mapa.count(tem))
                        mapa[tem] = cnt++;
                    a[i][cou++] = mapa[tem];
//                    cout << tem << "**" << endl;
                    tem = "";
                }
                else
                    tem += t[j];
            }
            if(!mapa.count(tem))
                mapa[tem] = cnt++;
            a[i][cou++] = mapa[tem];
//            cout <<tem << "**" <<endl;
        }

//        for(int i = 1; i <= n; ++i)
//        {
//            for(int j = 1; j <= m; ++j)
//                cout << a[i][j] << " ";
//            puts("");
//        }


        for(int i = 1; i < m; ++i)
        {
            for(int j = i+1; j <= m; ++j)
            {
                map<pair<int, int>, int> app;
                for(int k = 1; k <= n; ++k)
                {
                    if(app[make_pair(a[k][i], a[k][j])])
                    {
                        int r1 = app[make_pair(a[k][i], a[k][j])];
                        int r2 = k;
                        int c1 = i;
                        int c2 = j;
                        puts("NO");
                        printf("%d %d\n", r1, r2);
                        printf("%d %d\n", c1, c2);
                        goto END;
                    }
                    app[make_pair(a[k][i], a[k][j])] = k;
                }
            }
        }
        puts("YES");
    }
    return 0;
}
Donate comment here
0%