滴滴2023秋招笔试 老张的美数课 (C++ DP)

时间限制：3000MS
内存限制：589824KB
题目描述：
老张教授开了一堂美数课！
老张认为每个非员整数x都有一个美丽值b(x)。
一个非页整数的美丽值定义为这个数十进制下每个数位的异或和。即：

• 对于123来说，美丽值为1^2^3=0.
• 对于654815424，美丽值为6^5^4^8^1^5^4^2^4=9（在C/C++中^运算符表示异或）

现在老张想考考同学，对于 $[L,R]$ 这个闭区间内的所有整数，美丽值怡好为 $t$ 的数有多少个。

输入描述：

第一行一个正整数 T，表示有 T 次询问。
接下禾有三行，
第一行个非员整数 $L_1,L_2\dots L_i\dots L_T(1\le i\le T)$
第二行个非员整数 $R_1,R_2\dots Ri\dots R_T(1\le i\le T)$
第三行个非负整数 $t_1,t_2\dots t_i\dots t_T(1\le 1\le T)$
每个询问是对于$[L_i,R_i]$这个闭区间内的所有整数，美丽值怡好为 $t_i$ 的数有多少个。
$1\le T\le 70000$
$0\le L\le R\le 70000$
$0\le t\le 70000$

输出描述：

每个询问输出1个整数，共T个，每两个数之间用空格隔开，表示答案。

样例输入：

2
0 1
0 10
0 1
1
2
3
4

样例输出：

1 2
1

预分析

1. 1-70000每个数都要计算自己的”美丽值“，即各个位数的异或，时间开销会很大。那么大的问题，能不能转变成小的问题？所以就想到了DP。
2. 每次询问，是一个“子区间 + 符合条件的数量“，有点前缀和的影子。但是本题不能用，因为前缀和要记录0-9每一个数字的前缀和，就需要 $70001\times 10\times 4B$ 的空间来存pre数组，会报一个错误Aborted (core dumped)—内存空间不足。

DP

• DP数组的意义：$DP[i]$ 的值，就是数字 i 的美丽值。
• 递推函数：
• • 对于只有 1 位的数字 $[0,9]$， $DP[i]=i$; 也可以写成：$$DP[i]=DP[0]\stackrel{ˆ}{}i=DP[i/10]\stackrel{ˆ}{}(i\%10)$$
• • 对于有 2 位的数字 [10, 99], 如数字 11， $DP[12]=1\stackrel{ˆ}{}2=DP[1]\stackrel{ˆ}{}2=DP[12/10]\stackrel{ˆ}{}(12\%10)$;
     
    即：$$DP[i]=DP[i/10]\stackrel{ˆ}{}(i\%10)$$
• • 对于有 3 位的数字[100, 999], 如数字 243:， $DP[243]=2\stackrel{ˆ}{}4\stackrel{ˆ}{}3=\left(2\stackrel{ˆ}{}4\right)\stackrel{ˆ}{}3=DP[24]\stackrel{ˆ}{}3=DP[243/10]\stackrel{ˆ}{}(243\%10)$
     
    $$DP[i]=DP[i/10]\stackrel{ˆ}{}(i\%10)$$依旧成立;
• • 对于 4，5，6，7，8 ……位的数字都成立；
• 初始化：DP[0] = 0就行了
• 遍历顺序: 从 1 到 70000, 闭区间$[1,70000]$递增。

代码

#include 
#include

using namespace std;

int main() {
    int t;
    cin >> t;

    vector<int> left(t), right(t), value(t);
    for (int i=0;i < t;i++) cin >> left[i];
    for (int i=0;i < t;i++) cin >> right[i];
    for (int i=0;i < t;i++) cin >> value[i];

    vector<int> beau(70001);
    beau[0] = 0;
    for (int i = 1; i <= 70000; i++) {
        beau[i] = beau[i / 10] ^ (i % 10);
    }

    for (int i = 0; i < t; i++){
        int ans = 0;
        for (int j = left[i]; j <= right[i]; j++)
            if (beau[j] == value[i]) ans++;
        cout << ans << " ";
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29