关于模拟或暴力类型题的时间复杂度降维优化举例

首先,一般的模拟类型的题如果按照题面做一般就入坑了。因为此类题如果按照题面一步一步模拟,那时间复杂度会相当大,如果此模拟题数据不是很水,一般都不会通过,所以时间复杂度至少要降维处理。而模拟题一般的做法是推导,把模拟的过程推成一个公式,而公式的时间复杂度为常数,即O(1),即实现由0(…)0(N)->0(…)0(1)的降维过程。但推导公式往往是一件很麻烦的事情,因此推导公式是模拟类题的关键。以下两道题原本是用模拟或暴力来解决,但其实它们都是可以优化的,例如第一题只需要求周期内的数与周期即可,不用遍历全部数,第2题只需对该数n进行分析即可,时间复杂度0(1),不用从1遍历到n一个个进行统计。

斐波那契数列

百度熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它,向你展示了一个数字串,它称之为“斐波那契”串:

1

1
11235813471123581347112358…

聪明的你当然一眼就看出了这个串是这么构造的:

  1. 先写下两位在0~9范围内的数字a, b,构成串ab;

  2. 取串最后的两位数字相加,将和写在串的最后面。

上面百度熊向你展示的串就是取a = b = 1构造出来的串。

显然,步骤1之后不停地进行步骤2,数字串可以无限扩展。现在,百度熊希望知道串的第n位是什么数字。

输入数据的第一行为一个整数T(1 ≤ T ≤1000), 表示有T组测试数据;每组测试数据为三个正整数a, b, n(0 ≤ a, b < 10, 0 < n ≤109)。

对于每组测试数据,输出一行“Case #c: ans”(不包含引号) c是测试数据的组数,从1开始。

提示:

  1. 对于第一、二组数据,串为112358134711235…

  2. 对于第三组数据,串为14591459145914…

样例输入

1
2
3
4
3
1 1 2
1 1 8
1 4 8

样例输出

1
2
3
Case #1: 1
Case #2: 3
Case #3: 9

代码

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
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500;
int t, c, d, n, cyc, cnt;
int a[maxn], vis[maxn];
int init(){
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
a[1] = c;
a[2] = d;
cnt = 2;
while(!vis[a[cnt-1]*10+a[cnt-0]]){
vis[a[cnt-1]*10+a[cnt]] = cnt;
int tmp = a[cnt-1] + a[cnt];
if(tmp<10)
a[++cnt]=tmp;
else{
a[++cnt]=tmp/10;
a[++cnt]=tmp%10;
}
}
return vis[a[cnt-1]*10+a[cnt]];
}
int main(){
cin>>t;
for(int i = 1;i<=t;i++){
cin >> c >> d >> n;
int res = init();
cout<<"Case #"<<i<<": ";
if(cnt>=n)
cout<<a[n]<<endl;
else
cout<<a[res+(n-res)%(cnt-res)]<<endl;
}
return 0;
}

计数问题

试计算在区间 11 到 nn 的所有整数中,数字 xx(0 \leq x \leq 90≤x≤9)共出现了多少次?例如,在 11 到 1111 中,即在 11、22、33、44、55、66、77、88、99、1010、1111 中,数字 11 出现了 4 次。

输入格式

输入共 1 行,包含 2 个整数 nn、xx,之间用一个空格隔开。

输出格式

输出共 1 行,包含一个整数,表示 xx 出现的次数。

数据规模与约定

对于 100% 的数据,1 \leq n \leq 1,000,0001≤n≤1,000,000,0 \leq x \leq 90≤x≤9。

忽略每行输出的末尾多余空格

样例输入

1
11 1

样例输出

1
4

代码

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
#include<bits/stdc++.h>
using namespace std;
int n, x;
int main(){
cin>>n>>x;
int cnt = 0, res = 1, re = 1;
int tmp = n;
if(x){
while(tmp){
int mod = tmp%10;
cnt+=(res-re)/10*mod;
if(mod>x)
cnt+=re;
else if(mod==x)
cnt+=n%re+1;
re*=10;
res*=10;
res+=re;
tmp/=10;
}
}
else{
for(int i = 1;i<=n;i++)
for(int j=i;j;j/=10)
if(j%10==x)cnt++;
}
cout<<cnt<<endl;
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!