蓝桥杯真题31日冲刺国一 | 每日题解报告 第九天

大家好，我是泡泡，今天的题有些考验思维

一、最大乘积

题目链接：最大乘积 - 蓝桥云课 (lanqiao.cn)

题目要求：

把 1 ~ 9 这 9 个数字分成两组，中间插入乘号， 有的时候，它们的乘积也只包含 1 ~ 9 这 9 个数字，而且每个数字只出现 1 次。

比如：

984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
...

符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？

注意，需要输出的是一个整数，表示那个最大的积，只输出乘积，不要输出整个算式。

解题思路：

暴力全排列，将全排列数字分离成两个数字，判断有没有重复即可

#include<bits/stdc++.h>
using namespace std;
int a[11],b[11],s[11],ans;
bool pd(int n)//判重
{
    while(n)
    {
        s[n%10]++;
        n/=10;
    }
    for(int i=1;i<10;i++)
    {
        if(s[i]!=1)
        {
            return false;
        }
    }
    return true;
}
int jia(int x, int y)//分解
{
    int t=0;
    for(int i=x;i<=y;i++)
    {
        t = t * 10 + a[i];
    }
    return t;
}
void dfs(int x)
{
    if(x==10)
    {
        for(int i=1;i<=8;i++)
        {
            int x = jia(1,i);
            int y = jia(i+1,9);
        }
        for(int i=1;i<=8;i++)
        {
            int x = jia(1,i);                             
            int y = jia(i+1,9);        
            if(pd(x*y))
            {
                ans = max(ans,x*y);
            }
            memset(s,0,sizeof(s));
        }
        return;
    }
    for(int i=1;i<=9;i++)
    {
        if(!b[i])
        {
            a[x] = i;
            b[i] = 1;
            dfs(x+1);
            b[i] = 0;
        }
    }
}
int main()
{  
   dfs(1);
   cout<<ans;
   return 0;
}

二、阶乘约数

题目链接：阶乘约数 - 蓝桥云课 (lanqiao.cn)

题目要求：

定义阶乘 n! = 1 × 2 × 3 × · · · × n。

请问 100!（100 的阶乘）有多少个正约数。

解题思路：

用一个数学公式：

任意一个正整数 X 都可以表示成若干个质数乘积的形式，即 X = p1α1 ∗ p2α2 …… ∗ pnαn

约数个数 = (a1 + 1)(a2 + 1)……(an + 1)

100! 是个158位的数，我们先将1~100分别做因数分解，这些因数累乘起来，得到100!的因数分解。

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main()
{
    for(int i=2;i<=100;i++)
    {
        int n = i;
        for(int j=2;j<=n/j;j++)
        {
            while(n%j==0)
            {
                a[j]++;
                n /= j;
            }
        }
        if(n>1)
        {
            a[n]++;
        }
    }
    long long ans = 1;
    for(int i=2;i<=100;i++)
    {
        if(a[i])
        {
            ans *= (a[i]+1);
        }
    }
    cout<<ans;
    return 0;    
}

三、含2天数

题目链接：含 2 天数 - 蓝桥云课 (lanqiao.cn)

题目要求：

小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴，因为每天日历上都可以看到 2。

如果日历中只显示年月日，请问从公元 1900 年 1 月 1 日到公元 9999 年 12 月 31 日，一共有多少天日历上包含 2。即有多少天中年月日的数位中包含数字 2。

解题思路：

判断闰年，判断这个年份的位数是否带2，重点是这两个，如果年份没2，134567891011月份的带2日期是10*12，直接相加即可。

#include <bits/stdc++.h>
using namespace std;
bool pd(int y)//年份是否有2
{
    while(y)
    {
        if(y%10==2)
        {
            return true;
        }
        y /= 10;
    }
    return false;
}
bool run(int y)//闰年
{
    if(y%400==0||y%100!=0&&y%4==0)
    {
        return true;
    }
    return false;
}
int main()
{
    int n = 0;
    int t = 0;
    for(int i=1900;i<=9999;i++)
    {
        if(pd(i))
        {
            if(run(i))
            {
                n = 366;
            }
            else
            {
                n = 365;
            }
        }
        else
        {
            if(run(i))
            {
                n = 31 + 120 + 29;
            }
            else
            {
                n = 31 + 120 + 28;
            }
        }
        t += n;
    }
    cout<<t;
    return 0;
}

四、k倍区间

题目链接：“蓝桥杯”练习系统

题目要求：

解题思路：

区间序列之和是k的倍数，两个区间之间的差值如果是k的倍数，则中间的数满足k倍区间；用前缀和记录一下，再遍历用乘法原理

#include<bits/stdc++.h>
using namespace std;
long long sum,ans,a[100010];
int main()
{
    int n,k,x;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum += x;
        a[sum%k]++;
    }
    for(int i=0;i<k;i++)
    {
        ans += a[i] * (a[i]-1)/2;
    }
    ans += a[0];
    cout<<ans;
}

今天的题千万要多多理解，尤其第二题第四题，大家加油。