蓝桥杯算法笔记

题目

1. 乌托邦树

问题描述

实现一个算法得到乌托邦树的高度。介绍如下：

乌托邦树每年经历 2 个生长周期。每年春天，它的高度都会翻倍。每年夏天，它的高度都会增加 1 米。

对于一颗在春天开始时种下的高 1 米的树，问经过指定周期后，树的高度为多少。

输入描述 输入一个数字 N\ (0 \leq N \leq 1000)N (0≤N≤1000)，表示指定周期。

输出描述 输出一个数字，为经过指定周期后树的高度。

题解

一年有两个生长周期，春天和夏天，春天长高一倍，夏天长高一米，每一年都是以春天开始的，例如输入 3 代表生长了 3 个周期，最后的高度是 6 米，因为树原本有一米，春天长了一倍后就是两米，过了一个周期，夏天长了一米后有 3 米，又过了一个周期，然后又到了春天，然后长了一倍就是 6 米。所以我们可以把春天的周期看作是奇数周期，夏天是偶数周期，轮到奇数周期就在原来的高度上增加一倍，轮到偶数周期就在原来的基础上增高一米，循环 N 就能得到最后的高度。

源代码

#include <iostream>
using namespace std;
int main()
{
  int N;
  int length = 1;
  cin >> N;

  for(int i = 1;i <= N;i++){
    if(i&1==1)          \\判断奇数或者是偶数的方法
      length=length*2;
    else
      length=length+1;
  }
  cout << length;

  return 0;
}

2. 用杂志拼接信件

问题描述

实现一个算法确定能否由杂志构成信件。介绍如下：

影视剧中信件大多是从报纸或杂志上的字符剪下来拼接而成的。

杂志和信件均由字符串构成，对于给定的杂志和信件，确定信件是否可以由杂志上的字符构成。

例如杂志为 ab，信件为 aa，则不能构成。杂志为 aab，信件为 aa，则可以构成。

输入描述 输入两行字符串，长度均不超过 100。

第一行为杂志字符串，第二行为信件字符串。

输出描述 输出一行，若信件可由杂志构成则输出 YES，否则输出 NO。

思路

此题的一种快捷算法是直接运用函数求解，查找字符串是否有包含关系，这种方法快捷简单，能够节省时间，但是需要我们对函数的使用方法有了解。 find()函数的使用方法。 在不知道函数的情况下，我们也可以解决，b 字符串的内容包含在 a 字符串里面的，所以我们就只要逐个检验对比两个字符串的情况就可以得出结果。

源代码

---

直接运用函数查找

#include <iostream>
#include<string>
using namespace std;
int main()
{
  // 请在此输入您的代码
  string a,b;
  cin >> a;
  cin >> b;
  if(a.find(b) != string::npos) //如果字符串不存在包含关系，那么返回值就一定是npos
    cout<<"YES";
  else cout<<"NO"; //k=-1说明没有找到
  return 0;
} 

---

使用数组单独查找

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string a, b;                                
    int c = 0, d = 0;
    cin >> a >> b;         //需注意此处为 b字符串 在 a字符串 中查找
    for (int i = 0; i < a.length(); i++) {
        if (a[i] == b[c])c++;
        if (js == b.length()) {
            d = 1;
            break;
        }
    }
    if (d == 1)
        cout << "YES";
    else cout << "NO";
    return 0;
} 

3. 分发饼干

问题描述

实现一个算法找到使最多孩子得到满足的分发饼干方法。介绍如下：

家长要将饼干分发给孩子，每个孩子有一个表示胃口的值，每个饼干有一个表示尺寸的值。如果饼干的尺寸与孩子的胃口相等或大于胃口，则将这个饼干分发给这个孩子，孩子能得到满足。

对于给定孩子及饼干的数组，需要将饼干分发给孩子，使最多的孩子得到满足。

例如孩子数组为 [1, 2, 3]，饼干数组为 [1, 1]，则将尺寸为 1 的饼干分发给胃口为 1 的孩子，这个孩子将得到满足，而另外的两个孩子无法得到满足。那么得到满足的孩子个数为 1 个。

思路

其实就是逐个比较数组元素的大小，由于数据规模小，所以直接使用双重循环也可以。

源代码

---

#include <iostream>
using namespace std;
int main()
{
  int N,M;
  int A[1001],B[1001];
  int count=0;
  cin >> N >>M;
  for(int i = 0;i<N;i++){
    cin >> A[i];
  }
  for(int i = 0;i<M;i++){
    cin >> B[i];
  }

  for(int i = 0;i<N;i++){
    for(int j = 0;j<M;j++){
      if(A[i] <= B[j]){
        count++;
        break;
      }
    }
  }
  cout << count;

  // 请在此输入您的代码
  return 0;
}

4. 其他元素的乘积

问题描述

给定一个数组，对于数组的每个位置，实现一个算法求数组中除当前元素的所有元素的乘积。介绍如下：

例如数组为 [0, 1, 2]，除当前元素的所有元素乘积为 [12, 02, 0*1]，结果为 [2, 0, 0]。 输入描述 第一行输入一个数字（2≤N≤10^4）。表示数组元素的个数。

第二行输入数组元素0≤A≤100。

输出描述 输出一行 N 个数字，由空格隔开，为除当前元素的所有元素的乘积。

思路

不能使用除法，我的第一想法就是把所有元素的全部乘一遍，得到一个 sum ，然后其他元素的值就为 sum / a[i], 我还考虑了元素的范围会不会超限，但是这根本就不需要考虑，因为数组 a 里面假如出现了一个元素为 0 ，那么这个方法就行不通。所以我们需要另寻它路。

我们再引进三个数组，分别存储 a 数组的左元素乘积和右元素乘积， l[i] 表示存储数组 a[i] 左边所有元素的乘积，r[i] 表示存储a[i]右边元素的乘积。最后一个 answer 数组用于存储最后的结果。可以得到结果。

源代码

---

借用三数组法

#include <iostream>
using namespace std;
int main()
{
  int N;
  int a[100001];
  int l[100001];
  int r[100001];
  int answer[100001];

  cin >> N;

  for(int i = 0 ;i < N;i++){
    cin >> a[i];
  }

  l[0]=1;
  for(int i = 1;i < N;i++){
    l[i] = a[i-1] * l[i-1];
  }
  r[N-1]=1;
  for(int i = N-2;i>=0;i--){
    r[i]= a[i+1] * r[i+1];
  }
  for(int i = 0;i<N;i++){
    answer[i] = l[i]*r[i];
    cout << answer[i] <<" ";
  }

  return 0;
}

---

只借用一个数组

#include <iostream>
using namespace std;
int main()
{
  int N;
  cin >> N;
  int a[N],answer[N];

  for(int i = 0;i < N;i++){
    cin >> a[i];
  }

  answer[0] = 1;
  for (int i = 1; i < N; i++) {
    answer[i] = a[i - 1] * answer[i - 1];
  }
  // R 为右侧所有元素的乘积
  // 刚开始右边没有元素，所以 R = 1
  int R = 1;
  for (int i = N - 1; i >= 0; i--) {
  // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
  answer[i] = answer[i] * R;
  // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
  R *= a[i];
  }
  for(int i = 0;i<N;i++){
    cout << answer[i] <<" ";
  }
  
  return 0;
}

5. 寻找 3 个数的最大乘积

问题描述

实现一个算法在数组中找到 3 个数字的最大乘积。介绍如下：

例如数组 [5, -2, 3, 1, -1, 4] 中 3 个数字的最大乘积为 60。
输入描述
第一行为数字 N (3≤N≤1000)，表示数组元素的个数。

第二行为数组元素 Ai -1000 <= Ai <= 1000
输出描述
输出一行，为 3 个数字的最大乘积。

思路

对数组进行排序，把最大的三个元素找出来乘起来就行；但是这个方法在蓝桥杯的评测系统评测时，调试的时候可以通过，但是提交代码的时候就显示错误，但是其他的三重循环的居然能通过我也是不知道为什么。

源代码

---

排序找最大元素

#include <iostream>
using namespace std;

void sort(int a[], int lo, int hi);
int partition(int a[], int lo ,int hi);
void swap(int a[], int i, int j);

void sort(int a[], int lo, int hi){
	if(hi <= lo) return;
	int j = partition(a, lo ,hi);
	sort(a, lo, j - 1);
	sort(a, j + 1, hi);
}

int partition(int a[], int lo ,int hi){
	int i = lo , j = hi + 1;
	int temp = a[lo];
	while(true){
		while(a[++i] < temp && i < hi);
		while(a[--j] > temp);
		if(i>=j) break;
		swap(a, i, j);
	}
	swap(a, lo, j);
	return j;
}

void swap(int a[], int i, int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

int main()
{
  int n;
  int a[n];
  cin >> n;
  
  for(int i = 0;i < n;i++){
    cin >> a[i];
  }

  sort(a,0,n-1);

  int sum = a[n-1]*a[n-2]*a[n-3];

  cout << sum;

  return 0;
}