CF1213C Book Reading 题解

题目链接:
1.luogu
2.codeforces

C题很简单,只要会打表,轻松就AC

貌似也不用打表也能过,但是我发现我已经打了一般,然后就继续打了下去。

阅读题目时:

阅读题目大意,可以发现暴力的一个一个去查看是否满足条件是会超时的,所以我们需要进行优化,才能AC。

大致思路:

  1. 首先我们发现一个规律,对于每个数字的倍数来说,每10的倍数,都是一样的(这个其实很好说明,例如对于 3*33*13来说,最后一位就是取决于个位数*个位数的)
  2. 然后,既然有第一步的规律,我们就可以尝试吧整个表给打出来。分为a数组和b数组。a数组记录每一个数的末尾数字,b数组记录每一个数的总和。
    $\color{red}{Note:}$请注意b数组的形式,不能直接模2。因为有5的特例,对于5的倍数总数来说是25而不是45,且样例并未体现出该问题。 你可以看看我的WA code
  3. 最后,根据题目要求查看进行一轮(10个数)有多少个并乘以对应的b数组数值、不满足则查看进行了几个,并一一相加。

代码:

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
31
32
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int q;
ll n,m;
ll a[11][11]={{0},
{1,2,3,4,5,6,7,8,9,0},
{2,4,6,8,0,2,4,6,8,0},
{3,6,9,2,5,8,1,4,7,0},
{4,8,2,6,0,4,8,2,6,0},
{5,0,5,0,5,0,5,0,5,0},
{6,2,8,4,0,6,2,8,4,0},
{7,4,1,8,5,2,9,6,3,0},
{8,6,4,2,0,8,6,4,2,0},
{9,8,7,6,5,4,3,2,1,0},
};
ll b[11]={0,45,40,45,40,25,40,45,40,45};
int main() {
ios::sync_with_stdio(false);
cin>>q;
while(q--) {
cin>>n>>m;
ll c=(n%(m*10ll))/m,d=n/m/10,e=m%10,ans=0; //这里的c,d,e就是体现思路中的第三步了。其中d数组代表着进行了多少轮,e数组表示末尾数是多少,c数组代表着还有进行多少轮后还有多少零头
//何为10ll? 10ll代表着10这个数不是int类型的,而是long long类型的
for(int i=0;i<c;i++) {
ans+=a[e][i];
}
ans+=d*(b[e]);
cout<<ans<<'\n';
}
return 0;
}
支持原创!从我做起~ 支付宝搜“611460069”领到的红包也可以赞助哦~
召唤伊斯特瓦尔