蓝桥杯15届第二次模拟赛C/C++详解

简介: 蓝桥杯15届第二次模拟赛C/C++详解

第一题:不赘述了

108

第二题:

求 2**2023%1000,即 2的2023次方除以1000的余数

思路:

即求2的2023次方的后3位

我们只关心后三位即可,所以每次都让后三位*2即可

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int main()
{
    int x = 1;
    for (int i = 1; i <= 2023; i++)
    {
        x = (x * 2) % 1000;
    }
    cout << x << endl;
    return 0;
}

答案:

608

第三题:

 如果一个正整数转化成二进制与转换成八进制后所有数位的数字之和相等,则称为数位和相等的数。   

前几个数位和相等的正整数为 1, 8, 9, 64, ……   请问第 23 个数位和相等的正整数是多少?

思路:

直接暴力即可把每个数的二进制与八进制都算出来,暴力

代码:

4169
#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;
int bina(int  x)
{
    int sum = 0;
    stack<int> s;
    while (x)
    {
        s.push(x % 2);
        x /= 2;
    }
    while (!s.empty())
    {
        sum += s.top();
        s.pop();
    }
    return sum;
}
int eight(int x)
{
    int sum = 0;
    stack<int> s;
    while (x)
    {
        s.push(x % 8);
        x /= 8;
    }
    while (!s.empty())
    {
        sum += s.top();
        s.pop();
    }
    return sum;
}
int main()
{
    int cnt= 0;
    int i = 0;
    for (i = 1;cnt < 23;i++)
    {
        if (bina(i) == eight(i))
            cout << i << " " ,cnt++;
    }
    cout << i - 1;
    cout << (bina(4169) == eight(4169));
    return 0;
}

答案:

4169

第四题:

对于以下这些数(6行,每行6个,共36个),请问约数个数最多的是哪个?(如果有多个,请回答出现最早的那个)   

对于以下这些数(6行,每行6个,共36个),请问约数个数最多的是哪个?(如果有多个,请回答出现最早的那个)   

393353 901440 123481 850930 423154 240461   

373746 232926 396677 486579 744860 468782   

941389 777714 992588 343292 385198 876426   

483857 241899 544851 647930 772403 109929   

882745 372491 877710 340000 659788 658675   

296521 491295 609764 718967 842000 670302

代码:

2
#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;
int getNums(int x)
{
    int s = 0;
    for (int i = 1;i <= x; i++)
    {
        if (x % i == 0)
            s++;
    }
    return s;
}
int main()
{
    int n = 6;
    int a[6][6];
    int res = 0;
    int x,y;
    for (int i = 0; i < n;i++)
        for (int j = 0;j < n;j++)
        {
            cin >> a[i][j];
            int num = getNums(a[i][j]);
            if (num > res)
            {
                res = num;
                x = i;y = j;
            }
        }
    cout << x << " " << y;
    return 0;
}

答案:

901440(博主傻啦吧唧的直接写了第二数)

第5题:

小蓝有一个01矩阵。他打算将第一行第一列的 0 变为 2 。变化过程有传染性,每次 2 的上下左右四个相邻的位置中的 0 都会变成 2 。直到最后每个 2 的周围都是 1 或 2 结束。   请问,最终矩阵中有多少个 2 ?   以下是小蓝的矩阵,共 30 行 40 列。   

      0000100010000001101010101001001100000011   0101111001111101110111100000101010011111   1000010000011101010110000000001011010100   0110101010110000000101100100000101001001   0000011010100000111111001101100010101001   0110000110000000110100000000010010100011   0100110010000110000000100010000101110000   0010011010100110001111001101100110100010   1111000111101000001110010001001011101101   0011110100011000000001101001101110100001   0000000101011000010011111001010011011100   0000100000011001000100101000111011101100   0010110000001000001010100011000010100011   0110110000100011011010011010001101011011   0000100100000001010000101100000000000010   0011001000001000000010011001100101000110   1110101000011000000100011001001100111010   0000100100111000001101001000001010010001   0100010010000110100001100000110111110101   1000001001100010011001111101011001110001   0000000010100101000000111100110010101101   0010110101001100000100000010000010110011   0000011101001001000111011000100111010100   0010001100100000011000101011000000010101   1001111010010110011010101110000000101110   0110011101000010100001000101001001100010   1101000000010010011001000100110010000101   1001100010100010000100000101111111111100   1001011010101100001000000011000110110000   0011000100011000010111101000101110110001

思路:

代码:

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int n = 30;int m = 40;
int g[31][41];
char tg[31][41];
int cnt;
int bfs(int x,int y)
{
    queue<PII> q;
    PII p = {x,y};
    q.push(p);
    g[x][y] = 2;
    while (!q.empty())
    {
        PII p = q.front();
        cnt++;
        q.pop();
        int x = p.first;int y = p.second;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];int ny = y + dy[i];
            if (nx > 0 && nx <= n && ny > 0 && ny <= m && g[nx][ny] == 0)
            {
                g[nx][ny] = 2;
                q.push({nx, ny});
            }
        }
    }
}
int main()
{
    for (int i = 1 ;i <= n;i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> tg[i][j];
            g[i][j] = tg[i][j] - '0';
        }
    }
    bfs(1,1);
    cout << cnt; 
    return 0;
}

答案

541

第6题:

问题描述

  给定一个正好六位的正整数 x,请将 x 循环左移一位后输出。

  所谓循环左移一位,是指将原来的十万位变为个位,原来的万位到个位向左移动依次变为十万位到十位。

  例如:194910 左移一位变为 949101 。

  又如:987123 左移一位变为 871239 。

输入格式

  输入一行包含一个整数 x 。保证输入的 x 正好包含 6 个十进制数位,而且十万位和万位上的数字均不为 0 。

输出格式

  输出一行包含一个整数,表示答案。

样例输入

194910

样例输出

949101

代码:

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;
int main()
{
    string str;
    cin >> str;
    cout << str.substr(1,str.length()) << str.substr(0,1);
    return 0;
}

第7题:

问题描述

  输入一个仅包含小写英文字母的字符串,请问这个字符串中的最后一元音是什么。

  在英文中,a, e, i, o, u 共 5 个字母是元音字母,其它字母不是元音字母。

输入格式

  输入一行包含一个字符串,仅由小写英文字符组成,字符串中至少包含一个元音字母。

输出格式

  输出一行包含一个字符,表示答案。

样例输入

lanqiao

样例输出

o

样例输入

cup

样例输出

u

评测用例规模与约定

  对于所有评测用例,1 <= 字符数量 <= 10000 。

思路:

没啥思路暴力就完啦

代码:

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;
char yuan[] = {'a','e','i','o','u'};
int main()
{
    string str;
    cin >> str;
    char res;
    for (int i = 0;i < str.length();i++)
    {
        for (int j = 0;j < 5;j++)
            if (str[i] == yuan[j])
                res = str[i];
    }
    return 0;
}

第 8题:

1、问题描述:

  给定一个整数,对这个整数的一次转换是指将这个整数变为这个整数的所有数位上的非零数字的乘积。

  例如,对 123456789 进行一次转换变为 1*2*3*4*5*6*7*8*9=362880,再进行一次转换变为 3*6*2*8*8=2304,再进行一次转换变为 2*3*4=24,再进行一次转换变为 8。

  给定一个整数,请依次将转换过程中经历的每个整数输出,直到小于 10 。

2、输入格式:

  输入一行包含一个整数 n 。

3、输出格式:

  输出多行,每行包含一个整数。

4、样例输入:

123456789

5、样例输出:

362880

2304

24

8

思路:

简单的高精度乘法,每次计算递推即可

代码:

#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int> mul(vector<int>& A , int b){
    vector<int> C;
    int t = 0;
    for (int i = 0;i < A.size() || t;i++){
        if(i < A.size())    t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string a;
    cin >> a;
    vector<int> A;
    vector<int> C;
    C.push_back(1);
    int t = -1;
    for (int i = a.size() - 1 ; i>=0 ; i--) A.push_back(a[i] - '0');
    while (C.size() > 1 || t == -1)
    {
        t = 0;
        C.clear();
        C.push_back(1);
        for (int i = 0; i < A.size(); i++)
        {
            if (A[i])
                C = mul(C,A[i]);
        }
        for (int j = C.size() - 1; j >= 0;j--)
            cout << C[j];
        cout << endl;
        A = C;
    }
    return 0;
}

第9题:

1、问题描述:

  小蓝站在一个 n 行 m 列的方格图中间,方格图的每一个方格上都标有一个正整数。

  如果两个相邻方格(上下左右四个方向相邻)内的数的最大公约数大于 1 ,则可以从其中一个方格移动到另一个方格,当然也可以从另一个方格移回第一个方格。

  假设小蓝开始时站在第 r 行第 c 列,请问小蓝可以移动到方格图内的多少个方格?

2、输入格式:

  输入的第一行包含两个整数 n, m ,用一个空格分隔,表示方格图的行数和列数。

  接下来 n 行,每行包含 m 个正整数,相邻整数间用一个空格分隔,依次表示方格图中从第 1 行到第 n 行,每行从第 1 列到第 m 列中的数。

  接下来一行包含两个整数 r, c,用一个空格分隔,表示小蓝所在的行号和列号。

3、输出格式:

  输出一行包含一个整数,表示答案。

4、样例输入:

3 4

3 6 5 5

2 4 3 5

7 8 3 8

3 2

5、样例输出:

5

6、评测用例规模与约定:

  对于50%的评测用例,1 <= n, m <= 100,方格图中的每个数不超过 10**5 (10的5次方)。

  对于所有评测用例,1 <= n, m <= 1000,方格图中的每个数不超过 10**9 (10的9次方)。

思路:

因为它可以从一个点走到另一个点,还可以从另一个点再次走回去,所以我这里想得就是用bfs

dfs大多是一条路走到黑的那种

代码:

#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
const int N = 1010;
int g[N][N];
int st[N][N];
int n,m;
int x,y;
typedef pair<int,int> PII;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int maxDivisor(int a,int b)
{
    if (a >= b)
    {
        while (a % b)
        {
            a %= b;
            int temp = a;
            a = b;
            b = temp;
        }
    }
    else
    {
        while (b % a) {
            b %= a;
            int temp = b;
            b = a;
            a = temp;
        }
    }
    return min(a,b);
}
int bfs(int x,int y)
{
    int cnt = 0;
    st[x][y] = 1;
    queue<PII> q;
    q.push({x,y});
    while (!q.empty())
    {
        PII t = q.front();
        x = t.first;y = t.second;
        q.pop();
        cnt++;
        for (int i = 0; i < 4; i++)
        {
            int nx =  t.first + dx[i];int  ny = t.second + dy[i];
            if (nx > 0 && nx <= n && ny > 0 && ny <= m && !st[nx][ny] && maxDivisor(g[nx][ny],g[x][y]) > 1)
            {
                //cout << g[x][y] << " " <<  g[nx][ny] << " " << maxDivisor(g[nx][ny],g[x][y]) << endl;
                st[nx][ny] = 1;
                q.push({nx,ny});
            }
        }
    }
    return cnt;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m ;j++)
            cin >> g[i][j];
    cin >> x >> y;
    int res = bfs(x,y);
    cout << res;
    return 0;
}

第10题:

1、问题描述:

  给定一个序列 a[1], a[2], …, a[n] 和一个整数 k,请找出一个长度正好为 k 的区间,使得区间中所有数的和最大。

  即要找到一个整数 p ,使得 1 <= p 且 p+k-1 <= n ,使得 a[p]+a[p+1]+...+a[p+k-1] 最大。

2、输入格式:

  输入的第一行包含两个整数 n , k。

  第二行包含 n 个整数,相邻的整数之间使用一个空格分隔,表示给定的序列。

3、输出格式:

  输出一行包含一个整数,表示最大的区间和,你只需要输出和就行,不需要输出方案。

4、样例输入:

6 3

2 3 9 1 9 5

5、样例输出:

19

6、评测用例规模与约定:

  对于 30% 的评测用例,1 <= k <= n <= 30,1 <= a[i] <= 100。

  对于 60% 的评测用例,1 <= k <= n <= 1000,1 <= a[i] <= 10000。

  对于所有评测用例,1 <= k <= n <= 1000000,1 <= a[i] <= 1000000。

思路:

直接递推的话是100000次肯定能过 ,也可以用前缀和来做。都挺简单的,但是记得一定要开longlong 因为最大值1000000 * 1000000 = 1e12

直接递推:

#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
const int N = 10000010;
int a[N];
int n,k;
int main()
{
    cin >> n >> k;
    int sum = 0;
    unsigned long long res = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
        if (i >= k)
        {
            sum -= a[i - k];
        }
        res = max(sum,res);
    }
    cout << res;
    return 0;
}

前缀和:

算每个[ i , i - k)区间的前缀和,求最大值

#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
const int N = 10000010;
typedef unsigned long long ll;
ll a[N];
int n,k;
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        //滚动数组优化,因为sum[i] = sum[i - 1] + a[i]所以a[i - 1] a[i - 2]....都是无用的,可以直接拿他们盛放sum[i - 1]sum[i - 2]....;
        cin >> a[i];
        a[i] = a[i - 1] + a[i];
    }
    ll res = 0;
    for (int i = k;i <= n; i++)
        res = max(res,a[i] - a[i - k]);
    cout << res;
    return 0;
}

以上写的题解如果有错误,请大家指出,我自己也不知道自己做的对不对。

以后的模拟还会接着出题解

周赛的题解如果大家需要的话,可以在评论区说,也会出题解

目录
相关文章
|
5天前
|
测试技术 C++
[蓝桥杯 2023 省 B] 冶炼金属(c++)
[蓝桥杯 2023 省 B] 冶炼金属(c++)
15 0
|
2月前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
29 0
|
2月前
|
Java 数据安全/隐私保护 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-193 Password Suspects(C++&Java)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-193 Password Suspects(C++&Java)
20 1
|
2月前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-161 Abbott’s Revenge(C++写法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-161 Abbott’s Revenge(C++写法)
125 42
|
2月前
|
人工智能 测试技术 C++
第十五届蓝桥杯模拟赛B组(第二期)C++
第十五届蓝桥杯模拟赛B组(第二期)C++
87 0
第十五届蓝桥杯模拟赛B组(第二期)C++
|
3月前
|
C++
蓝桥杯15届第二次模拟C++
蓝桥杯15届第二次模拟C++
30 0
|
2月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
56 0
|
2月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
36 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
36 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
47 0