2018年美团春招(第二批)题解

时间:2021-11-17 14:03:35

  算法岗,一共两道编程题,题目具体如下:

第一题:

# 给你A数组,询问ΣΣA[gcd(i,j)],1<=i<=n,1<=j<=m
# 输入:
# 每行有四个整数,N,n,m,p,其中N表示A数组长度,n,m,p为参数;对于A数组如下得出:
#
# A[1]=p,A[x]=(A[x-1]+153)%p
#
# 数据范围
#
# 小数据 n,m<=N<=1000,p<=1000
#
# 大数据 n,m<=N<=100000,p<=100000

#其中gcd(i,j)表示i和j最大公约。

代码如下:

#include<iostream>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<sstream>
using namespace std;

int gcd(int  a,int b)
{
    if(a < b)
        return gcd(b,a);
    return b == 0 ? a : (b,a % b);

}
int getRs(int A[], int n, int m)
{
    int rs = 0;
    for(int i = 1; i <=n ; i++)
        for(int j = 1; j <=m; j++)
            rs += A[gcd(i,j)];
    return rs;
}
int main()
{
    int A[100001];
    int N,n,m,p;
    cin>>N>>n>>m>>p;
    A[1] = p;
    for(int i = 2; i <= N; i++)
        A[i] = (A[i - 1] + 153) % p;
    cout<<getRs(A,n,m)<<endl;

}

这样做,只能AC百分之60,当把rs由int改为long long的时候,就可以AC百分之90了,剩下的数据还是超时。试着从最大公约数的函数进行优化,但是没用。估计应该从getRs函数中的那叠加两个循环进行优化,可以看得出来,对于两个数a和b,i = a && j = b的gcd(i,j)和

j = a && i = b的gcd(i,j)的结果是相同的,也就是说这两个叠加循环中,实际上已有一半是重复计算的,但如果存储所有组合的gcd的话,内存会溢出。谁有好的思路,可以介绍下!

第二题:

# 小明在探寻数学的奥秘,她现在想知道n以内的正整数一共有多少位数字。不统计前导零。

# 例如:n为13时,12345678910111213,共17位,则输出为17。

# 输入:第一行一个数T(T<=100),表示数据组数。

# 对于每组数据,第一行1个整数n (1 <= n <= 10^9)
# 对于每组数据,输出一行,表示数字位数和

=========================================================================================================================

对于这道题,我用了四种方法,前三种都超时。

方法1:直接从i到n循环,判断每个数字的位数,求位数的方式如下:

int cnt = 0;
while(n)
{
    cnt++;
    n /= 10;
}

方法2:直接从1到n循环,并把每个数字转换成string,然后用size()方法求其长度,大体如下:

int cnt = 0;
while(n)
{
    cnt++;
    n /= 10;
}

方法3:由方法2得到的启示,直接把每个数字变成一个子串string,最后把这些子串合并成一个大的string,结果就是该string的size(),大致如下:

int fun(int num)
{
string str;
for(int i = 1; i <= num; i++)
     str += to_string(i);
return str.size();
}

但仔细一想,与方法2区别并不大,本质一样的哇。

方法4:

看来直接这么求是不行的,那么只能进行找规律了。仔细分析题目,可以找到这么一个规律:

令f(n)表示数字num长度为n时,从1到n位数组成的最大数字(如n=3时,最大数字是999),构成的数字位数和。那么:

n = 0时,f(0) = 0

n = 1时[1 ~ 9], f(1) = 9

n = 2时[1 ~9,10 ~ 99],f(2) =(99 - 9) * 2 + 9 = (10^2 - 1 - 9) * 2 + f(1) = 189 

n = 3时,[1 ~99,100 ~ 999],f(3) = (999 -99 )* 3 + 189 = (10 ^ 3 -1 -99 )* 3 + f(2)

...

当 n = 9时,f(9) =[10 ^ 9 - (10 ^ 8 - 1)] * 9 + f(8)

所以对于一个长度为n的数num,它的数字位数和 = f(n- 1) + [num - 10 ^(n - 1) + 1] * n,其中后半部分表示的是num与n-1位数的最大数字相差的数字个数。例如456可以分为两部分,1 ~ 99和 100 ~ 456,并且100 ~456的位数和为(456 - 100 +1) * 3.(加1是包括456本身)

代码如下:

#include<iostream>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<sstream>
using namespace std;

long long getRs(long long f[],int num)
{
    int len = to_string(num).size();
    return f[len - 1] + (num - pow(10 , len - 1) + 1) * len;
}
int main()
{
 long long f[10] = {0,9,189,2889,38889,488889,5888889,68888889,788888889,8888888889};
 int n;
 int num;
 cin>>n;
 while(n--)
 {
     cin>>num;
     cout<<getRs(f,num)<<endl;
 }
}

该方法的时间复杂度为O(1),绝不会超时的!我此处先实现计算出了每个f(n)对应的值,也可以不用实现计算出f(n)的值,根据公式迭代计算也是可以的。

注:返回结果应为long long(此处最好不要去使用long,因为在32为机器中long的表示范围和int是一样的,而long long不论在32位机器还是64位机器中,都占8个字节,所以没毛病!)

从这些题目中,可以得到一个很重要的结论:在做题前,一定要弄清楚单纯的int型 ,是否能够满足题目要求,取样例的极限值看看是否int会溢出,这是非常重要的一点!!!此外,造成溢出的值不一定是指变量,也可能包括函数的返回值,一定要考虑周全,方能AC!!!(JD的笔试题目中也有体现出这一点)