Codeforces - 1433A Boring Apartments

题面

题目描述

我们把仅由一个或多个相同的数位组成的数字叫作「无聊的数字」。我们把 $\leq 10000$ 的这种数按照以下规则排列：

• 首先，将仅由 $1$ 组成的 $\leq 10000$ 的「无聊的数字」按照升序排列：$1, 11, 111, 1111, \dots$。
• 再将仅由 $2$ 组成的 $\leq 10000$ 的「无聊的数字」按照升序排列：$2, 22, 222, 2222, \dots$。
• 以此类推。

给出 $t$ 次询问，每次询问给定一个无聊的数字 $x$，请求出当数列排到 $x$ 时，$x$ 以及前面所有的“无聊的数字”的位数之和。

输入输出样例

样例输入 #1

4
22
9999
1
777

样例输出 #1

13
90
1
66

数据范围与约定

对于 $100\%$ 的数据，$1 \leq t \leq 36, 1 \leq x \leq 9999$。

思路

先手算一下，可以找出规律：

• $(num \bmod 10) - 1$ 是结果的十位上的数字。
• 数字长度为 $i$ 时，个位上的数字就是 $1 + 2 + 3 + ... + i$ 。

可以得到如下代码：

int num, ans = 0, i = 1;
cin >> num;
ans = ((num % 10) - 1) * 10;
while (num) {
    ans += i++;
    num /= 10;
}
cout << ans << endl;

代码

打表版

Codeforces 提交记录

#include <bits/stdc++.h>

using namespace std;

int main() {
    int           t, q;
    map<int, int> ans;
    cin >> t;
    ans[1]    = 1;
    ans[11]   = 3;
    ans[111]  = 6;
    ans[1111] = 10;
    ans[2]    = 11;
    ans[22]   = 13;
    ans[222]  = 16;
    ans[2222] = 20;
    ans[3]    = 21;
    ans[33]   = 23;
    ans[333]  = 26;
    ans[3333] = 30;
    ans[4]    = 31;
    ans[44]   = 33;
    ans[444]  = 36;
    ans[4444] = 40;
    ans[5]    = 41;
    ans[55]   = 43;
    ans[555]  = 46;
    ans[5555] = 50;
    ans[6]    = 51;
    ans[66]   = 53;
    ans[666]  = 56;
    ans[6666] = 60;
    ans[7]    = 61;
    ans[77]   = 63;
    ans[777]  = 66;
    ans[7777] = 70;
    ans[8]    = 71;
    ans[88]   = 73;
    ans[888]  = 76;
    ans[8888] = 80;
    ans[9]    = 81;
    ans[99]   = 83;
    ans[999]  = 86;
    ans[9999] = 90;
    while (t--) {
        cin >> q;
        cout << ans[q] << endl;
    }
    return 0;
}

非打表版

• 洛谷提交记录
• Codeforces 提交记录

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int num, ans = 0, i = 1;
        cin >> num;
        ans = ((num % 10) - 1) * 10;
        while (num) {
            ans += i++;
            num /= 10;
        }
        cout << ans << endl;
    }
    return 0;
}