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

code-style传染计划

Posted by 2012201208 at 2026-04-07 14:13:56
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

struct Record {
    int a, b, c, d;
    int score, kind, cnt, sum;
    // 便利 recordList 获取最完美的
    // 种类多 → 好
    // 种类相同 → 邮票总数少 → 好
    // 还相同 → 最大面值高 → 好
    // 再相同 → tie
    Record() : a(-1), b(-1), c(-1), d(-1) {
        kind = 0;
        score = 0;
        cnt = 0;
        sum = 0;
    }

    Record(int stamps[], int _a) : a(stamps[_a]), b(-1), c(-1), d(-1) {
        kind = 1;
        cnt = 1;
        sum = a;
        int maxValue = a;
        score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
    }

    Record(int stamps[], int _a, int _b) : a(stamps[_a]), b(stamps[_b]), c(-1), d(-1) {
        unordered_set<int> distinctSet;
        distinctSet.insert(_a);
        distinctSet.insert(_b);
        kind = distinctSet.size();
        cnt = 2;
        sum = a + b;
        int maxValue = std::max(a, b);
        score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
    }

    Record(int stamps[], int _a, int _b, int _c) : a(stamps[_a]), b(stamps[_b]), c(stamps[_c]), d(-1) {
        unordered_set<int> distinctSet;
        distinctSet.insert(_a);
        distinctSet.insert(_b);
        distinctSet.insert(_c);
        kind = distinctSet.size();
        cnt = 3;
        sum = a + b + c;
        int maxValue = std::max(std::max(a, b), c);
        score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
    }

    Record(int stamps[], int _a, int _b, int _c, int _d) : a(stamps[_a]), b(stamps[_b]), c(stamps[_c]), d(stamps[_d]) {
        unordered_set<int> distinctSet;
        distinctSet.insert(_a);
        distinctSet.insert(_b);
        distinctSet.insert(_c);
        distinctSet.insert(_d);
        kind = distinctSet.size();
        cnt = 4;
        sum = a + b + c + d;
        int maxValue = std::max(std::max(std::max(a, b), c), d);
        score = kind * 100000000 + (9 - cnt) * 1000000 + maxValue;
    }

    void OutputMarch() {
        printf("%d (%d):", sum, kind);
        if (a >= 0) {
            printf(" %d", a);
        }
        if (b >= 0) {
            printf(" %d", b);
        }
        if (c >= 0) {
            printf(" %d", c);
        }
        if (d >= 0) {
            printf(" %d", d);
        }
        printf("\n");
    }

    void OutputTie() {
        printf("%d (%d): tie\n", sum, kind);
    }
};

struct Resolver {
    int stamps[100];
    int stampsLength;
    vector<Record> recordList;

    Resolver() : recordList(100) {
    }

    bool input() {
        stampsLength = 0;
        while (true) {
            if (scanf("%d", &stamps[stampsLength++])==EOF) {
                return false;
            }
            if (stamps[stampsLength - 1] == 0) {
                break;
            }
        }
        // 入参排序方便裁剪 (注意有一个0)
        sort(stamps, stamps + stampsLength - 1);
        return true;
    }

    void solve(const int need) {
        // 需要最多四个邮票;
        recordList.clear();
        for (int i = 0; i < stampsLength; i++) {
            if (stamps[i] == need) {
                // 入栈,继续,丢掉儿子
                recordList.push_back(Record(stamps, i));
                continue;
            }
            if (stamps[i] > need) {
                // 直接break
                break;
            }
            for (int j = i; j < stampsLength; j++) {
                if (stamps[i] + stamps[j] == need) {
                    // 入栈,继续,丢掉儿子
                    recordList.push_back(Record(stamps, i, j));
                    continue;
                }
                if (stamps[i] + stamps[j] > need) {
                    // 直接break
                    break;
                }
                for (int k = j; k < stampsLength; k++) {
                    if (stamps[i] + stamps[j] + stamps[k] == need) {
                        // 入栈,继续,丢掉儿子
                        recordList.push_back(Record(stamps, i, j, k));
                        continue;
                    }
                    if (stamps[i] + stamps[j] + stamps[k] > need) {
                        // 直接break
                        break;
                    }
                    for (int l = k; l < stampsLength; l++) {
                        if (stamps[i] + stamps[j] + stamps[k] + stamps[l] == need) {
                            // 入栈,继续,丢掉儿子
                            recordList.push_back(Record(stamps, i, j, k, l));
                            continue;
                        }
                        if (stamps[i] + stamps[j] + stamps[k] + stamps[l] > need) {
                            // 直接break
                            break;
                        }
                    }
                }
            }
        }

        // 便利 recordList 获取最完美的
        // 种类多 → 好
        // 种类相同 → 邮票总数少 → 好
        // 还相同 → 最大面值高 → 好
        // 再相同 → tie
        int cnt, firstPos;
        int maxScore = cnt = firstPos = -1;
        for (int i = 0; i < recordList.size(); i++) {
            if (recordList[i].score > maxScore) {
                maxScore = recordList[i].score;
                cnt = 1;
                firstPos = i;
            } else if (recordList[i].score == maxScore) {
                cnt++;
            }
        }
        if (cnt == 1) {
            recordList[firstPos].OutputMarch();
        } else if (cnt > 1) {
            recordList[firstPos].OutputTie();
        } else {
            printf("%d ---- none\n", need);
        }
    }
};

int main() {
    Resolver *resolver = new(Resolver);
    while (resolver->input()) {
        int need;
        while (scanf("%d", &need) != EOF && need != 0) {
            resolver->solve(need);
        }
    }
}

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