アルゴリズムコンテスト入門経典(第2版)-劉汝佳-第5章C++とSTL例題(9/12)

32763 ワード

アルゴリズム ACM STL ウバアルゴリズムコンテスト入門経典

説明
***また、问题を简単にするために、私はVOJでcontestを开いて、一绪に上ですることを歓迎します:第5章例題contestは直接ある问题を见たいならば、カタログを开いてから相応の问题を开いてください!!
例題
例5-1 UVA 10474大理石はどこにあるか(並べ替えと検索)
考え方この問題は基礎を比較して、ソートはsortで、検索はlowerを使いますboundは、いずれもSTLの標準関数です.注意lower_bound関数の戻り値は、検索数よりも小さくない最初の位置に対応するポインタであり、見つからない場合はa+n(すなわち、関数の2番目のパラメータ)を返す.コード#コード#

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 10000;

int main(void)
{
    int n, q, t = 0;
    int a[N], x;

    while (scanf("%d%d", &n, &q) != EOF && n) {
        for (int i = 0; i < n; i ++)
            scanf("%d", &a[i]);
        sort(a, a+n);
        printf("CASE# %d:
", ++t);
        while (q--) {
            scanf("%d", &x);
            int m = lower_bound(a, a+n, x) - a;
            printf("%d ", x);
            if (m == n || a[m] != x) printf("not found
");
            else printf("found at %d
", m+1);
        }
    }

    return 0;
}

例5-2 UVA 101木塊問題(using std::vector)
構想はこの問題で木の塊の山の長さがずっと変化しているため、頻繁に要素を追加して削除する操作が必要で、vectorを使うのが最も適切です.size()resize()push_のようなvectorの機能関数の使い方を学ぶことに注意してください.back()など.また,この問題の4つの操作のうち具体的な操作は一定の重複があり,合理的な分割操作はコードモジュール化をよりよくすることができる.コード#コード#

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 25;

typedef pair<int, int> P;

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

P find_pile(int a)
{
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < pile[i].size(); j ++) {
            if (pile[i][j] == a) return P(i, j);
        }
    }
    return P(n, n);
}

void clear_above(P p)
{
    int i = p.first, j = p.second;
    for (int k = j+1; k < pile[i].size(); k ++) {
        int a = pile[i][k];
        pile[a].push_back(a);
    }
    pile[i].resize(j+1);
}

void pile_over(P p, int b)
{
    int i = p.first, j = p.second;
    for (int k = j; k < pile[i].size(); k ++) {
        int a = pile[i][k];
        pile[b].push_back(a);
    }
    pile[i].resize(j);
}

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

int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i ++) pile[i].push_back(i);

    string s1, s2;
    int a, b;
    P p1, p2;
    while (cin >> s1 && s1 != "quit") {
        cin >> a >> s2 >> b;
        p1 = find_pile(a);
        p2 = find_pile(b);
        if (p1.first == p2.first) continue;
        if (s1 == "move") clear_above(p1);
        if (s2 == "onto") clear_above(p2);
        pile_over(p1, p2.first);
        //print();
        //printf("===============
");
    }
    print();

    return 0;
}

例5-3 UVA 10815アンディの最初の辞書(using std::set)
考え方この問題に関する知識点は,1,setの使い方(setに重複する値がないことに注意)2,isalpha isdigitなどの関数の使い方3,反復器iteratorの使い方注意学習である.コード#コード#

#include <cstdio>
#include <iostream>
#include <string>
#include <cctype>
#include <set>
using namespace std;

set<string> d;

int main() {
    string s;                                                                          
    char ch;         
    while (getline(cin, s)) {                                                          
        for (int i = 0; i < s.size(); i++) {
            if (!isalpha(s[i]))                                                        
                continue;                
            string tmp;                                                                
            while (i < s.size() && isalpha(s[i]))
                tmp += tolower(s[i++]);                                                
            d.insert(tmp);                       
        }
    }                                                                                  
    for (set<string>::iterator i = d.begin(); i != d.end(); i++)
        cout << *i << endl;                                                            
    return 0;                                                    
}

例5-4 UVA 156反片語(using std::map)
構想私のコードは2つのmapを使って、本の中のルーチンコードは1つのmapと1つのvectorを使ったほうがいいです.コード#コード#

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
using namespace std;

map<string, string> sorted;
map<string, int> num;

int main(void)
{
    string s, s1;
    char ch[21];
    while (cin >> s && s != "#") {
        int n = s.size();
        for (int i = 0; i < s.size(); i ++)
            ch[i] = tolower(s[i]);
        ch[n] = '\0';
        sort(ch, ch+n);
        s1 = ch;
        sorted[s] = s1;
        if (num.find(s1) == num.end()) num[s1] = 1;
        else num[s1] ++;
    }

    set<string> res;
    for (map<string, string>::iterator it = sorted.begin();
        it != sorted.end(); it ++) {
        if (num[it->second] == 1) res.insert(it->first);
    }
    for (set<string>::iterator it = res.begin();
        it != res.end(); it ++) {
        cout << *it << endl;
    }

    return 0;
}

例5-5 UVA 12096集合スタックコンピュータ(using std::stack and other containers)
構想という問題で主に使われているデータ構造はstackですが、最も重要な知識点はstackではありません!本題はマッピングでデータ構造を簡略化する考え方がある:もう一つの比較的複雑なデータ構造をmapでint型idにマッピングすることで、記憶空間を大幅に低減できるだけでなく、検索効率を大幅に向上させることができる.だからこれは第五章の最も重要な問題で、一つもありません!!!後続の練習問題や例題にはこのような考えがいくつか使われており、後で説明します.コード#コード#

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
using namespace std;

typedef set<int> Set;
map<Set, int> IDs;
vector<Set> Sets;

stack<int> st;

int getID(Set s)
{
    if (IDs.count(s)) return IDs[s];
    Sets.push_back(s);
    return IDs[s] = Sets.size()-1;
}

void init()
{
    Set s0;
    getID(s0);
}

void push()
{
    st.push(0);
}

int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        init();
        char op[10];
        Set s1, s2, s3;
        int id;
        while (n--) {
            scanf("%s", op);
            switch(op[0]) {
                case 'P':
                    st.push(0);
                    break;
                case 'D':
                    st.push(st.top());
                    break;
                case 'U':
                    s1 = Sets[st.top()]; st.pop();
                    s2 = Sets[st.top()]; st.pop();
                    for (Set::iterator it = s2.begin(); it != s2.end(); it++)
                      s1.insert(*it);
                    st.push(getID(s1));
                    break;
                case 'I':
                    s1 = Sets[st.top()]; st.pop();
                    s2 = Sets[st.top()]; st.pop();
                    s3.clear();
                    for (Set::iterator it = s2.begin(); it != s2.end(); it++)
                      if (s1.count(*it)) s3.insert(*it);
                    st.push(getID(s3));
                    break;
                case 'A':
                    id = st.top(); st.pop();
                    s2 = Sets[st.top()]; st.pop();
                    s2.insert(id);
                    st.push(getID(s2));
                    break;
                default:
                    break;
            }
            printf("%d
", Sets[st.top()].size());
        }
        printf("***
");
    }

    return 0;
}

例5-6 UVA 540コミュニティキュー(using std::queue and other containers)
構想キューの特徴は先入先出であり,通常キューシステムの問題はキューに用いられる.この問題は2つのキューで解決します.各グループには1つのキュー(要素はグループメンバーID)があり、チーム全体に1つのキュー(要素はグループID)が形成されます.コード#コード#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

const int T = 1000;

int t;
map<int, int> his_team;
queue<int> qt, q[T];

void init_queue()
{
    while (qt.size()) qt.pop();
    for (int i = 0; i < t; i++)
        while (q[i].size()) q[i].pop();
}

int main(void)
{
    int kase = 0, n, m;
    char op[10];
    while (scanf("%d", &t) && t) {
        for (int i = 0; i < t; i++) {
            scanf("%d", &n);
            for (int j = 0; j < n; j++) {
                scanf("%d", &m);
                his_team[m] = i;
            }
        }
        init_queue();

        printf("Scenario #%d
", ++kase);
        while (scanf("%s", op) && strcmp(op, "STOP")) {
            if (op[0] == 'E') {
                scanf("%d", &m);
                int i = his_team[m];
                if (q[i].empty()) qt.push(i);
                q[i].push(m);
            } else {
                int i = qt.front();
                printf("%d
", q[i].front());
                q[i].pop();
                if (q[i].empty()) qt.pop();
            }
        }
        printf("
");
    }

    return 0;
}

例5-7 UVA 136ブス数(using priority_queue)
構想という問題のuvaではずっとsubmit errorだったが、私のプログラムの実行結果は他のブログと比較したことがあり、完全に正しい.この問題はlong longを必ずしも使う必要はありません.求めた結果(1500番目の醜数)はintの表現範囲を超えないからです.しかし、私は結果*5が超えるので、私のプログラムではlong longを使いました.コード#コード#

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL;

int main()
{
    LL a = 0, b = 0;
    priority_queue<LL, vector<LL>, greater<LL> > pq;
    pq.push(1);
    int cnt = 0;
    while (pq.size()) {
        a = pq.top();
        pq.pop();
        if (a != b) {
            cnt++;
            if (cnt == 1500) break;
            pq.push(a*2);
            pq.push(a*3);
            pq.push(a*5);
            b = a;
        }
    }
    printf("%lld
", a);

    return 0;
}

例5-8 UVA 400 Unix isコマンド(ソートと文字列処理)
構想注意この問題は列優先方式で出力することが要求され,これはプログラムの正常な出力の方向とは異なる.そのため、ループ階層を変更する必要があります.具体的にはプログラムを参照してください.また、文字がある限りMまたはM+2文字を補完し、文字がない場合は使用しません.コード#コード#

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100;
const int M = 60;

void print_char(int k, char c)
{
    while (k--) printf("%c", c);
}

int main()
{
    int n, m, col, row;
    string s[N];
    while (~scanf("%d", &n)) {
        m = 0;
        for (int i = 0; i < n; i++) {
          cin >> s[i];
          m = max(m, (int)s[i].size());
        }
        sort(s, s+n);

        col = (M-m)/(m+2) + 1;
        row = n/col + ((n%col) ? 1 : 0);
        print_char(M, '-');
        printf("
");
        for (int j = 0; j < row; j ++) {
            for (int i = 0; i < col; i ++) {
                int k = i*row+j;
                if (i == col-1) {
                    if (k < n) {
                        cout << s[k];
                        print_char(m-s[k].size(), ' ');
                    }
                    printf("
");
                } else {
                    cout << s[k];
                    print_char(m+2-s[k].size(), ' ');
                }
            }
        }
    }

    return 0;
}

例5-9 UVA 1592データベース(uniquely using std::map)
構想の四重循環列挙は必ずタイムアウトし、実際には多くの無駄な比較が存在する.実際には、c 1およびc 2を列挙し、各ローを上から下までスキャンするだけです.新しい行rに出会うたびに,c 1,c 2の2列の内容を1つの二元グループとして1つのmapに格納する.mapのキー値にこの二元群が既に存在する場合、その二元群は要求されるr 1にマッピングされ、現在の行はr 2である.もう一つの詳細な問題は、c 1、c 2の2列からなる2元グループをどのように表すかです.1つの方法は、2つの文字列を直接1つの長い文字列につづり、より高速なのは前処理を行うことです.すべての文字列に番号を割り当てると、データベース全体のセルが整数になり、上記の2つのグループが2つの整数になります.例5-5で紹介したテクニックです.また、やっている間にエピソードがあり、初めてTLEを提出しましたが、プログラムを調べてみると、各グループのデータ計算時にmapを再初期化するのを忘れていました.コード#コード#

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

const int N = 10000;
const int M = 10;

typedef pair<int, int> P;
map<P, int> firstpos;
map<string, int> str2key;
vector<string> key2str;

int ID(string &s)
{
    if (str2key.count(s)) return str2key[s];
    key2str.push_back(s);
    return str2key[s] = key2str.size()-1;
}

int main()
{
    int r, c;
    char ch;
    string tab[N][M];
    while (cin >> r >> c) {
        getchar();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                tab[i][j] = "";
                while ((ch = getchar()) != ',' && ch != '
')
                  tab[i][j] += ch;
            }
        }

        int flag = true;
        for (int j = 0; j < c; j++) {
            for (int k = j+1; k < c; k++) {
                firstpos.clear();
                str2key.clear();
                key2str.clear();
                for (int i = 0; i < r; i++) {
                    P p(ID(tab[i][j]), ID(tab[i][k]));
                    if (firstpos.count(p)) {//find
                        printf("NO
");
                        printf("%d %d
", firstpos[p]+1, i+1);
                        printf("%d %d
", j+1, k+1);
                        flag = false;
                        break;
                    } else
                        firstpos[p] = i;
                }
                if (flag == false) break;
            }
            if (flag == false) break;
        }
        if (flag) printf("YES
");
    }

    return 0;
}

例5-10 UVA 207 PGAツアーの賞金(ランキングとその他の詳細処理)
この問題はまだ試していないので,まず位置を占めている.コード#コード#

 
   5-11 UVA 814           (      STL       ) 
     
       ，     。 
    
   
  
   5-12 UVA 221       (   ) 
     
       ，     。

POJ 1251(最小生成ツリー)

Ridesの紹介とインストール