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

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

斐波那契数列

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

1	11235813471123581347112358…

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

先写下两位在0~9范围内的数字a, b，构成串ab；
取串最后的两位数字相加，将和写在串的最后面。

上面百度熊向你展示的串就是取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开始。

提示：

对于第一、二组数据，串为112358134711235…
对于第三组数据，串为14591459145914…

样例输入

样例输出

1
2
3

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

代码

#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。

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

样例输入

11 1

样例输出

代码

#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;
}