2023年4月蓝桥杯B组A到G题解析

标签：10 R1 int 整数 蓝桥 126 2023 解析 dp

试题 A: 阶乘求和 本题总分：5 分 【问题描述】 令 S = 1! + 2! + 3! + ... + 202320232023!，求 S 的末尾 9 位数字。 提示：答案首位不为 0。 【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。 思路:暴力计算量会超过10^12,考虑阶乘特点,对于i∈[1,202320232023],当i增大时,i中所含的偶因子{2,5,10...}会越来越多,不妨假设当i超过某个数时i!的末九尾全为0,所以打表看一下Si = 1!+2!+.....+i!,当Si的末九位不变时,就得到了答案.

#include<bits/stdc++.h>
using namespace std;
int mian()
{
long long ans = 0;
for(int i=1;i<=10000000;i++)
{
    long long temp =  1;
    for(int j=1;j<=i;j++)
    {
         temp*=j;
     }
ans+=temp;
ans%=1000000000;
cout<<ans<<endl;
}
return 0;
}

　　

试题 B: 幸运数字 本题总分：5 分 【问题描述】 哈沙德数是指在某个固定的进位制当中，可以被各位数字之和整除的正整 数。例如 126 是十进制下的一个哈沙德数，因为 (126)10 mod (1+2+6) = 0；126 也是八进制下的哈沙德数，因为 (126)10 = (176)8，(126)10 mod (1 + 7 + 6) = 0； 同时 126 也是 16 进制下的哈沙德数，因为 (126)10 = (7e)16，(126)10 mod (7 + e) = 0。小蓝认为，如果一个整数在二进制、八进制、十进制、十六进制下均为 哈沙德数，那么这个数字就是幸运数字，第 1 至第 10 个幸运数字的十进制表示 为：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。现在他想知道第 2023 个幸运数 字是多少？你只需要告诉小蓝这个整数的十进制表示即可。 【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include<bits/stdc++.h>
using namespace std;
int geta(int x)
{
     int ans = 0;
     while(x)
     {
       ans+=x%10;
       x/=10;
     }
return ans;
}
int mian()
{
int temp = 11;//从第11个开始;
for(int i=127;i<=10000000;i++)
{
    if(i%geta(i)==0)
{
cout<<temp++<<i<<endl;
}
}
return 0;
}

      试题 C: 数组分割 时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分 【问题描述】 小蓝有一个长度为 N 的数组 A = [A0, A1, . . . , AN−1]。现在小蓝想要从 A 对 应的数组下标所构成的集合 I = {0, 1, 2, . . . , N − 1} 中找出一个子集 R1，那么 R1 在 I 中的补集为 R2。记 S 1 = ∑ r∈R1 Ar，S 2 = ∑ r∈ R2 Ar ，我们要求 S 1 和 S 2 均为 偶数，请问在这种情况下共有多少种不同的 R1 。当 R 1 或 R2 为空集时我们将 S 1 或 S 2 视为 0。 【输入格式】 第一行一个整数 T，表示有 T 组数据。 接下来输入 T 组数据，每组数据包含两行：第一行一个整数 N，表示数组 A 的长度；第二行输入 N 个整数从左至右依次为 A0, A1, . . . , AN−1，相邻元素之 间用空格分隔。 【输出格式】 对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你 需要将答案对 1000000007 进行取模后输出。 【样例输入】 2 2 6 6 2 1 6 【样例输出】 4 思路:若A中的元素有奇数个奇数,则无存在的划分,反之若存在n个(n%2=0&&n!=A.length),则划分为组合数Cn0+Cn2+Cn4+...+Cnn = 2^(n-1)+1,若n=A.length,则划分为Cn1+Cn2+Cn3+...+Cnn = 2^n

import java.util.Scanner;
public class C
{
    public static int t;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        while ((t--) != 0)
        {
            int fod = 0;
            int n;
            n = sc.nextInt();
            for (int i = 0;i < n;i++)
            {
                int x;
                x = sc.nextInt();
                if (x % 2 == 1)
                {
                    fod++;
                }
            }
            if (fod % 2 == 1)
            {
                System.out.print(0);
                System.out.print("\n");
                continue;
            }
            else
            {
                if (fod == 0)
                {
                    System.out.print((long)Math.pow(2,n));
                    System.out.print("\n");
                }
                else
                {
                    System.out.print((long)(Math.pow(2,fod - 1)) + 1);
                    System.out.print("\n");
                }
            }
        }
    }
}

时间开销O(n)     试题 D: 矩形总面积 时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分 【问题描述】 平面上有个两个矩形 R1 和 R2，它们各边都与坐标轴平行。设 (x1, y1) 和 (x2, y2) 依次是 R1 的左下角和右上角坐标，(x3, y3) 和 (x4, y4) 依次是 R2 的左下 角和右上角坐标，请你计算 R1 和 R2 的总面积是多少？ 注意：如果 R1 和 R2 有重叠区域，重叠区域的面积只计算一次。 【输入格式】 输入只有一行，包含 8 个整数，依次是：x1，y1，x2，y2，x3，y3，x4 和 y4。 【输出格式】 一个整数，代表答案。 【样例输入】 2 1 7 4 5 3 8 6 【样例输出】 22 思路:得出R1四个角的坐标后看看是否存在某个角落在R2的区域,减去重叠区域的面积. 时间开销O(1)     试题 E: 蜗牛 时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分 【问题描述】 这天，一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0，横坐标分别 为 x1, x2, ..., xn。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 (xn, 0)。它只能在 x 轴上或者竹竿上爬行，在 x 轴 上爬行速度为 1 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行 的速度分别为 0.7 单位每秒和 1.3 单位每秒。 为了快速到达目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之间建立了传 送门（ 0 < i < n），如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai)，就可以 瞬间到达第 i + 1 根竹竿的高度为 bi+1 的位置 (xi+1, bi+1)，请计算蜗牛最少需要 多少秒才能到达目的地。 【输入格式】 输入共 1 + n 行，第一行为一个正整数 n； 第二行为 n 个正整数 x1, x2, . . . , xn； 后面 n − 1 行，每行两个正整数 ai , bi+1。 【输出格式】 输出共一行，一个浮点数表示答案（四舍五入保留两位小数）。 【样例输入】 3 1 10 11 1 1 2 1 思路:dp,设有dp[i][0],dp[i][1]表示到达第i根杆子底部和第i根杆子的传送点的最优解,则有状态转移方程dp[i][0] = min(dp[i-1][0],dp[i-1][1]+从第i-1根下来到第i根的时间),dp[i][1] = min(dp[i-1][1]+两个传送点的时间,dp[i-1][0]+从第i-1根底部到第i根传送点的时间);当到达最后一根杆子时,ans = min(dp[n-1][0],dp[n-1][1]+从第n-1根上下来的时间). 时间开销O(n)       试题 G: 买二赠一 时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分 【问题描述】 某商场有 N 件商品，其中第 i 件的价格是 Ai。现在该商场正在进行 “买二 赠一” 的优惠活动，具体规则是： 每购买 2 件商品，假设其中较便宜的价格是 P（如果两件商品价格一样， 则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P 2 的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商 品，但是每件商品只能被购买或免费获得一次。 小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少 钱？ 【输入格式】 第一行包含一个整数 N。 第二行包含 N 个整数，代表 A1, A2, A3, . . . ，AN。 【输出格式】 输出一个整数，代表答案。 【样例输入】 7 1 4 2 8 5 7 1 【样例输出】 25 思路:贪心,首先sort(A,A+n),每次取两个最大的出来然后,用其中小的带来的优惠买一件免费的,用book数组记录被买过的

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int ans = 0;
map<int,int> m;
int prices[N];
int book[N];//用来记录什么被买过
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
        m[prices[i]/2] = 1;
    }
    sort(prices, prices + n);
    int flag =0,temp = 1e9+7;
    for(int i=n-1;i>=0;i--)
    {
       if(book[i]==0&&flag<=1)
       {
           ans+=prices[i];
           temp = min(temp,prices[i]);
           flag++;
       }
       if(flag==2)
       {
           int i = upper_bound(prices,prices+n,temp/2)-prices-1;//用upper_bound快速定位能买的优惠商品,时间开销logn
           while(i>=0&&book[i]==1)
           {
               i--;
           }
           if(i>=0)
           book[i] = 1;
           flag = 0;
           temp = 1e9+7;
       }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度O(nlogn);

标签：10,R1,int,整数,蓝桥,126,2023,解析,dp
From： https://www.cnblogs.com/remarkableboy/p/17299397.html