Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

写了近14K代码终于一次AC了

Posted by miklcct at 2013-06-12 21:25:07 on Problem 3966
#include <cassert>
#include <stdexcept>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Card {
    class Rank {
        friend bool operator<(const Rank &, const Rank &);
        friend bool operator>(const Rank &, const Rank &);
        friend bool operator<=(const Rank &, const Rank &);
        friend bool operator>=(const Rank &, const Rank &);
        friend bool operator==(const Rank &, const Rank &);
        friend bool operator!=(const Rank &, const Rank &);
      public:
        Rank() {}
        Rank(const Rank &rhs) : value(rhs.value) {}
        operator char() const {
            return all_representations[value];
        }
        Rank(char representation) {
            size_t location = all_representations.find(representation);
            if (location == string::npos) {
                throw invalid_argument("Invalid rank");
            }
            value = location;
        }
        explicit Rank(int v) : value(v) {
            if (value >= number_of_distinct_ranks) {
                throw invalid_argument("Invalid rank");
            }
        }
        int get_value() const {
            return value;
        }
        static const int number_of_distinct_ranks;
        Rank &operator++();
        Rank &operator--();
      private:
        int value;
        static const string all_representations;
    } rank;
    enum Suit {club, diamond, heart, spade} suit;
    Card() {}
    Card(const Card &rhs) : rank(rhs.rank), suit(rhs.suit) {}
    Card(const char *representation) : rank(representation[0]) {
        switch (representation[1]) {
          case 'C':
            suit = club;
            break;
          case 'D':
            suit = diamond;
            break;
          case 'H':
            suit = heart;
            break;
          case 'S':
            suit = spade;
            break;
          default:
            throw new invalid_argument("Invalid suit");
        }
    }
};

const string Card::Rank::all_representations("23456789TJQKA");
const int Card::Rank::number_of_distinct_ranks = 13;

bool operator<(const Card::Rank &lhs, const Card::Rank &rhs) {
    return lhs.value < rhs.value;
}

bool operator>(const Card::Rank &lhs, const Card::Rank &rhs) {
    return lhs.value > rhs.value;
}

bool operator<=(const Card::Rank &lhs, const Card::Rank &rhs) {
    return lhs.value <= rhs.value;
}

bool operator>=(const Card::Rank &lhs, const Card::Rank &rhs) {
    return lhs.value >= rhs.value;
}

bool operator==(const Card::Rank &lhs, const Card::Rank &rhs) {
    return lhs.value == rhs.value;
}

bool operator!=(const Card::Rank &lhs, const Card::Rank &rhs) {
    return lhs.value != rhs.value;
}

bool operator==(const Card &lhs, const Card &rhs) {
    return lhs.suit == rhs.suit && lhs.rank == rhs.rank;
}

bool operator!=(const Card &lhs, const Card &rhs) {
    return lhs.suit != rhs.suit || lhs.rank != rhs.rank;
}

bool operator<(const Card &lhs, const Card &rhs) {
    return lhs.rank < rhs.rank;
}

bool operator>(const Card &lhs, const Card &rhs) {
    return lhs.rank > rhs.rank;
}

bool operator<=(const Card &lhs, const Card &rhs) {
    return lhs.rank <= rhs.rank;
}

bool operator>=(const Card &lhs, const Card &rhs) {
    return lhs.rank >= rhs.rank;
}

class Hand {
  public:
    struct Ranking {
        enum Category {high_card, one_pair, two_pairs, three_of_a_kind, straight, flush, full_house, four_of_a_kind, straight_flush} category;
        vector<Card::Rank> tie_breakers;
        Ranking &operator++();
        Ranking &operator--();
        void dump() const {
            cerr << category << ' ';
            for (vector<Card::Rank>::const_iterator p = tie_breakers.begin(); p != tie_breakers.end(); ++p) {
                cerr << *p << ' ';
            }
            cerr << endl;
        }
      private:
        void fill_remaining_tie_breakers(int start, int end);
    };
    static const int number_of_cards = 5;
    template<class Iterator> Hand(Iterator begin) {
        for (int count = 0; count < number_of_cards; ++count) {
            for (int index = 0; index < count; ++index) {
                if (cards[index] == *begin) {
                    throw new invalid_argument("A hand must not contain two cards which are the same.");
                }
            }
            cards[count] = *begin;
            ++begin;
        }
    };
    Ranking calculate_ranking() const;
    int calculate_value() const;
  private:
    Card cards[number_of_cards];
};

bool operator==(const Hand::Ranking &a, const Hand::Ranking &b);
bool operator!=(const Hand::Ranking &a, const Hand::Ranking &b);

int main() {
    Card cards[Hand::number_of_cards];
    for (int count = 0; count < Hand::number_of_cards; ++count) {
        string input;
        cin >> input;
        cards[count] = input.c_str();
    }
    cout << Hand(cards).calculate_value() << '\n';
}

int Hand::calculate_value() const {
    const Ranking ranking = calculate_ranking();
    int ans = 1;
    const Card cards_of_lowest_hand[] = {"3S", "7S", "2C", "4S", "5H"};
    for (Ranking iterator = Hand(cards_of_lowest_hand).calculate_ranking(); iterator != ranking; ++iterator) {
        //iterator.dump();
        ++ans;
    }
    return ans;
}

Hand::Ranking Hand::calculate_ranking() const {
    Ranking answer;
    int rank_counts[Card::Rank::number_of_distinct_ranks] = {};
    bool being_flush = true;
    for (int i = 0; i < number_of_cards; ++i) {
        ++rank_counts[cards[i].rank.get_value()];
        if (cards[i].suit != cards[0].suit) {
            being_flush = false;
        }
    }
    bool being_straight = false;
    for (int i = 0; i + 5 <= Card::Rank::number_of_distinct_ranks; ++i) {
        bool starting_straight = true;
        for (int j = i; j < i + 5; ++j) {
            if (!rank_counts[j]) {
                starting_straight = false;
            }
        }
        if (starting_straight) {
            being_straight = true;
            answer.tie_breakers.push_back(Card::Rank(i + 4));
        }
    }
    // 12345
    if (rank_counts[12]) {
        bool starting_straight = true;
        for (int i = 0; i < 4; ++i) {
            if (!rank_counts[i]) {
                starting_straight = false;
            }
        }
        if (starting_straight) {
            being_straight = true;
            answer.tie_breakers.push_back(Card::Rank(3));
        }
    }
    if (being_straight) {
        answer.category = being_flush ? Ranking::straight_flush : Ranking::straight;
    } else {
        int maximum_number_of_cards_in_a_rank = 0;
        for (int i = 0; i < Card::Rank::number_of_distinct_ranks; ++i) {
            maximum_number_of_cards_in_a_rank = max(maximum_number_of_cards_in_a_rank, rank_counts[i]);
        }
        for (int i = maximum_number_of_cards_in_a_rank; i >= 1; --i) {
            for (int j = Card::Rank::number_of_distinct_ranks - 1; j >= 0; --j) {
                if (rank_counts[j] == i) {
                    answer.tie_breakers.push_back(Card::Rank(j));
                }
            }
        }
        switch (maximum_number_of_cards_in_a_rank) {
          case 4:
            answer.category = Ranking::four_of_a_kind;
            break;
          case 3:
            answer.category = answer.tie_breakers.size() == 2 ? Ranking::full_house : Ranking::three_of_a_kind;
            break;
          case 2:
            answer.category = answer.tie_breakers.size() == 3 ? Ranking::two_pairs : Ranking::one_pair;
            break;
          case 1:
            answer.category = being_flush ? Ranking::flush : Ranking::high_card;
            break;
        }
    }
    return answer;
}

Hand::Ranking &Hand::Ranking::operator++() {
    switch (category) {
      case straight:
      case straight_flush:
        try {
            ++tie_breakers[0];
        } catch (overflow_error &) {
            if (category == straight) {
                category = flush;
                const Card::Rank lowest_ranks_of_a_hand[] = {'7', '5', '4', '3', '2'};
                tie_breakers.assign(&lowest_ranks_of_a_hand[0], &lowest_ranks_of_a_hand[sizeof lowest_ranks_of_a_hand / sizeof lowest_ranks_of_a_hand[0]]);
            } else {
                throw;
            }
        }
        break;
      case four_of_a_kind:
      case full_house:
        try {
            ++tie_breakers[1];
            if (tie_breakers[1] == tie_breakers[0]) ++tie_breakers[1];
        } catch (overflow_error &) {
            try {
                ++tie_breakers[0];
                tie_breakers[1] = '2';
            } catch (overflow_error &) {
                if (category == four_of_a_kind) {
                    category = straight_flush;
                    tie_breakers.assign(1, '5');
                } else {
                    category = four_of_a_kind;
                    tie_breakers[0] = '2';
                    tie_breakers[1] = '3';
                }
            }
        }
        break;
      case three_of_a_kind:
        ++tie_breakers[2];
        if (tie_breakers[2] == tie_breakers[0]) {
            ++tie_breakers[2];
        }
        if (tie_breakers[2] == tie_breakers[1]) {
            try {
                ++tie_breakers[1];
                if (tie_breakers[1] == tie_breakers[0]) ++tie_breakers[1];
                fill_remaining_tie_breakers(2, 3);
            } catch (overflow_error &) {
                try {
                    ++tie_breakers[0];
                } catch (overflow_error &) {
                    category = straight;
                    tie_breakers.assign(1, '5');
                }
                fill_remaining_tie_breakers(1, 3);
            }
        }
        break;
      case two_pairs:
        try {
            ++tie_breakers[2];
            if (tie_breakers[2] == tie_breakers[1]) ++tie_breakers[2];
            if (tie_breakers[2] == tie_breakers[0]) ++tie_breakers[2];
        } catch (overflow_error &) {
            ++tie_breakers[1];
            if (tie_breakers[1] == tie_breakers[0]) {
                try {
                    ++tie_breakers[0];
                    tie_breakers[1] = '2';
                    fill_remaining_tie_breakers(2, 3);
                } catch (overflow_error &) {
                    category = three_of_a_kind;
                    tie_breakers[0] = '2';
                    tie_breakers[1] = '4';
                    tie_breakers[2] = '3';
                }
            } else {
                fill_remaining_tie_breakers(2, 3);
            }
        }
        break;
      case one_pair:
        try {
            int i;
            for (i = 3; i >= 1; --i) {
                ++tie_breakers[i];
                if (tie_breakers[i] == tie_breakers[0]) {
                    ++tie_breakers[i];
                }
                if (i == 1 || tie_breakers[i] != tie_breakers[i - 1]) break;
            }
            fill_remaining_tie_breakers(i + 1, 4);
        } catch (overflow_error &) {
            try {
                ++tie_breakers[0];
                fill_remaining_tie_breakers(1, 4);
            } catch (overflow_error &) {
                category = two_pairs;
                tie_breakers.resize(3);
                tie_breakers[0] = '3';
                tie_breakers[1] = '2';
                tie_breakers[2] = '4';
            }
        }
        break;
      case high_card:
      case flush:
        try {
            int i;
            for (i = 4; i >= 0; --i) {
                ++tie_breakers[i];
                if (i == 0 || tie_breakers[i] != tie_breakers[i - 1]) break;
            }
            fill_remaining_tie_breakers(i + 1, 5);
            // prevent generating snake
            Card sample_cards[number_of_cards];
            for (int i = 0; i < number_of_cards; ++i) {
                sample_cards[i].suit = Card::club;
                sample_cards[i].rank = tie_breakers[i];
            }
            Ranking sample_ranking = Hand(sample_cards).calculate_ranking();
            if (sample_ranking.category == straight_flush) {
                ++*this;
            }
        } catch (overflow_error &) {
            if (category == high_card) {
                category = one_pair;
                tie_breakers.resize(4);
                tie_breakers[0] = '2';
                fill_remaining_tie_breakers(1, 4);
            } else {
                category = full_house;
                tie_breakers.resize(2);
                tie_breakers[0] = '2';
                tie_breakers[1] = '3';
            }
        }
        break;
      default:
        assert(false);
    }
    return *this;
}

bool operator==(const Hand::Ranking &lhs, const Hand::Ranking &rhs) {
    return lhs.category == rhs.category && lhs.tie_breakers == rhs.tie_breakers;
}

bool operator!=(const Hand::Ranking &lhs, const Hand::Ranking &rhs) {
    return lhs.category != rhs.category || lhs.tie_breakers != rhs.tie_breakers;
}

Card::Rank &Card::Rank::operator++() {
    if (value == number_of_distinct_ranks - 1) {
        throw overflow_error("Rank already maximum");
    }
    ++value;
    return *this;
}

void Hand::Ranking::fill_remaining_tie_breakers(int start, int end) {
    if (end > start) {
        tie_breakers[end - 1] = '2';
        for (int i = end - 1; i >= start; --i) {
            for (int j = start - 1; j >= 0; --j) {
                if (tie_breakers[i] == tie_breakers[j]) {
                    ++tie_breakers[i];
                }
            }
            if (i != start) {
                tie_breakers[i - 1] = tie_breakers[i];
                ++tie_breakers[i - 1];
            }
        }
    }
}

注释:
Card即是牌,每张牌有rank同suit,分别属Card::Rank及Card::Suit。
Card::Rank用来代表牌的点数,能自动转换为char(即2、3、4、……、Q、K、A等)及由char转换,亦可用get_value来取得其强度。当中的operator++能直接增加一点,如果超标则抛出异常。
Card::Suit代表花色,只是简单的enum。
Hand即是手牌,有5张牌。calculate_value是求答案的方法,而calculate_ranking则返回一般玩家所使用的牌力描述(例如同花顺A头、85对带3、AJ632花等等)。
Hand::Ranking有operator++,用来找出下一组比这组大的牌,例如23457下一组为23467,75对带A下组是76对带2,同花顺A头下组会抛出异常。所以calculate_value只需先制造最少的Ranking,然后不断++到找到为止。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator