avatar

目录
2018 SCUPC 校赛D题

2018校赛中的D题是除了两道签到题之外AC数最多的一题,然而我却感觉这题的难度在蓝桥杯初赛里面可以算压轴了吧。这也是我唯做出来的一题,大佬们打扰了。
下面来回顾一下这道AC数最多的非签到题。

Description
在自然数序列(0,1,2,3,4,5…)中,求去掉所有含2,3,5,7的数字后(0,1,4,6,8,9…)的第k个数.

Input
第1行为输入组数T。
第2—T+1行为长度k。
T≤1000,1≤k≤1000000000000

Output
每组样例输出一行。

Sample Input
3
1
4
1000000000000

Sample Output
0
6
4086441010601686

Time Limit: 1000ms, Memeory Limit: 64MB

第一次打这种真格算法竞赛的我,第一次想的是直接枚举暴力(来自暴力蓝桥杯省二选手的挣扎),然后队友告诉我1000000000以上枚举一遍直接超时,果然我还是不懂规矩啊TAT。
那怎么办呢?找规律吧,不如先把0到100满足条件的数列出来再看看?
data.png

可以看到前10个自然数[0,9]中满足条件的有6个数,前100个自然数[0,99]中满足条件的有36个数,所以可以大胆地猜测,前10的n次方个自然数中有6的n次方个是满足条件的。(这是当时解题时的思路,然而好像这个思路对解题影响并不大)
现在我们知道98这个自然数是第35个满足条件的自然数。那逆过来是怎么推导的呢?
上面的矩阵一行是6个数,所以第35个数应该是在第(35//6+1)行,第(35mod6)列,也就是6行5列。
那6行5列和98有关系吗?其实把上面的矩阵换个方法看,可以变成这样:
table_data.png
看看行标和列标可以说6行5列是90+8=9*10+8*1
我们建立一个映射

F(a) = {1,2,3,4,5,6}->{0,1,4,6,8,9}

那么

98==F(6)*10+F(5)*1==9*10+8*1

到了这里问题已经很明显了,这是一道进制转换的数论题,要求把十进制减一(这里要注意0占了一个坑)转换成六进制,再对这个6进制数每一位进行一次映射。进制转换的问题,用短除法就可以解决,至于映射,写一个数组就好了。

Code
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
30
#include<iostream>
using namespace std;

long long int pow(int i, int n) { //重复造轮子症
if(n == 0)
return 1;
if(n == 1)
return i;
return i * pow(i, n-1);
}

int main() {
int map[6] = {0,1,4,6,8,9}; //用于映射的数组
int t;
cin >> t;
for(int i = 0; i < t; i++) {
long long int tmp, sum = 0;
int len = 0;
cin >> tmp;
long long int k = tmp - 1;
while(k != 0) { //短除法
int bit = k % 6;
sum += pow(10, len) * map[bit];
len++;
k /= 6;
}
cout << sum << endl;
}
return 0;
}

不得不说这道AC数最高的题花了我两个小时的时间。

文章作者: LightingX
文章链接: http://lightingx.top/blog/2018/04/20/2018%20SCUPC%20%E6%A0%A1%E8%B5%9BD%E9%A2%98/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LightingX

评论