1. 2067: [蓝桥杯2023初赛] 幸运数

传送门：http://oj.ecustacm.cn/problem.php?id=2067

1.1. 题意

小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 $2314$ 是一个幸运数字，因为它有 $4$ 个数位，并且 $2 + 3 = 1 + 4$ 。现在请你帮他计算从 $1$ 至 $100000000$ 之间共有多少个不同的幸运数字。本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。

1.2. Tag

模拟、枚举

1.3. 难度

☆

1.4. 思路1

直接从 $1$ 枚举到 $100000000$ ，每个数字判断两个条件：

偶数个数位
前半数位和等于后半数位和

数字 $x$ 拆分出每一位可以通过不断对 $10$ 求余数求解。

例如 $1234$ ： $1234\%10=4$ 、 $1234/10=123$ 、 $123\%10=34$ 、 $123/10=12$ 、...

这样就能求出每一位然后进行判断。

1.4.1. C++：

#include<bits/stdc++.h>
using namespace std;

inline bool check(int x){
    string s;
    while(x)s += (char)(x % 10 + '0'), x /= 10;
    int n = s.size();
    if(n % 2 == 1)return false;     //约束1：偶数个数位
    int sum1 = 0, sum2 = 0;
    for(int i = 0; i < n / 2; i++){
        sum1 += s[i] - '0';
        sum2 += s[i + n / 2] - '0';
    }
    return sum1 == sum2;            //约束2：前半部分和等于后半部分
}
int main(){
    // int ans = 0;
    // for(int i = 1; i <= 100000000; i++){
    //     if(check(i)){
    //         ans++;
    //         //cout<<i<<endl;
    //     }
    // }
    // cout<<ans<<endl;
    cout<<4430091<<endl;
    return 0;
}

1.4.2. Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // int ans = 0;
        // for(int i = 1; i <= 100000000; i++){
        //     if(check(i))ans++;
        // }
        int ans = 4430091;
        System.out.println(ans);
    }
    public static boolean check(int x) {
        String s = String.valueOf(x);
        if(s.length() % 2 == 1)return false;
        int sum1 = 0, sum2 = 0;
        for(int i = 0; i < s.length() / 2; i++){
            sum1 += s.charAt(i) - '0';
            sum2 += s.charAt(i + s.length() / 2) - '0';
        }
        return sum1 == sum2;
    }
}

1.4.3. Python：

def check(x):
    x = [int(i) for i in list(str(x))]
    n = len(x)
    if n % 2 == 1:
        return False
    return sum(x[:n // 2]) ==  sum(x[n // 2:])

# ans = 0
# for i in range(10, 100000001):
#     if check(i):
#         ans += 1
# print(ans)
print(4430091)

1.5. 思路2

统计位数相同且和相同的数字个数记为表 $A$ 。

$A[i][j]$ 表示 $i$ 位数中，和为 $j$ 的数字个数。

对于位数为 $2i$ 的数字，前半部分和为 $j$ 存在 $A[i][j]$ 种可能。

后半部分和为 $j$ 存在 $\sum_{k=1}^i A[k][j]$ 种可能（因为后半部分允许存在前导0）。

最终答案等于 $\sum_{i=1}^4 \sum_{j=1}^{i * 9}{A[i][j]} * (\sum_{k=1}^i A[k][j])$

1.5.1. C++

#include<bits/stdc++.h>
using namespace std;
int A[5][50];
int main(){
    for(int x = 1; x <= 9999; x++){
        int now_cnt = 0, now_sum = 0;
        int now = x;
        while(now)now_cnt++, now_sum += now % 10, now /= 10;
        A[now_cnt][now_sum]++;
    }
    int ans = 0;
    for(int i = 1; i <= 4; i++)
        for(int j = 1; j <= i * 9; j++)
            for(int k = 1; k <= i; k++)
                ans += A[i][j] * A[k][j];
    cout<<ans<<endl;
    return 0;
}

1.5.2. Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] A = new int[5][50];
        for(int x = 1; x <= 9999; x++){
            int now_cnt = 0, now_sum = 0;
            int now = x;
            while(now != 0){
                now_cnt++;
                now_sum += now % 10;
                now /= 10;
            }
            A[now_cnt][now_sum]++;
        }
        int ans = 0;
        for(int i = 1; i <= 4; i++)
            for(int j = 1; j <= i * 9; j++)
                for(int k = 1; k <= i; k++)
                    ans += A[i][j] * A[k][j];
        System.out.println(ans);
    }
}

1.5.3. Python

A = [[0] * 50 for i in range(5)]
idx = 0
for x in range(1, 10000):
    x = [int(i) for i in list(str(x))]
    A[len(x)][sum(x)] += 1
ans = 0
for i in range(1, 5):
    for j in range(1, i * 9 + 1):
        for k in range(1, i + 1):
            ans += A[i][j] * A[k][j]
print(ans)

1.6. 思考

如果求 $1-n$ 中的幸运数个数，其中 $n<=10^{18}$ 应该怎么做呢？

2067: [蓝桥杯2023初赛] 幸运数