『算法-ACM竞赛』蓝桥杯-算法入门级题目及答案解析

『算法-ACM 竞赛』蓝桥杯-算法入门级题目及答案解析

写在最前面：
本文中会出现大量的请查阅.请自学什么的，不是我不讲，本文是面向算法初学者和蓝桥杯的文章，如果真的想看进阶算法的也不会来看这些题目，所以不要介意，我这里就算是抛砖引玉了，大佬勿喷，ACMEer 绕道哈哈哈哈。

1.杨辉三角形

问题描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。
它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
　　
下面给出了杨辉三角形的前4行：
   1
  1 1
 1 2 1
1 3 3 1
给出n，输出它的前n行。

输入格式
输入包含一个数n。

输出格式
输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。

样例输入
4
样例输出
1
1 1
1 2 1
1 3 3 1

数据规模与约定
1 <= n <= 34。

杨辉三角形入门的话就是考察代码编写，是个模拟题目，当数据量达到一定程度之后是组合数问题，可以使用卢卡斯定理，这里是入门，暂且不提，有兴趣可以去我博客数论查找！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int s[1000], a[1000];

void print(int source[], int ans[], int now, int target) //状态转移
{
    for (int i = 0; i < now; i++)
    {
        i == 0 ? ans[i] = 1 : ans[i] = source[i] + source[i - 1];
        cout << ans[i] << "\t";
    }
    puts("");
    if (now == target)
        return;
    print(ans, source, now + 1, target);
}
int main()
{
    int n;
    cin >> n;
    print(s, a, 1, n);
}

2.字符串比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
问题描述
　　给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：
　　1：两个字符串长度不等。比如 Beijing 和 Hebei
　　2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing
　　3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing
　　4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing
　　编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。
输入格式
　　包括两行，每行都是一个字符串
输出格式
　　仅有一个数字，表明这两个字符串的关系编号
样例输入
BEIjing
beiJing
样例输出
3


直接可以讨论用 c++的 string 即可，相关的 string 操作：1.可以判等== 2.可以比较字典序 < 或 > 3.reserve 反转 4.length()判断长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int compare(string s1,string s2)
{
    if(s1.length()==s2.length())
    {
        if(s1==s2)return 2;
        for(int i=0;i<s2.length();i++)
        {
            if(toupper(s1[i])!=toupper(s2[i])) return 4;
        }
        return  3;
    }
    else return 1;
}
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    cout<<compare(s1,s2);
}

3.N 皇后问题 Plus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
问题描述
　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
　　输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

解析
N 皇后问题，是一类搜索问题，这里我们使用 4 个数组来保证米字的形状没有皇后，斜线的保存我们要发现一条左斜线的横坐标减纵坐标是相同的，同一右斜线上的点横纵坐标相加的值相同，由此我们可以推理出以下搜索策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
int mp[10][10];
int hen[10], shu[10], zuo[100], you[100];
int ans = 0;
void js(int len, int cen)
{
    if (cen == len)
    {
        ans++;
        return;
    }
    // puts("--------------------------------------------------------\n");
    // for (int i = 0; i < len; i++)
    // {
    //     for (int j = 0; j < len; j++)
    //     {
    //         cout<< mp[i][j]<<" ";
    //     }
    //     puts("");
    // }
    for (int i = 0; i < len; i++)
    {
        if (hen[i] == 0 && shu[i] == 0 && zuo[(cen + i) / 2] == 0 && you[cen - i + len] == 0 && mp[cen][i])
        {
            mp[cen][i] = 0;
            hen[i] = shu[i] = zuo[(cen + i + 1) / 2] = you[cen - i + len] = 1;
            js(len, cen + 1);
            mp[cen][i] = 1;
            hen[i] = shu[i] = zuo[(cen + i + 1) / 2] = you[cen - i + len] = 0;
        }
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            cin >> mp[i][j];
        }
    js(n, 0);
    cout << ans << endl;
}

4.导弹拦截

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
问题描述
　　某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

　　输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
　　一行，为导弹依次飞来的高度
输出格式
　　两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入
389 207 155 300 299 170 158 65

样例输出
6
2

这是一类动态规划问题，LIS 问题。
第一问是求一个数列的最长下降子序列，第二问则是最长的非严格上升子序列(如 3 3 2 1，可以相等）因为最长上升子序列的每一个高度都需要一套拦截系统，彼此独立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int h[1000];
int dp[1000][2];
map<int,int> cou;
pair<int,int> Lis(int a[],int len)
{
    int ans=0,cnt=0;
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(h[j]<h[i]) dp[i][0]=max(dp[i][0],dp[j][0]+1);
            else dp[i][1]=max(dp[i][1],dp[j][1]+1);
            ans=max(ans,dp[i][0]);
            cnt=max(cnt,dp[i][1]);
        }

    }
    return make_pair(ans+1,cnt+1);
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> h[i];
    auto answ=Lis(h,n);
    cout<<answ.first<<" "<<answ.second <<endl;

}

5.Fibonacci 数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
问题描述

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。

说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。

因为是入门，蓝桥杯也考不了这么难，这里写递推。如果有兴趣进阶的话，可以研究下，矩阵快速幂，和母函数的做法，我博客里应该都有！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
const int MOD=10007;
int f[100000];
int init(int n)
{
    f[1]=f[2]=1;
    for(int i=3;i<=n;i++)
    f[i]=f[i-1]+f[i-2]%MOD;
}
int main()
{
    int n;
    cin>>n;
    init(n);
    cout<<f[n]<<endl;
}

6.校门外的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
问题描述
　　某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数 轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
　　由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已 知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树 都移走后，马路上还有多少棵树。

输入格式
　　输入文件的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点 和终止点的坐标。
输出格式
　　输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入
500 3
150 300
100 200
470 471
样例输出
298

数据规模和约定
　　对于20%的数据，区域之间没有重合的部分；
　　对于其它的数据，区域之间有重合的情况。

这道题很简单是签到题，就是考察的模拟，会不会处理区间重叠情况，这道题的进阶做法是差分，有兴趣的可以查阅，我们这里只是蓝桥杯和入门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int a[1000000];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        for(int j=l;j<=r;j++)
        {
            a[j]=-1;
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++)
        if(a[j]==0) ans++;
    cout<<ans<<endl;


}

7.夺宝奇兵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
算法提高 夺宝奇兵
时间限制：1.0s   内存限制：512.0MB

[题目描述]
　　在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图:

　　7
　　3 8
　　8 1 0
　　2 7 4 4
　　4 5 2 6 5

　　”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?在上图所示例子中,按照5->7->8->3->7的顺序,将得到最大值30

[输入]
　　第一行正整数N(100>=N>1),表示山的高度
　　接下来有N行非负整数,第i行有i个整数(1<=i<=N),表示山的第i层上从左到右每条路上的珠宝数目

[输出]
　　一个整数,表示从山底到山顶的所能得到的珠宝的最大数目.
[样例输入]
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

[样例输出]
　　30


经典 DP 算法，可以自下而上也可以从上向下，每次只保留最优的选择方案，状态转移方程为：
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + mountain[i][j];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int mountain[MAXN][MAXN];
int dp[MAXN + 1][MAXN + 1];

int main()
{

    cin>>n;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j <= i; ++j)
            cin>>mountain[i][j];
    }
    for (int i = N - 1; i >= 0; --i)
    {
        for (int j = 0; j <= i; ++j)
        {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + mountain[i][j];
        }
    }
    cout<<dp[0][0]<<endl;
}

8.质因数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 基础练习 分解质因数
时间限制：1.0s   内存限制：512.0MB

问题描述
　　求出区间[a,b]中所有整数的质因数分解。
输入格式
　　输入两个整数a，b。
输出格式
　　每行输出一个数的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
提示
　　先筛出所有素数，然后再分解。
数据规模和约定
　　2<=a<=b<=10000

因为是对区间进行分解，那么质因数将会用到很多次，我们不能每一次都进行试除法，所以预先达标保留，我这里只用了一次试除法，每次对求出小于右端点的所有质因子，这里用了一个小优化，一个数的一对因子不可能都大于他开根号，对于质数的筛法有埃式筛法和线性筛法我博客里也有可以去看，写到这里真的用不着，时间给的很充足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
int prime[10000], cnt = 0;
void init(int n)
{
    for (int i = 2; i < n; i++)
    {
        int flag = 0;
        for (int j = 2; j * j <= i; j++)
        {
            if (i % j == 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 1)
            continue;
        else
        {
            prime[++cnt] = i;
        }
    }
}
void fj(int n)
{
    cout << n << "=";
    int flag = 0;
    for (int i = 1; prime[i] <= n; i++)
    {
        while (n % prime[i] == 0)
        {
            if (!flag)
            {
                flag = 1;
            }
            else
                cout << "*";
            cout << prime[i];
            n /= prime[i];
        }
    }
    puts("");
}
int main()
{
    int l, r;
    cin >> l >> r;
    init(r);
    for (int i = l; i <= r; i++)
    {
        fj(i);
    }
}

写在最后：
我叫风骨散人，名字的意思是我多想可以不低头的自由生活，可现实却不是这样。家境贫寒，总得向这个世界低头，所以我一直在奋斗，想改变我的命运给亲人好的生活，希望同样被生活绑架的你可以通过自己的努力改变现状，深知成年人的世界里没有容易二字。目前是一名在校大学生，预计考研，热爱编程，热爱技术，喜欢分享，知识无界，希望我的分享可以帮到你！
如果有什么想看的，可以私信我，如果在能力范围内，我会发布相应的博文！
感谢大家的阅读！😘 你的点赞、收藏、关注是对我最大的鼓励！

算法 > ACM竞赛
『算法-ACM竞赛』蓝桥杯-算法入门级题目及答案解析
https://chiamzhang.github.io/2024/06/29/『算法-ACM竞赛』蓝桥杯-算法入门级题目及答案解析/
Author
Chiam
Posted on
June 29, 2024
Licensed under