洛谷-P1008 三连击（桶排序）

题目背景

本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。

题目描述

将1,2, \cdots ,91,2,⋯,9共99个数分成33组，分别组成33个三位数，且使这33个三位数构成1:2:31:2:3的比例，试求出所有满足条件的33个三位数。

输入格式

木有输入

输出格式

若干行，每行33个数字。按照每行第11个数字升序排列。

输入输出样例

输入 #1

无

输出 #1

192 384 576
* * *
...

* * *
（输出被和谐了）

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstdio>

using namespace std;

vector<int> d(10);

void split(int n)
{
    while (n != 0) {
        ++d[n % 10];
        n /= 10;
    }
}

bool check(int a, int b, int c)
{
    split(a); split(b); split(c);
    for (int i = 1; i <= 9; ++i) {
        if (d[i] != 1) {
            return false;
        }
    }

    return true;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 456; i <= 987; ++i) {
        if (i % 3 == 0) {
            int num1 = i / 3;
            int num2 = num1 * 2;
            if (check(num1, num2, i)) {
                cout << num1 << " " << num2 << " " << i << endl;
            }
            fill(d.begin(), d.end(), 0);
        }
    }

    return 0;
}

逐个枚举肯定不是什么好策略，可以考察最小的各个位上互不相同的数字是456，因为最小的三位互不相同的数是123，它的3倍是369，但是3已经被用过了，所以第一位必须是4，因为1234都被用了，所以后面只能是5和6.最大的三位互不相同的是987，很容易理解。

另外，记得只要每次check，就必须初始化桶。