2016年蓝桥别A组模拟训练

1. 网友年龄

某君新认识一网友。当问及年龄时，他的网友说： “我的年龄是个2位数，我比儿子大27岁, 如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”
请你计算：网友的年龄一共有多少种可能情况？
提示：30岁就是其中一种可能哦. 请填写表示可能情况的种数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

代码：

#include <iostream>

#define FF(a,b) for(a=0;a<b;a++)

#define F(a,b,c) for(a=b;a<c;a++)

#define O printf

#define I scanf

#define MAX (1<<30)+1

#define LEN 1010

using namespace std;

int ans=;

bool isOk(int x){

    int cd=x-;

    if((cd%)*+cd/==x){

        ans++;

        cout<<x<<','<<cd<<endl;

    }

}

int main(){

    int i;

    F(i,,) isOk(i);

    cout<<ans<<endl;

    return ;

}

结果：7

,

,

,

,

,

,

,

--------------------------------

Process exited after 0.5086 seconds with return value

请按任意键继续. . .

用时：3min

2. 生日蜡烛

某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？
请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

代码：

#include <iostream>

#define FF(a,b) for(a=0;a<b;a++)

#define F(a,b,c) for(a=b;a<c;a++)

#define O printf

#define I scanf

#define MAX (1<<30)+1

#define LEN 1010

using namespace std;

int main(){

    int x,n;

    FF(x,)

    FF(n,)

    if((x+(x+n-))*n==)

        cout<<x<<"岁开始，过了"<<n<<"年"<<endl ;

    return ;

}

结果：26

26岁开始，过了8年

--------------------------------

Process exited after 0.5775 seconds with return value

请按任意键继续. . .

用时：5min

3. 方格填数

如下的10个格子

填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

代码：（强行全排列后判断）

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdlib.h>

#define FF(a,b) for(a=0;a<b;a++)

#define F(a,b,c) for(a=b;a<c;a++)

#define O printf

#define I scanf

#define MAX (1<<30)+1

#define LEN 1010

using namespace std;

int ans=;

int p[]={MAX,,,,,,,,,,,MAX};

void judge(){

    int i,j;

    FF(i,){    //竖向比较

        FF(j,){

            if(abs(p[i*+j]-p[i*+j+])==) return;

        }

    }

    FF(i,){    //竖向比较

        FF(j,){

            if(abs(p[i*+j]-p[i*+j+])==) return;

        }

    }

    FF(i,){    //正对角线

        F(j,,){

            if(abs(p[i*+j]-p[i*+j+])==) return;

        }

    }

    FF(i,){    //副对角线

        FF(j,){

            if(abs(p[i*+j]-p[i*+j+])==) return;

        }

    }

    ans++;

}

int main(){

    do{

        judge()    ;

    }while(next_permutation(p+,p+));

    cout<<ans<<endl;

    return ;

}

结果：1580


--------------------------------

Process exited after 0.7154 seconds with return value

请按任意键继续. . .

用时：约30min

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 + ;

    int x = a[p];

    while(){

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

        quicksort(a,q+,r);

    }

}

int main()

{

    int i;

    int a[] = {,,,,,,,,,,,};

    int N = ;

    quicksort(a, , N-);

    for(i=; i<N; i++) printf("%d ", a[i]);

    printf("\n");

    return ;

}

填写：

swap(a,j,p)

5. 消除尾一

下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0
如果最后一位是0，则原数字保持不变。
如果采用代码中的测试数据，应该输出：

  ->

  ->

请仔细阅读程序，填写划线部分缺少的代码。

#include <stdio.h>

void f(int x)

{

    int i;

    for(i=; i<; i++) printf("%d", (x>>(-i))&);

    printf("   ");

    x = _______________________;   

    for(i=; i<; i++) printf("%d", (x>>(-i))&);

    printf("\n");

}

int main()

{

    f();

    f();

    return ;

}

我的答案是 (-(~x))&x

标准答案是 x&(x+1)

6. 寒假作业

现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

计算次数13！，编码复杂度低但时间复杂度高的算法：（用时255秒）

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdlib.h>

#define FF(a,b) for(a=0;a<b;a++)

#define F(a,b,c) for(a=b;a<c;a++)

#define O printf

#define I scanf

#define MAX (1<<30)+1

#define LEN 1010

using namespace std;

int p[]={,,,,,,,,,,,,} ;

int ans;

void judge(){

    if(p[]+p[]==p[] && p[]-p[]==p[] &&  p[]%p[]== && p[]/p[]==p[] && p[]*p[]==p[] ){

        puts("ok");

        ans++;

    }

}

int main(){

    do{

        judge()    ;

    }while(next_permutation(p,p+));

    cout<<ans<<endl;

    return ;

}

剪枝优化后，执行时间为1.4秒：

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdlib.h>

#define FF(a,b) for(a=0;a<b;a++)

#define F(a,b,c) for(a=b;a<c;a++)

#define O printf

#define I scanf

#define MAX (1<<30)+1

#define LEN 20

using namespace std;

int num[LEN];

int used[LEN];

int ans=;

void dfs(int step) {

    if(step==){

        if(num[]%num[]) return;

        if(num[]/num[]!=num[]) return;

        ans++;

        return;

    }

    if(step==)

        if(num[]+num[]!=num[]) return;

    if(step==)

        if(num[]-num[]!=num[]) return;

    if(step==)

        if(num[]*num[]!=num[]) return;

    for(int i=;i<=;i++) if(!used[i]){

        used[i]=;

        num[step]=i;

        dfs(step+);

        used[i]=;

    }

}

int main(){

    dfs();

    cout<<ans<<endl;

    return ;

}

巴特西

2016年蓝桥别A组模拟训练

1. 网友年龄

2. 生日蜡烛

3. 方格填数

4. 快速排序

5. 消除尾一

6. 寒假作业

最新文章

热门文章