历年蓝桥杯省赛B组真题试题.doc

(完整word)历年蓝桥杯省赛B组真题试题
(1）
煤球数目

有一堆煤球,堆成三角棱锥形。具体：
第一层放1个，
第二层3个(排列成三角形）,
第三层6个（排列成三角形），
第四层10个（排列成三角形），
。...
如果一共有100层，共有多少个煤球？

题解：纯粹的数学题而已

int a[101］ =｛0};
for（int i = 1 ； i < 101 ； i ++)
a[i] = a［i-1] + i;
int ans = 0;
for（int j = 1 ; j < 101 ； j ++）
ans += a［j］;
printf(”％d\n",ans)；

(2）
生日蜡烛

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

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

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

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

题解：暴力枚举.
第一重循环枚举刚开始过生日时候的岁数。
第二重循环是枚举现在的岁数
第三重循环就是将刚开始过生日的岁数和现在的岁数加起来。

int start,end；
for（start = 1 ； start < 236 ； start ++)
{
for( end = start ； end < 236 ; end ++ )
｛
int sum = 0;
for（int i = start； i <= end； i ++)
sum += i；
if( sum == 236)
printf（"start ： ％d end ： ％d\n”，start，end)；
｝
}

（3)
B DEF
A + — + —— = 10
C GHI

(如果显示有问题，可以参见【图1.jpg】）

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

比如:
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法？ //29

题解：DFS+回溯
由于计算机中5/2会等于2，而且如果打算采用精度方面的处理的话，会很麻烦，而且很容易错。
所以,把这些式子全部变成乘法形式就好了.
A＊C＊GHI+B＊GHI+DEF*C=10＊C*GHI

代码:
int visit[10］，num[10]；
int sum=0；

void dfs(int n)
{
if(n==10)
{
int b=num[7]*100+num［8］*10+num[9］; //GHI
int a=num[4］*100+num[5］*10+num［6］; //DEF
//cout〈〈b〈<' ’<〈a〈<’ '〈〈num［1］〈〈’ ’<〈num[2］〈〈’ ’<<num[3]<〈endl;
if（num［1］*num［3］*b+num[2]*b+num［3］＊a==10＊num［3］＊b) sum++;
//cout〈<”＊"〈〈endl；
return ;
｝
for（int i=1;i<=9;++i)
｛
if（!visit［i］)
{
visit［i]=1;
num［n］=i；
dfs（n+1);
visit［i]=0；
num[n]=0;
｝
}
｝

int main（）
{
memset（num，0，sizeof(num）)；
memset（visit，0,sizeof（visit))；
dfs(1）；
cout<<sum；
return 0;
｝

(4)
快速排序

排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。

其思想是:先选一个“标尺"，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。

这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。

这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。

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

#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); //由于要按照从小到大排序，就i一直向右移动直到大于x值位置
while（a[—-j］>x）； //一样的，一直左移直到小于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）,因为这时候的j是已经不大于了x的,p这个位置要放该区间的最小值,j满足,换过去。

（5)
抽签

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

(以下省略,总共101行)
#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;
｝

仔细阅读代码，填写划线部分缺少的内容。

注意：不要填写任何已有内容或说明性文字。

题解:
这个题目是这样的，对于f(int a［],int k，int m,char b［])。
a［] 是每个国家的最多指派人数，k表示当前是哪个国家，m表示还需要派送几个人(可以为负数)。b表示已经派送的人的字符串。
所以这个题目在递归中间的的 第一个循环表示从0~a[i］中让i国选择指派人数，内循环只是向b[］记录的过程。
所以答案是f（a，k+1，m-i，b）. 因为这里i = j 。应该 f(a，k+1，m—j，b）也可以。

(6）
方格填数

如下的10个格子

（如果显示有问题，也可以参看【图1.jpg】）

填入0~9的数字。要求:连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

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

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字.

题解:
1580
深搜+回溯，填完之后在判断是否可以。

#include 〈stdio。h〉  
＃include <math.h>  
int flag[3］［4]； //表示哪些可以填数  
int mpt[3］[4]； //填数  
bool visit［10];  
int ans = 0；  
void init（）   //初始化  
{  
    int i,j；  
    for(i = 0 ; i 〈 3 ； i ++)  
        for（j = 0 ; j 〈 4 ; j ++）  
            flag［i］［j] = 1;  
    flag［0]［0］ = 0；  
    flag[2］[3］ = 0;  
｝  

void Solve（）  
｛  
    int dir［8］[2] = ｛ 0，1，0，—1,1，0，—1，0,1,1，1，—1，-1,1,-1，—1｝;  
    int book = true；  
    for（int i = 0 ； i 〈 3 ； i ++)  
    ｛  
        for（int j = 0 ； j 〈 4； j ++)  
        ｛  
            //判断每个数周围是否满足  
            if(flag[i］[j］ == 0)continue;  
            for（ int k = 0 ; k < 8 ; k ++)  
            {  
                int x,y;  
                x = i + dir［k］[0］;  
                y = j + dir［k］［1];  
                if(x < 0 ｜| x 〉= 3 ｜｜ y < 0 || y >= 4 |｜ flag[x][y］ == 0） continue;  
                if（abs(mpt[x］[y］ - mpt[i][j］) == 1）  book = false；  
            ｝  
        ｝  
    }  
    if（book） ans ++；  
}  

void dfs（int index)  
{  
    int x，y；  
    x = index / 4;  
    y = index ％ 4;  
    if（ x == 3)  
    {  
        Solve（);  
        return；  
    ｝  
    if（flag[x]［y])  
    ｛  
        for(int i = 0 ; i 〈 10 ; i ++）  
        ｛  
            if（!visit[i])  
            ｛  
                visit[i] = true；  
                mpt[x]［y] = i;  
                dfs(index+1）；  
                visit［i] = false；  
            ｝  
        }  
    }  
    else  
    ｛  
        dfs(index+1);  
    ｝  
｝  
int main()  
{  
    init(）；  
    dfs（0）;  
    printf（"%d\n”，ans）;  
    return 0；  
}  

(7)
剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票.
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】,【图3。jpg】中，粉红色所示部分就是合格的剪取。

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

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字.

题解：
这个题目跟上一道题目类似,看来这一届的深搜很火啊。
跟上面一样的套路。

＃include 〈stdio。h>  
＃include <string.h>  
int mpt［3］[4］；  
int mpt_visit[3］［4］；  
int num[6]；   
int have［13］;  
int visit［13]；  
int ans = 0;  
int Count = 0;  

void init()  
｛  
    int k = 1;  
    for（int i = 0 ; i < 3 ; i ++）  
        for(int j = 0 ； j 〈 4 ; j ++）  
        {  
            mpt[i］［j] = k;  
            k ++；  
        ｝  
}  
int dir［4］[2］ = ｛0，1，0,-1，-1，0,1，0};  
//判断五个数是否能连在一起  
void dfs_find（int x，int y）  
{  
    for(int i = 0 ; i < 4 ; i++）  
    ｛  
        int tx，ty；  
        tx = x + dir［i]［0]；  
        ty = y + dir[i］[1]；  
        if(tx < 0 ｜｜ tx 〉= 3 || ty < 0 |｜ ty 〉= 4） continue;  
        if（have[mpt[tx]［ty］] == 0 |｜ mpt_visit［tx］［ty])continue；  
        mpt_visit[tx］［ty］ = 1；  
        Count ++;  
        dfs_find(tx，ty);  
    ｝  
}  

void Solve（）  
｛  
    int i;  
    memset（have，0,sizeof(have)）；  
    memset(mpt_visit，0,sizeof（mpt_visit));  
    for(i = 1； i 〈 6 ; i ++) have［num[i］] = 1;  
    for(i = 0 ; i 〈 12 ; i ++）  
    ｛  
        int x，y;  
        x = i / 4；  
        y = i % 4;  
        if（have[mpt[x]［y]］)  
        {  
            Count = 1；  
            mpt_visit［x][y］ =1；  
            dfs_find（x,y)；  
            break；  
        ｝  
    ｝  
    if（Count == 5）  
    {  
        ans ++;  
    ｝  
}  

//创建5个数的组合  
void dfs_creat（int index)  
{  
    if（index == 6）  
    ｛  
        Solve（);  
        return；  
    }  
    for（int i = num［index-1］ + 1； i < 13 ; i ++)  
    ｛  
        if(！visit［i])  
        {  
            visit［i］ = true;  
            num［index］ = i；  
            dfs_creat（index+1);  
            visit[i] = false;  
        }  
    }  
}  

int main(）  
{  
    init(）；  
    dfs_creat(1)；  
    printf(”％d\n”,ans）;  
    return 0；  
｝  

（8）
四平方和

四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多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

资源约定：
峰值内存消耗 〈 256M
CPU消耗 〈 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入。..” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意： main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 ＃include 〈xxx>， 不能通过工程设置而省略
题解:
一道水题.水的不能在水。
从样例就可以看出来它找的顺序了.
直接对你输入的数字开根号，然后一个一个往下缩，直到下一个数要大于第一个数就停。
然后对剩下的开根号，一直开完就好了，

另外一个快速的方法。用网上的。先把两个平方数能相加的到的数字球出来然后记录。这样我们第三层循环就可以先判断再循环了。

int mpt［5000010］ ={0｝；  //mpt［i］ = 1表示i 能够用两个完全平方数相加而得。  
int n;  
void init（)  
{  
    for(int i = 0 ； i*i <= n ; i ++)  
        for(int j = 0 ； j*j 〈=n ; j ++）  
            if(i*i+j*j <= n） mpt[i＊i+j*j］ = 1;  
｝  
int main()  
{  

    int flag = false；  
    scanf(”％d”，＆n)；  
    init()；  
    for(int i = 0 ; i ＊ i <= n ; i ++）  
    ｛  
        for(int j = 0 ； j * j 〈= n ; j ++)｛  
            if(mpt［n — i＊i - j*j] == 0） continue；   //如果剩下的差用两个完全平方数不能组合出来就不继续  
            for（int k = 0 ; k ＊ k <= n ； k ++)  
            ｛  
                int temp = n - i*i - j*j — k*k；  
                double l = sqrt（(double) temp）;  
                if（l == (int)l )  
                ｛  
                    printf（”%d ％d %d %d\n"，i，j，k，（int)l）;  
                    flag = true;  
                    break；  
                }  
            }  
            if（flag)break；  
        ｝  
        if（flag）break；  
    }  
    return 0;  ｝
（9）
交换瓶子

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

比如有5个瓶子：
2 1 3 5 4

要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5

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

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

输入格式为两行:
第一行： 一个正整数N（N<10000）， 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况.

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

例如,输入：
5
3 1 2 5 4

程序应该输出：
3

再例如，输入：
5
5 4 3 2 1

程序应该输出：
2

题解：
这道题目就是典型的贪心题了。
从最左边的那个下标开始,往右边找最小的数字。
然后从次左边的那个下标开始,找剩余右边的最小的数字然后交换。
这样的复杂度是O(n*n);
会超时。
因为这个题目的编号是1～n；
所以可以用两个数组，一个存输入的数组,一个标识该数应该是在第几个位置。
然后直接一个循环,

#include <cmath〉
#include <iostream>
using namespace std；

const int maxn=1e5+10；

int main（)
{
int num［maxn］,bb[maxn］；
int n，sum=0;
cin〉>n;
for(int i=1；i<=n;++i）
{
cin〉>num[i］;
bb[num[i]］=i;
}
for（int i=1；i〈=n;++i)
｛
if(num［i］==i） continue;
else if（num［i]!=i）
｛
if(i==num[num［i］］) swap（num［i]，num［num[i]])，++sum；
else sum+=2；
｝
｝
cout〈〈sum;
return 0；
}

//这个代码可能还有点BUG.