【题解】等比整数

题意

给你一长度为的整数，你可以在其中取一些数字组成新的整数，问出现次数最多的新树是什么呢，取的数的位置需要满足一个条件就是要求取得数字的下标之差所组成的序列是一个等比序列。

题解

实际上出现次数最多的字符串只会在长度为的数字以及长度为的数字当中出现。因为，当若存在某一个数字出现次数最多且长度大于，长度为的数字肯定也是其子串，且出现次数应该大于等于该长度大于的数的。所以我们只要去找这个长度为的数中长度为和的串最多出现次数即可。统计长度为的数很简单，统计长度为的数只用用一个二维数组，来就可以了，表示以开头以结尾的数字有多少个。

复杂度

时间复杂度

代码

#include <bits/stdc++.h>
using namespace std;
long long a[10],b[10][10];
int main()
{
    string str;
    cin>>str;
    for(int i=0; i<str.length(); i++)
    {
        int x=str[i]-'0';
        for(int j=0; j<10; j++)
            b[j][x]+=a[j];
        a[x]++;
    }
    long long ans=0;
    for(int i=0; i<10; i++)
        ans=max(ans,a[i]);
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
            ans=max(ans,b[i][j]);
    }
    printf("%lld\n",ans);
    return 0;
}