第十三届蓝桥杯真题解析

简介: 第十三届蓝桥杯真题解析


修建灌木

算法原理

1.模拟:

解题思路:

我们来模拟一遍很容易发现,一棵树如果想长得最高,就是看爱丽丝隔多长时间来修剪它

如图,以6为例,一定是往返的时间最长,而往返有两种方式,所以只需要比较两种往返谁大就好了。

其实如果是中间左边的(1 2 3 4),一定是往右往返最大,在中间右边的(5 6 7 8),一定是往左往返最大,但是这个中间数判断有些麻烦,要看总数是奇数还是偶数,又有整形变量精度缺失问题,索性就写个max就做比较了。

代码实现:

#define ll long long
#include<iostream>
using namespace std;
int max(int a,int b)
{
    return a>b?a:b;
}
 
int main ()
{
    int i,n;
    cin>>n;
    for(i=1;i<=n;i++)
  {
        cout<<max(i-1,n-i)*2<<endl;
    }
     
    return 0;
}

2.找规律

代码实现:

#include<iostream>
using namespace std;
  
int main()
{
    int n;
    int a[10005];
    scanf("%d", &n);
    if (n % 2 == 0)//n为偶数的时候
    {
        for (int i = 1; i <= n / 2; i++)
        {
            a[i] = (2 * (n - i));
            cout << a[i] << endl;
            //printf("%d\n", a[i]);
        }
        for (int j = n / 2 + 1; j <= n; j++)
        {
            a[j] = a[n + 1 - j];
            cout << a[j] << endl;
            //printf("%d\n", a[j]);
        }
    }
    if (n % 2 != 0)//n为奇数的时候
    {
        for (int i = 1; i <= n / 2; i++)
        {
            a[i] = 2 * (n - i);
            cout << a[i] << endl;
            //printf("%d\n", a[i]);
        }
        //printf("%d\n", n - 1);
        cout<<n-1<<endl;
        for (int j = n / 2 + 2; j <= n; j++)
        {
            a[j] = a[n + 1 - j];
            cout << a[j] << endl;
            //printf("%d\n", a[j]);
        }
    }
  return 0;
}

刷题统计:

算法原理:

1.暴力(80分)

直接将结果枚举出来

代码实现:

#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
  ll a, b, n;
  cin >> a >> b >> n;
  ll ret = 0;
  ll day = 0;
  for(ll j=0;;j++)
  {
    //一周
    for (ll i = 0; i < 7; i++)
    {
      if (i <= 4)
      {
        ret += a;
        day++;
      }
      else
      {
        ret += b;
        day++;
      }
      if (ret >= n)
        break;
    }
    if (ret >= n)
      break;
  }
  cout << day << endl;
  return 0;
}

但是当样例过大时会超时。

2.计算:

先用ans表示有多少周,n/(5a+b2)

工作日有二天,周末有二天

sum表示天数

用n-(5a+2b)*ans=剩余的天数

剩余的天数一定会落在工作日,或者周末这两种情况;

再用(n-(5a+2b)*ans)/a表示能在工作日完成的a题,

如果(n-(5a+2b)*ans)%a 不等于0,说明有剩余,还要加一天

在周末这种情况也同理;

代码实现:

//满分做法
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
  ll a, b, n;
  cin >> a >> b >> n;
  ll ans, sum = 0;
  //先看有多少周
  ans = n / (a * 5 + b * 2);
  ll m = a * 5 + b * 2;
    //剩余天数
    ll residue=n-m*ans;
    //天数=周数*7
    sum = ans * 7;
    //剩余天数<=工作日的工作量(落在工作日)
    if (residue<= 5 * a)
    {
        //能被工作日弄完
        sum += residue / a;
        //不能弄完
        if (residue % a != 0)
        {
            sum++;
        }
    }
    //落在周末
    else
    {
        //先把前面5天工作日加上
        sum += 5;
        //看剩余天数
        sum += (residue - 5 * a) / b;
        if ((residue - 5 * a) % b != 0)
        {
            sum++;
        }
    }
    cout << sum;
  return 0;
}

X进制减法

算法原理:

解题思路:10 4 0->1052+4*2=108.

因此A=a[i]*pr+a[i-1]*p[r-1]+……a[0];

注意事项:

数据非常大,必须边求边累加,直接累加最后相减会出现问题

代码实现:

#include<iostream>
#include<cstring>
using namespace std;
int p(int a,int b,int c)
{
    return (a>b?a:b)>c?(a>b?a:b):c;
}
int main()
{
    int n,m,l,a[100001],b[100001];
    long long res=0;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    cin>>l>>n;
    for(int i=n;i>0;i--)cin>>a[i];
    cin>>m;
    for(int i=m;i>0;i--)cin>>b[i];
    for(int i=n;i>1;i--)
    {
        res=((res+a[i]-b[i])*p(a[i-1]+1,b[i-1]+1,2))%1000000007;
    }
    res+=a[1]-b[1];
    cout<<res<<endl;
    return 0;
}

统计子矩阵:

算法原理:

/解题思路/

/使用双指针 将A数组中的任意俩列的前缀和看做一个一维数组求解/

/在一维数组中 a[n]={a[1],a[2],…,a[n]}; 类似题目 求其中不大于k:9的数组矩阵个数/

那么有俩个指针i j 开始时同时指向a[1]:1

sum=a[i]加到a[j]

sum比k小 则j++即j后移

比k大 则i++即i后移

sum比k大时,此时产生的数组数为(i-j)

代码实现:

#include<bits/stdc++.h>
using namespace std;
int a[520][520];
int s[520][520];  //A数列每行的前缀和 
int main()
{
  long long count=0;
  int k,m,n; cin>>n>>m>>k;
/*输入A数列 同时求前缀和*/
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {cin>>a[i][j]; s[i][j]=s[i][j-1]+a[i][j];}
/*数据处理*/
    for(int j1=1;j1<=m;j1++)
        for(int j2=j1;j2<=m;j2++) //j1 j2 表示所要枚举的列数 
    {
        int j=1,sum=s[1][j2]-s[1][j1-1]; //sum表示s数组的累加 
                for(int i=1;i<=n;i++)
            {
                 while(sum<=k && j<=n) {j++; sum+=s[j][j2]-s[j][j1-1];} 
                    count+=j-i;
                    sum-=s[i][j2]-s[i][j1-1]; //当sum>k时,i后移,同时要减去上一个值 
            }
    }
   cout<<count;
  return 0;
}

积木画

算法原理:

首先这个题肯定是用动态规划来做的,正好它也符合动态规划做题的思想,无后效性也满足所以我们用动态规划做会好做一点.

那怎么想这个题呢,首先它是二维的一个矩阵模式,并且有摆放还是有顺序的,所以我们如果要用二维dp来做还确实不好做,拿我们所幸直接用一维来简化拼积木的过程,但是怎么简化呢.

我们先来看下题目给的案例:

首先我们直接来看三阶的,第一个和第二个我们可以发现I型积木拼放的方式是有2种的,或者看一和四都行,然后L型积木的拼接方式是1种看三和五(你把他们两个反转过来就是一种),那我们不妨想的简单一点所以递推公式就是:d p [ i ] = d p [ i − 1 ] ∗ 2 + d p [ i − 3 ] dp[i]=dp[i-1]*2+dp[i-3]dp[i]=dp[i1]2+dp[i3];

证明的方法就是我们刚才的思想过程,我们讲二维的矩阵看成了一维的,所以I型积木就是等于1个方格,所以我们记为i-1,L型积木就是等于1.5个方格,但是L型积木不能单独出现,必须成双的出现,所以我们记为i-3,又由于I型积木出现在一个位置有两种方式,所以我们乘以二,L型积木出现只有一直方式我们乘以1,就结束了。

但是我们还要进行初始化前三个:

当i等于1的时候dp就是1,这个没啥说的,只能放一种I型不管咋放都一样.

当i等于2的时候dp是2,因为可以放两个I型,可以水平放可以竖直放2种.

当i等于3的时候就是题目当中的情况dp等于5,

代码实现:

#include<stdio.h>
#include<string.h>
#include<iostream>
#incldue<vector>
using namespace std;
#define mod 1000000007
int dp[10000005];
int main()
{
    int n;
    cin>>n;
    vector<int> dp(10000005,0);
    dp[1]=1,dp[2]=2,dp[3]=5;
    for(int i=4;i<=n;i++)
    {
        dp[i]=(dp[i-1]*2%mod+dp[i-3]%mod)%mod;
    }
    cout<<dp[n];
    return 0;
}
相关文章
|
10月前
|
机器学习/深度学习 算法 C++
2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析
2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析
260 0
|
10月前
蓝桥杯第六届省赛(单片机)--深度解析
蓝桥杯第六届省赛(单片机)--深度解析
113 0
十三届蓝桥杯真题JavaB组解析+代码(带你复习知识点)(一)
十三届蓝桥杯真题JavaB组解析+代码(带你复习知识点)(一)
【蓝桥杯嵌入式】蓝桥杯第十届省赛真题,程序题全解析(含代码)
【蓝桥杯嵌入式】蓝桥杯第十届省赛真题,程序题全解析(含代码)
347 0
|
存储
【蓝桥杯嵌入式】ADC模数转换的原理图解析与代码实现(以第十一届省赛为例)——STM32G4
【蓝桥杯嵌入式】ADC模数转换的原理图解析与代码实现(以第十一届省赛为例)——STM32G4
213 0
【蓝桥杯嵌入式】PWM的设置,原理图解析与代码实现(第十一届省赛为例)——STM32
【蓝桥杯嵌入式】PWM的设置,原理图解析与代码实现(第十一届省赛为例)——STM32
331 0
【蓝桥杯嵌入式】PWM的设置,原理图解析与代码实现(第十一届省赛为例)——STM32
【蓝桥杯嵌入式】STM32定时器的配置,解析预分频系数和重装载值与时钟频率的关系
【蓝桥杯嵌入式】STM32定时器的配置,解析预分频系数和重装载值与时钟频率的关系
465 0
【蓝桥杯嵌入式】LCD屏的原理图解析与代码实现(第十三届省赛为例)——STM32
【蓝桥杯嵌入式】LCD屏的原理图解析与代码实现(第十三届省赛为例)——STM32
351 0
【蓝桥杯嵌入式】点亮LED灯,流水灯的原理图解析与代码实现——STM32
【蓝桥杯嵌入式】点亮LED灯,流水灯的原理图解析与代码实现——STM32
444 0
蓝桥杯之单片机学习(十四)——基础技能综合实训案例解析
蓝桥杯之单片机学习(十四)——基础技能综合实训案例解析
228 0
蓝桥杯之单片机学习(十四)——基础技能综合实训案例解析

推荐镜像

更多