专栏首页CSDN旧文蓝桥杯--算法入门级题目及答案解析

蓝桥杯--算法入门级题目及答案解析

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

1.杨辉三角形

问题描述

杨辉三角形又称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。

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

#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到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()判断长度

#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

问题描述
  给定一个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个数组来保证米字的形状没有皇后,斜线的保存我们要发现一条左斜线的横坐标减纵坐标是相同的,同一右斜线上的点横纵坐标相加的值相同,由此我们可以推理出以下搜索策略

#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.导弹拦截

问题描述
  某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

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

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

样例输出
6
2

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

#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数列

问题描述

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。

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

#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.校门外的树

问题描述
  某校大门外长度为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%的数据,区域之间没有重合的部分;
  对于其它的数据,区域之间有重合的情况。

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

#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.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];

#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.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

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

#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);
    }
}

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图论--LCA--Tarjan(离线)

    风骨散人Chiam
  • 使用高级程序设计语言实现集合的交并差运算

    风骨散人Chiam
  • 图论--拓扑排序--判断一个图能否被拓扑排序

    拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得...

    风骨散人Chiam
  • LeetCode 215. Kth Largest Element in an Array分析

    显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

    desperate633
  • LeetCode第五天

    leetcode 第五天 2018年1月6日 22.(566) Reshape the Matrix ? ? JAVA class Solution { ...

    郭耀华
  • P3809 【模版】后缀排序

    题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

    attack
  • BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)

    attack
  • 高仿京东金融的数值滚动尺

    以前博客讲的大部分都是静态的自定义View的编写,其实无非就是“画画”画出一个好看的效果,而这篇博客写的是写一个动态的自定义控价,这里不仅需要"画",还要各种事...

    HelloJack
  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 09:向量点积计算

    09:向量点积计算 总时间限制: 1000ms 内存限制: 65536kB描述 在线性代数、计算几何中,向量点积是一种十分重要的运算。 给定两个n维向量a=(...

    attack

扫码关注云+社区

领取腾讯云代金券