Skip to content

Codeforces - 1433A Boring Apartments

题解585 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

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

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

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

输入输出样例

样例输入 #1

4
22
9999
1
777

样例输出 #1

13
90
1
66

数据范围与约定

对于 100%100\% 的数据,1t36,1x99991 \leq t \leq 36, 1 \leq x \leq 9999

思路

先手算一下,可以找出规律:

  • (num mod 10)1(num \bmod 10) - 1 是结果的十位上的数字。
  • 数字长度为 ii 时,个位上的数字就是 1+2+3+...+i1 + 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;
}

非打表版

#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;
}