[ABC333C] Repunit Trio

yhx0322 · 2023-12-17 07:23:03 · 题解

Description

给出一个数字 N，求：第 N 小的用三个数相加的和，每个数必须是由重复的 1 构成，例如 1,11,111。

Solution

我们发现 1 \le N \le 333，答案范围不是特别大，想到了用 vector 预处理出所有的答案，排序之后取第 N 个。

注意枚举的时候由于只有三个加数，直接三重 for 循环就可以了。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 111111111111;
vector <long long> v;
int n;
int main() {
    cin >> n;
    // 暴力枚举即可
    for (long long i = 1; i <= N; i = i * 10 + 1) {
        for (long long j = 1; j <= N; j = j * 10 + 1) {
            for (long long k = 1; k <= N; k = k * 10 + 1) {
                v.push_back(i + j + k);
            }
        }
    }
    sort(v.begin(), v.end());
    auto k = unique(v.begin(), v.end()); // 注意要去重！
    cout << v[--n]; // 由于 vector 下标从 0 开始，所以要 --n
    return 0;
}