第七届蓝桥杯大赛个人赛省赛C语言A组题目答案

时间:2022-09-10 08:53:01

第七届省赛题目

注意

  • 简单的题目,只是写了一个函数实现功能,对于复杂的题目,会给出全部代码

1

  • 题目

    网友年龄

    某君新认识一网友。
    当问及年龄时,他的网友说:
    “我的年龄是个2位数,我比儿子大27岁,
    如果把我的年龄的两位数字交换位置,刚好就是我儿子的年龄”

    请你计算:网友的年龄一共有多少种可能情况?

    提示:30岁就是其中一种可能哦.
  • 代码

    void test01()
    {
    int num = 0;
    for(int i=0;i<=9;i++)
    {
    for(int j=0;j<i;j++)
    {
    if( 9*(i-j) == 27 )
    {
    num++;
    //printf("%d, %d\n", 10*i+j, 10*j+i);
    }
    }
    }
    printf("num : %d\n", num);
    }

2

  • 题目

    生日蜡烛

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

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

    请问,他从多少岁开始过生日party的?
  • 注意:这道题不需要进行两层循环即可。

  • 代码

    void test02()
    {
    int sum = 0;
    int si = 0, ei = 0;
    int goal = 236;
    while( sum != goal )
    {
    if( sum < goal )
    {
    ei++;
    sum += ei;
    }
    else if( sum > goal )
    {
    sum -= si;
    si++;
    }
    }
    printf("si : %d, ei : %d\n", si, ei);
    }

3

  • 题目

    方格填数

    如下的10个格子
    +--+--+--+
    | | | |
    +--+--+--+--+
    | | | | |
    +--+--+--+--+
    | | | |
    +--+--+--+

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

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

    一共有多少种可能的填数方案?
  • 思路:DFS

  • 代码

    #include <stdio.h>

    int num[3][4];
    int sum = 0;

    bool isFilled[10];

    int abs(int n)
    {
    return n >= 0 ? n : -n;
    }

    // 在num[r][c]处防止i符合规则则返回true
    bool isLegal(int r, int c, int val)
    {
    if( r == 0 && c == 0 )
    return true;
    else if( r == 0 )
    return abs(val-num[r][c-1]) > 1;
    else if( c == 0 )
    return abs(val-num[r-1][c]) > 1 && abs(val-num[r-1][c+1])>1;
    else if( c != 3 )
    return abs(val-num[r][c-1]) > 1 && abs(val-num[r-1][c]) > 1 && abs(val-num[r-1][c-1])>1 && abs(val-num[r-1][c+1])>1;
    else
    return abs(val-num[r][c-1]) > 1 && abs(val-num[r-1][c]) > 1 && abs(val-num[r-1][c-1])>1;
    }

    void dfs(int r, int c)
    {
    if( r == 2 && c == 3 )
    {
    sum++;
    return;
    }

    for(int i=0;i<=9;i++)
    {
    if( !isFilled[i] && isLegal(r, c, i) )
    {
    num[r][c] = i;
    isFilled[i] = true;
    dfs( r + (c+1)/4, (c+1)%4 );
    isFilled[i] = false;
    }
    }

    }

    int main()
    {
    num[0][0] = -10;
    num[2][3] = -10;
    for(int i=0;i<10;i++)
    isFilled[i] = false;
    dfs( 0, 1 );
    printf("%d\n", 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);
    while(a[--j]>x);
    if(i>=j) break;
    swap(a,i,j);
    }
    swap( a, p, 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;
    }

5

  • 题目

    消除尾一

    下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0
    如果最后一位是0,则原数字保持不变。

    如果采用代码中的测试数据,应该输出:
    00000000000000000000000001100111 00000000000000000000000001100000
    00000000000000000000000000001100 00000000000000000000000000001100
  • 代码

    #include <stdio.h>

    void f(int x)
    {
    int i;
    for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
    printf(" ");

    x = x&(x+1);

    for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
    printf("\n");
    }

    int main()
    {
    f(103);
    f(12);
    return 0;
    }

6

  • 题目

    寒假作业

    现在小学的数学题目也不是那么好玩的。
    看看这个寒假作业:

    □ + □ = □
    □ - □ = □
    □ × □ = □
    □ ÷ □ = □

    (如果显示不出来,可以参见【图1.jpg】)

    每个方块代表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

    就算两种解法。(加法,乘法交换律后算不同的方案)

    你一共找到了多少种方案?
  • 代码

    #include <stdio.h>
    bool isUsed[14];
    int num[4][3];
    int sum = 0;

    // 判断第几行最后一个值填入这个是否正确
    bool right( int r, int val )
    {
    switch(r)
    {
    case 0:
    return num[r][0] + num[r][1] == val;
    break;
    case 1:
    return num[r][0] - num[r][1] == val;
    break;
    case 2:
    return num[r][0] * num[r][1] == val;
    break;
    case 3:
    return val * num[r][1] == num[r][0];
    break;
    default:
    return false;
    }
    }

    void dfs( int r, int c )
    {
    if( r == 4 )
    {
    sum++;
    if( sum <= 3 )
    {
    for(int i=0;i<4;i++)
    {
    for(int j=0;j<3;j++)
    printf("%4d", num[i][j]);
    printf("\n");
    }
    }
    printf("\n");
    return;
    }

    for(int i=1;i<=13;i++)
    {
    // 该数没有被使用
    if( !isUsed[i] )
    {
    isUsed[i] = true;
    // 是计算的结果,则需要判断一下
    if( c != 2 || right(r, i) )
    {
    num[r][c] = i;
    dfs( r+(c+1)/3, (c+1)%3 );
    }

    isUsed[i] = false;
    }
    }
    }

    int main()
    {
    for(int i=1;i<14;i++)
    isUsed[i] = false;
    dfs( 0, 0 );
    printf("%d\n", sum);
    }

7

  • 题目

    剪邮票

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

    请你计算,一共有多少种不同的剪取方法。
  • 注:有人用dfs求解,我没怎么看懂23333,参考链接在这:http://blog.csdn.net/kavu1/article/details/51130029

  • 代码

    #include <stdio.h>

    bool map[3][4];
    int sum = 0;

    int idx[5];

    int abs( int a )
    {
    return a >= 0 ? a : -a;
    }

    bool connect(int a, int b)
    {
    int r1 = a/4, c1 = a%4;
    int r2 = b/4, c2 = b%4;
    return abs(r1-r2)+abs(c1-c2) == 1;
    }

    bool match()
    {
    bool ret = false;
    for(int i=0;i<5;i++)
    {
    ret = false;
    for(int j=0;j<5;j++)
    {
    if( connect(idx[i],idx[j]) )
    {
    ret = true;
    break;
    }
    }
    if( !ret ) // 如果无法连接,则退出并返回
    break;
    }
    return ret;

    }

    int main()
    {

    // 随机选取5个点,看是否能够
    for(int i1=0;i1<12;i1++)
    {
    idx[0] = i1;
    for(int i2=i1+1;i2<12;i2++)
    {
    idx[1] = i2;
    for( int i3=i2+1;i3<12;i3++ )
    {
    idx[2] = i3;
    for(int i4=i3+1;i4<12;i4++)
    {
    idx[3] = i4;
    for(int i5=i4+1;i5<12;i5++)
    {
    idx[4] = i5;
    if( match() )
    {
    sum++;
    }
    }
    }
    }
    }
    }
    printf("ans : %d\n", sum);
    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
  • 代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    int num[5];
    int goal = 0;

    int number = 0;

    void dfs(int n, int sum)
    {
    if( number != 0 )
    exit(0);
    if( sum > goal || n > 5 )
    return;
    if( n == 5 )
    {
    if( sum == goal )
    {
    number++;
    for( int i=1;i<5;i++ )
    printf("%d ", num[i]);
    printf("\n");
    }
    return;
    }
    // 这是不等于5的情况
    if( sum == goal )
    return;

    num[n] = num[n-1];
    int tmp = sum;
    while( tmp < goal )
    while( tmp < goal )
    {
    tmp = sum+num[n]*num[n];
    dfs( n+1, tmp );
    num[n]++;
    }
    }

    int main()
    {
    scanf("%d", &goal);
    dfs(1, 0);

    return 0;
    }

9

  • 题目

    密码脱落

    X星球的考古学家发现了一批古代留下来的密码。
    这些密码是由A、B、C、D 四种植物的种子串成的序列。
    仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
    由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

    你的任务是:
    给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

    输入一行,表示现在看到的密码串(长度不大于1000)
    要求输出一个正整数,表示至少脱落了多少个种子。

    例如,输入:
    ABCBA
    则程序应该输出:
    0

    再例如,输入:
    ABDCDCBABC
    则程序应该输出:
    3
  • 代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <string.h>

    char s[1020];
    int min_len = 9999;
    int s_len = 0;

    void dfs(int l, int r, int len)
    {
    if( l>=r )
    {
    if( min_len > len )
    min_len = len;
    return;
    }
    // 对称则继续检测
    if( s[l] == s[r] )
    dfs( l+1, r-1, len );
    // 2种情况
    else
    {
    dfs(l+1, r, len+1);
    dfs(l, r-1, len+1);
    }

    }


    int main()
    {
    gets( s );
    s_len = strlen( s );

    dfs( 0, s_len-1, 0 );
    printf("min len : %d\n", min_len);
    return 0;
    }

10

  • 题目

    最大比例

    X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
    并且,相邻的两个级别间的比例是个固定值。
    也就是说:所有级别的奖金数构成了一个等比数列。比如:
    16,24,36,54
    其等比值为:3/2

    现在,我们随机调查了一些获奖者的奖金数。
    请你据此推算可能的最大的等比值。

    输入格式:
    第一行为数字 N (0<N<100),表示接下的一行包含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
  • 参考链接:http://www.aichengxu.com/cyvyan/6607933.htm
  • 思路:这道题其实是找出所有相邻数的最大公约数的最大公约数,首先对数据进行排序,然后去除重复的数字,最后求出相邻数据被的最大公约数除过之后的数。原文的链接中的做法无法对16,24,81的测试数据正确求解(我认为正确的解为3/2,原文链接代码得到的是9/4
  • 注意:long long的数据输入与输出需要使用%lld,否则在输出时,会影响后面数据的输出,在输入时,对于很大的数据,无法读取。
  • 代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <string.h>

    int N;
    long long bonus[100];
    long long res[100], p1[100], p2[100];
    long long num1, num2;

    void sort()
    {
    long long tmp;
    for(int i=0;i<N;i++)
    {
    for(int j=i+1;j<N;j++)
    {
    if( bonus[j] < bonus[i] )
    {
    tmp = bonus[j];
    bonus[j] = bonus[i];
    bonus[i] = tmp;
    }
    }
    }
    }

    void removeSame()
    {
    int k = 1;
    res[0] = bonus[0];
    for(int i=1;i<N;i++)
    {
    if( bonus[i] == bonus[i-1] )
    continue;
    res[k++] = bonus[i];
    }
    N = k;

    }

    long long gcd(long long a, long long b)
    {
    long long t;
    if( b == 0 )
    return a;
    else
    return gcd( b, a%b );
    }

    long long max(long long a, long long b)
    {
    return a >= b ? a : b;
    }

    long long min(long long a, long long b)
    {
    return a <= b ? a : b;
    }

    void solve()
    {
    int tmp;
    int k;
    if( N == 1 )
    {
    num1 = 1;
    num2 = 1;
    return;
    }
    else if( N == 2 )
    {
    tmp = gcd( res[1], res[0] );
    num1 = res[1] / tmp;
    num2 = res[0] / tmp;
    return;
    }
    else
    {
    k = 0;
    long long g,g1,g2;
    for(int i=1;i<N;i++)
    {
    tmp = gcd( res[i], res[i-1] );
    p1[k] = res[i] / tmp;
    p2[k] = res[i-1] / tmp;
    k++;
    }
    }
    double t = 999999; // 存储最小的公约数
    long long t1, t2, tt1, tt2, max_tmp, min_tmp;
    long long max_p1, max_p2, min_p1, min_p2;
    for(int i=0;i<N-1;i++)
    {
    for(int j=i+1;j<N-1;j++)
    {
    if( p1[i]*p2[j] == p1[j]*p2[i] )
    {
    t1 = p1[i];
    t2 = p2[i];
    }
    else
    {
    max_p1 = max( p1[i], p1[j] );
    max_p2 = max( p2[i], p2[j] );

    min_p1 = min( p1[i], p1[j] );
    min_p2 = min( p2[i], p2[j] );

    max_tmp = max_p1;
    min_tmp = min_p1;
    max_p1 = max( min_tmp, max_tmp/min_tmp );
    min_p1 = min( min_tmp, max_tmp/min_tmp );

    max_tmp = max_p2;
    min_tmp = min_p2;
    max_p2 = max( min_tmp, max_tmp/min_tmp );
    min_p2 = min( min_tmp, max_tmp/min_tmp );

    t1 = gcd( max_p1, min_p1 );
    t2 = gcd( max_p2, min_p2 );

    }

    // 在之前的程序中可知p1>p2
    if( 1.0*t1/t2 < t )
    {
    t = 1.0*t1/t2;
    tt1 = t1;
    tt2 = t2;
    }
    }
    }
    tmp = gcd(tt1, tt2);
    num1 = tt1 / tmp;
    num2 = tt2 / tmp;
    }


    int main()
    {
    scanf("%d", &N);
    for(int i=0;i<N;i++)
    scanf("%lld", &bonus[i]);
    sort();
    removeSame();

    solve();

    printf("%lld/%lld\n", num1, num2);
    return 0;
    }