十六届蓝桥杯模拟赛1题解

1. 填空题1

题意

问2024有多少个质因数

思路

法一：枚举所有的因数然后判断是否为质数

法二：使用唯一分解定理（质因数分解定理）

代码

唯一分解定理：

#include<bits/stdc++.h> 
// bits/stdc++.h是万能库，会包含所有可能用到的函数
using namespace std;
int main(){
    int n = 2024;
    int cnt = 0;
    for(int i =2;i<=n;i++){
        if(n%i == 0){
            cnt++;
            while(n%i==0){
                n/=i;
            }
            cout<<i<<' ';
        }
    }
    return 0;
}
/*输出
2 3
11 1
23 1
代表2024 = pow(2,3) * pow(11,1) * pow(23,1)
*/

2. 填空题2

题意

问n进行多少次整数根号后会得到1。

思路

循环即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n = 2024;
    int cnt = 0;
    while(n != 1){
        n = (int)sqrt(n);
        cnt++;
    }
    cout<<cnt;
    return 0;
}

3. 填空题3

题意

问大于等于2024的第一个立方数是多少。

思路

枚举立方数即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i = 1;i<=15;i++){
        cout<<i*i*i<<endl;
    }
    return 0;
}
/*
1
8
27
64
125
216
343
512
729
1000
1331
1728
2197
2744
3375
*/

可以发现比2024大的立方数是2197 ，相减得到2197-2024 = 173

4. 填空题4

题意

问1901 年1月1日到 2024年12月31日之间有多少个好日期。

思路

枚举所有天数即可。

代码

#include<bits/stdc++.h>
using namespace std;
int mon[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isLeap(int y){
    return (y%4==0 && y%100!=0) || y%400==0;
}
int main(){
    int xq = 2;//星期
    int y = 1901,m = 1,d = 1;
    int cnt = 0;
    while(y != 2024 || m != 12 || d != 31){
        xq++;
        if(xq == 8) xq = 1;
        d++;
        if(isLeap(y)) mon[2] = 29;
        else mon[2] = 28;
        if(d > mon[m]) d = 1, m++;
        if(m > 12) m = 1, y++;
        if(xq == 1 && d % 10 == 1) cnt ++;
    }
    cout<<cnt<<endl;
    //输出762
    return 0;
}

5. 填空题5

题意

给出一个长度为30的数组a，找到一个整数V，使得V对这30个数异或后，平方和最小。

求最小的平方和。

思路

我们发现所有的数都不超过$2^{14} = 16384$ ,也就是说我们可以将所有的数用14位的二进制数来表示出来。

我们直接令V等于$[0,2^{14})$中的每个数，然后各自求出一个答案后取最小值即可。

代码

#include<bits/stdc++.h>
using namespace std;
int nums[] = {9226,4690,4873,1285,4624,1596,6982,590,8806,121,8399,8526,5426,64, 9655,7705,3929,3588,7397,8020,1311,5676,3469,2325,1226,8203,9524,3648,5278,8647};
int main(){
    int mx = pow(2,14);
    long long ans = 0x3f3f3f3f3f3f3f3f;
    for(int v = 0;v<mx;v++){
        long long sum = 0;
        for(int i = 0;i<30;i++){
            int t = v ^ nums[i];
            sum += t * t;
        }
        ans = min(ans,sum);
    }
    cout<<ans<<endl; // 1070293541
    return 0;
}

6. 停车场

题意

每15分钟收费2元，不足15分钟不收费，问总停车时间n分钟，收费多少元

思路

很容易发现$ans = 2 * \lfloor \frac{n}{15} \rfloor$ ，其中undefinedlfloor x \rfloor$ 代表x的向下取整。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    cout<< n / 15 * 2;
    return 0;
}

7. 数的操作

题意

有一个整数n， 每次操作让整数的非0位减少1.问多好此操作这个数会变为0

思路

每个位数互相独立，所以我们进行数位分离，然后取最大值即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    long long ans = 0;
    while(n){
        ans = max(ans,n%10);
        n /= 10;
    }
    return 0;
}

8. 减法式子

题意

给你一个减法式子，请你处理一下然后输出结果

思路

模拟题，先读入字符串，因为两个数都是非负数，所以只需要找到字符串的减号，然后提取出左右两个子串即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int p = 0;
    while(s[p] != '-') p ++;
    string s1 = s.substr(0, p);
    string s2 = s.substr(p+1, 100);
    int n1 = stoi(s1);
    int n2 = stoi(s2);
    cout<<n1-n2;
    return 0;
}

9. 子数组的和

题意

对于一个长度为$n$的数组$a$ , 找到一个p，使得$a[p] + a[p+2] + a[p+4] + ... + a[p + 2*k-2]$ 最大。

思路

我们对数组按照下标的奇偶分为两个数组，然后分别求两个数组的长度为k的子数组求和问题 即可。

**思路一**：前缀和思想，我们求出sum数组，其中$sum[i] = \sum_{j=1}^i a[j]$ ，递推式为$sum[i] = sum[i-1] + a[i]$

然后我们枚举所有的$l \in [1,n-k+1]$ ,找到$sum[l+k-1] - sum[l-1]$的最大值即可。

**思路二** ： 滑动窗口，我们先求出$s = \sum_{i = 1}^k a[i]$ ，然后每次让子数组向右移动一次，即s = s + a[i+k]; s = s - s[i] 然后不断求s的最大值即可。

**注意int会超出范围导致无法拿满分！！！！**

代码

#include<bits/stdc++.h>
using namespace std;
long long sum1[10005];
int t1 = 0;
long long sum2[100005];
int t2 = 0;
int main(){
    int n;
    cin>>n;
    for(int i =1;i<=n;i++){
        int x ;cin>>x;
        if(i % 2 == 1) {
            t1 ++;
            sum1[t1] = sum1[t1-1] + x;
        }else {
            t2 ++;
            sum2[t2] = sum2[t2-1] + x;
        }
    }
    int k;cin>>k;
    long long ans = 0;
    for(int i = 1;i<=t1-k+1;i++){
        ans = max(ans,sum1[i+k-1]-sum1[i-1]);
    }
    for(int i = 1;i<=t2-k+1;i++){
        ans = max(ans,sum2[i+k-1]-sum2[i-1]);
    }
    cout<<ans<<endl;
    return 0;
}

10. 对勾子序列

题意

给你一个数组，请你找到其中一个子序列，满足前一部分单调递减，后一部分单调递增。

思路

本题考查了动态规划的经典问题： 单调递增子序列。

我们对数组进行一次求单调递增子序列，以及求单调递减子序列，然后枚举分界点，找到最大的答案即可。

如何求最长上升子序列？

我们设dp数组：$dp[i]$ 表示以$i$结尾的子序列，最长的上升子序列的长度是多少，我们发现他要么从前面某个dp值转移过来，即$dp[i] = dp[p] + 1 \ \& a[i] > a[p]$ ，要么自己作为子序列的开始,即$dp[i] = 1$ 。于是每个dp值通过枚举前面的所有的值就可以得到。总分时间复杂度为$o(n^2)$

最长下降子序列同理，只需要稍微更改条件即可。

在我们求出最长上升子序列数组$dp1$ ，和最长下降子序列数组$dp2$ 之后，最终答案就是$dp1[i] + dp2[i] - 1$的最大值了。

---

另：最长上升子序列问题可以通过优化来$O(nlogn)$实现，感兴趣者可以自行了解，本文不多赘述

代码

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int dp1[1005];
int dp2[1005];
int main(){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    for(int i = 1;i<=n;i++){
        dp1[i] = 1;
        for(int j = 1;j<i;j++){
            if(a[j]<a[i]){
                dp1[i] = max(dp1[i],dp1[j]+1);
            }
        }
    }
    for(int i = 1;i<=n;i++){
        dp2[i] = 1;
        for(int j = 1;j<i;j++){
            if(a[j]>a[i]){
                dp2[i] = max(dp2[i],dp2[j]+1);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        ans = max(ans,dp1[i]+dp2[i]-1);
    }
    cout<<ans;
    return 0;
}