小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题

简介: 小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题

前言

继续的是我们寒假的好好逆袭和参加比赛!!!

一、煤球数目

题目描述:

有一堆煤球,堆成三角棱锥形。具体:

第一层放1个,

第二层3个(排列成三角形),

第三层6个(排列成三角形),

第四层10个(排列成三角形),…

如果一共有100层,共有多少个煤球?

请填表示煤球总数目的数字。

注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

分析分析:

我们真的没有走错片场嘛?啊哈哈哈哈哈哈哈,这就是一个简简单单的累加问题,直接开始吧!

题目代码

#include <iostream>
using namespace std;
int a[101]={0};
int main()
{
  int sum=0;
  for(int i=1;i<=100;i++)
  {
    a[i]=a[i-1]+i;
    sum=sum+a[i];
  }
  cout<<sum;
 } 

运行结果:

171700

二、生日蜡烛

题目描述:

某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来,他一共吹熄了236根蜡烛。

请问,他从多少岁开始过生日party的?

请填写他开始过生日party的年龄数。

注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

分析分析:

???模拟运算,从第一岁开始,然后一直到我们这个符合条件的岁数???,今年的真的好简单

题目代码

#include <iostream>
using namespace std;
int main()
{
  int sum = 0;
  //表示第几岁开始过生日
  for(int i = 1; i < 99; i++)
  {
    sum = 0;
    //现在第几岁
    for(int j=i; j < 99; j++)
    {
      sum += j;
      if(sum==236)
      {
        cout << i;
        return 0;
      }
    }
  }
  return 0;
 } 

运行结果:

26

三、凑算式

题目描述:

B      DEF
A + --- + ------- = 10
     C      GHI

这个算式中A到I代表1到9的数字,不同的字母代表不同的数字。

比如:

6+8/3+952/714 就是一种解法,

5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法?

分析分析:

和小唐学了这么久,这种题目我们就直接秒杀吧,有一种东西叫做全排列,next_permutation,直接出结果

题目代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  int sum=0; 
  int a[]={1,2,3,4,5,6,7,8,9};
  while(next_permutation(a,a+9))
  {
    float temp1=a[0];
    float temp2=a[1]*1.0/a[2];
    float temp3=(a[3]*100.0+a[4]*10.0+a[5])/(a[6]*100.0+a[7]*10.0+a[8]);
    if(fabs(temp1+temp2+temp3-10)<=1e-5)
    sum++;
  }
  cout<<sum;
 } 

运行结果:

29

四、快速排序

排序在各种场合经常被用到。

快速排序是十分常用的高效率的算法。

其思想是:先选一个“标尺”,

用它把整个队列过一遍筛子,

以保证:其左边的元素都不大于它,其右边的元素都不小于它。

这样,排序问题就被分割为两个子区间。

再分别对子区间排序就可以了。

下面的代码是一种实现,请分析并填写划线部分缺少的代码。

题目描述:

#include <stdio.h>
void swap(int a[], int i, int j)
{
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
}
int partition(int a[], int p, int r)
{
  int i = p;
  int j = r + 1;
  int x = a[p];
  while(1)
  {
    while(i<r && a[++i]<x);
    while(a[--j]>x);
    if(i>=j) break;
    swap(a,i,j);
  }
  ______________________;//填空
  return j;
}
void quicksort(int a[], int p, int r)
{
  if(p<r)
  {
    int q = partition(a,p,r);
    quicksort(a,p,q-1);
    quicksort(a,q+1,r);
  }
}
int main()
{
  int i;
  int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
  int N = 12;
  quicksort(a, 0, N-1);
  for(i=0; i<N; i++) 
    printf("%d ", a[i]);
  printf("\n");
  return 0;
}

分析分析:

这就是一个快速排序的基本操作了,那一个模块就是对函数是用于切割,表示比当前的数小的放左边,比当前数大的放右边,然后依次对左边和右边进行排序。填空部分就是在分完之后,将当前的数进行交换位置。我们可以直接带数字进去模拟会快很多

题目代码

swap(a,p,j);

五、抽签

题目描述:

X星球要派出一个5人组成的观察团前往W星。

其中:

A国最多可以派出4人。

B国最多可以派出2人。

C国最多可以派出2人。

那么最终派往W星的观察团会有多少种国别的不同组合呢?

下面的程序解决了这个问题。

数组a[] 中既是每个国家可以派出的最多的名额。

程序执行结果为:

DEFFF

CEFFF

CDFFF

CDEFF

CCFFF

CCEFF

CCDFF

CCDEF

BEFFF

BDFFF

BDEFF

BCFFF

BCEFF

BCDFF

BCDEF

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
void f(int a[], int k, int m, char b[])
{
  int i,j;
  if(k==N)
  { 
    b[M] = 0;
    if(m==0) printf("%s\n",b);
    return;
  }
  for(i=0; i<=a[k]; i++)
  {
    for(j=0; j<i; j++) 
      b[M-m+j] = k+'A';
    ______________________; //填空位置
  }
}
int main()
{
  int a[N] = {4,2,2,1,1,3};
  char b[BUF];
  f(a,0,M,b);
  return 0;
}

分析分析:

这个题目就由我们dfs的味道了,我们可以通过第一个if那里就可以看到那是一个递归的结构题了,到5的时候我们跳出,然后我们去看其他的逻辑,在哪里已经确定要是一个f(a,k+1,,b),关键就是我们的第三个属性了,这个我们更具上面的那一个for循环可以看到,m表示还需要多少人,这个就直接出来了f(a,k+1,m-j,b);

题目代码

f(a,k+1,m-j,b);

六、方格填数

题目描述:

如下的10个格子

(如果显示有问题,也可以参看【图1.jpg】)

填入0~9的数字。要求:连续的两个数字不能相邻。

(左右、上下、对角都算相邻)

一共有多少种可能的填数方案?

请填写表示方案数目的整数。

注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

分析分析:

既然不会!那我们就来暴力吧,嘿嘿,本来这个题目应该是要用dfs的,但是我个人更加喜欢暴力,它是一种美学!我们就只要简单的去判断,他的8个方位是不是连续的,然后去返回我们的值,再去做一个统计,这里有一个小细节,就是我把我们一开始的值都赋值给了-2,这样的话,我们就不用考虑他连不连续的问题了

题目代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int map[6][6];
int ans=0;
int Abs(int i,int j)//判断 8个方向 
{
  if(abs(map[i-1][j]-map[i][j])==1)
    return 0;
  if(abs(map[i+1][j]-map[i][j])==1)
    return 0;
  if(abs(map[i][j+1]-map[i][j])==1)
    return 0;
  if(abs(map[i][j-1]-map[i][j])==1)
    return 0;
  if(abs(map[i-1][j-1]-map[i][j])==1)
    return 0;
  if(abs(map[i+1][j-1]-map[i][j])==1)
    return 0;
  if(abs(map[i-1][j+1]-map[i][j])==1)
    return 0;
  if(abs(map[i+1][j+1]-map[i][j])==1)
    return 0;
  return 1;   
}
int f()//判断相邻的数是否连续 
{
  if(Abs(1,3)&&Abs(2,1)&&Abs(2,2)&&Abs(2,3)&&Abs(2,4)&&Abs(3,2))
    return 1;
  return 0; 
} 
int main()
{ 
  memset(map,-2,sizeof(map));
  int  a[] = {0,1,2,3,4,5,6,7,8,9};
  do{
    map[1][2]=a[0];
    map[1][3]=a[1];
    map[1][4]=a[2];
    map[2][1]=a[3];
    map[2][2]=a[4];
    map[2][3]=a[5];
    map[2][4]=a[6];
    map[3][1]=a[7];
    map[3][2]=a[8];
    map[3][3]=a[9];
    ans+=f();
  }while(next_permutation(a,a+10));
  cout<<ans<<endl;
  return 0;
}

运行结果:

1580

七、剪邮票

题目描述:

如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来,要求必须是连着的。

(仅仅连接一个角不算相连)

比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。

请你计算,一共有多少种不同的剪取方法。

分析分析:

这又是一个很经典的dfs算法,在这里,小唐没有想那没多,我们是不是要找一个5的邮票,这其实是已经定下来的,那我们直接使用全排列,把我们的所有可以做成5张邮票的数据找出来,然后我们去对我们5个邮票地位置进行一个比对,我们的答案就出来了,其实就是要求,你这五个邮票在不同的位置至少有一个相连就可以了

题目代码

#include<bits/stdc++.h>
using namespace std;
long long ans=0;
 int ss[3][4]={0,0,0,0,0,0,0,0,0,0,0,0};
 
 void dfs(int x,int y){
  if(x>2||x<0||y>3||y<0) return ;    
  if(ss[x][y]==0) return ;
  ss[x][y]=0;
  dfs(x+1,y);
  dfs(x,y+1);
  dfs(x-1,y);
  dfs(x,y-1);
 }
bool panduan(int a[12]){
  int k=0;
  int x,y;
  for(int i=0;i<3;i++){
    for(int j=0;j<4;j++){
      if(a[k]==1){
        x=i;y=j;
      }
      ss[i][j]=a[k++];
    }
  }
  dfs(x,y);
  int flag=0;
  
  for(int i=0;i<3;i++){
    for(int j=0;j<4;j++){
      if(ss[i][j]==1) flag=1;
    }
  }
  if(flag==1) return false;  
  return true;
}
int main(){
  int a[12]={0,0,0,0,0,0,0,1,1,1,1,1};
  do{
    if(panduan(a)) ans++;
  }while(next_permutation(a,a+12));
  
  cout<<ans;
  return 0;
} 

运行结果:

116

八、四平方和

题目描述:

四平方和定理,又称为拉格朗日定理:

每个正整数都可以表示为至多4个正整数的平方和。

如果把0包括进去,就正好可以表示为4个数的平方和。比如:

5 = 0^2 + 0^2 + 1^2 + 2^2

7 = 1^2 + 1^2 + 1^2 + 2^2

(^符号表示乘方的意思)

对于一个给定的正整数,可能存在多种平方和的表示法。

要求你对4个数排序:

0 <= a <= b <= c <= d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法

程序输入为一个正整数N (N<5000000)

要求输出4个非负整数,按从小到大排序,中间用空格分开

例如,输入:

5

则程序应该输出:

0 0 1 2

再例如,输入:

12

则程序应该输出:

0 2 2 2

再例如,输入:

773535

则程序应该输出:

1 1 267 838

分析分析:

???dfs就直接出来了

题目代码

#include<iostream>
using namespace std;
int sum;
int tmp[40];
int flag;
void dfs(int x,int step,int left)//x记录我们的大小,step我们数组的位置,left还差多少
{
  if(flag)
  return;
  if(step==4)
  {
    if(left==0){
      for(int i=1;i<=4;i++)//输出我们的数组
      cout<<tmp[i]<<" ";
      cout<<endl;
      flag=1;
    }
    return;
  }
  for(int i=x;i*i<=left;i++)
  {
    tmp[step+1]=i;
    dfs(i,step+1,left-i*i);
  }
}
int main()
{
  cin>>sum;
  dfs(0,0,sum);
  return 0;
}

运行结果:

【输入样式】
12
【输出样式】
2 2 2 2

九、交换瓶子

题目描述:

有N个瓶子,编号 1 ~ N,放在架子上。

比如有5个瓶子:

2 1 3 5 4

要求每次拿起2个瓶子,交换它们的位置。

经过若干次后,使得瓶子的序号为:

1 2 3 4 5

对于这么简单的情况,显然,至少需要交换2次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入格式为两行:

第一行: 一个正整数N(N<10000), 表示瓶子的数目

第二行:N个正整数,用空格分开,表示瓶子目前的排列情况。

输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。

分析分析:

冒泡排序???,这是什么题目,像极了小唐之前软考和数据结构的考试啊哈哈哈哈哈

题目代码

#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n+5];
  for(int i=0;i<n;i++)
      cin>>a[i];
  int min;
  int num=0;
  for(int i=0;i<n;i++){
    min=i;
    for(int j=i+1;j<n;j++){//找最小的 
      if(a[min]>a[j])
          min=j;
    }
    if(min!=i){
      num++;
      swap(a[i],a[min]);
    }
  }
  cout<<num<<endl;
  return 0;
}

运行结果:

输入:
5
3 1 2 5 4
输出:
3
输入:
5
5 4 3 2 1
输出:
2

十、最大比例

题目描述:

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。

并且,相邻的两个级别间的比例是个固定值。

也就是说:所有级别的奖金数构成了一个等比数列。比如:

16,24,36,54

其等比值为:3/2

现在,我们随机调查了一些获奖者的奖金数。

请你据此推算可能的最大的等比值。

输入格式:

第一行为数字N,表示接下的一行包含N个正整数

第二行N个正整数Xi(Xi<1 000 000 000 000),用空格分开。每个整数表示调查到的某人的奖金数额

要求输出:

一个形如A/B的分数,要求A、B互质。表示可能的最大比例系数

测试数据保证了输入格式正确,并且最大比例是存在的。

例如,输入:

3

1250 200 32

程序应该输出:

25/4

再例如,输入:

4

3125 32 32 200

程序应该输出:

5/2

再例如,输入:

3

549755813888 524288 2

程序应该输出:

4/1

分析分析:

这个题目,我一上手,笑死,直接懵了,小唐看的时候觉得是很简单的,但是随着去打。。。呵呵了,宝们先看看别人的思路

参考代码

题目代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#define MAX 100005
typedef long long ll;
using namespace std;
 
ll a[105];
 
struct node
{
  ll x,y;
}p[105];
bool cmp(node xx,node yy)
{
  return xx.x<yy.x;
}
int main()
{
  int n;
  cin>>n;
  for(int t=0;t<n;t++)
  {
    scanf("%lld",&a[t]);
  }
  sort(a,a+n);
  ll s1;
  ll x,y;
  int cnt=0;
  for(int t=n-1;t>=1;t--)
  {
    if(a[t]!=a[t-1])
    {
       s1=__gcd(a[t],a[t-1]);
       p[cnt].x=a[t]/s1;
       p[cnt++].y=a[t-1]/s1;  
      }
  }
  sort(p,p+cnt,cmp);
  ll minn=p[0].x;
  x=p[0].x;
  y=p[0].y;
    for(int t=0;t<cnt-1;t++)
    {
      if((p[t+1].x/p[t].x)<minn&&p[t+1].x/p[t].x!=1)
      {
        x=p[t+1].x/p[t].x;
        y=p[t+1].y/p[t].y;
    }
  }
  
  printf("%lld/%lld",x,y);
   
  return 0;
}
• 59
• 60

运行结果:

输入:
3
1250 200 32
输出:
25/4
输入:
4
3125 32 32 200
输出:
5/2


相关文章
|
28天前
|
数据安全/隐私保护 C++
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题
|
28天前
|
算法 测试技术 C++
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
|
28天前
|
算法 C++ 数据格式
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
|
1月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
64 0
|
1月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
49 0
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
49 0
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
58 0
|
1月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
53 0
|
1月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
35 1
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
52 0