第九届蓝桥杯C/C++组省赛解题与反思

第九届蓝桥杯C/C++组省赛解题

第一题 第几天

这个题目真是直接用计算器的日期统计或者excel，最不济使用日历数也行
答案：125

第二题：明码

这个题目真是4个小时去看了不下于三遍，就是没看懂，形成一个汉字又讲是数字，
今天放有机会知道原来问题在汉字中：九的九次方是多少？
答案:387420489

#include<stdio.h>
#include<string.h>
#include<math.h>
int arr[8];
void f(int x){
    int i=0;
    int x1;
    x1=fabs(x);
    while(x1!=0){
        arr[i]=x1%2;
        x1/=2;
        i++;
    }
    if(x<0){
        for(i=0; i<=7; i++){
            if(arr[i]==1 && i<7){
                for(int j=i+1; j<=7; j++){
                    if(arr[j]==0)   arr[j]=1;
                    else arr[j]=0;
                }
                break;
            }
        }
    }
}

int main ()
{
    int a[32],i,j,k;
    for(k=0; k<=9; k++){

        for(i=0; i<=31; i++)
            scanf("%d",&a[i]);
        for(i=0; i<=31; i++){
            f(a[i]);
            for(j=7; j>=0; j--)
                if(arr[j]==1)   printf("%d",arr[j]);
                else printf(" ");
            memset(arr,0,sizeof(arr));
            if(i%2==1)  printf("\n");
        }
    }
    return 0;
} 

第三题：乘积尾零

这是一题没想对会极度消耗时间的题目，比赛使在这个题上耗费了一个多小时还是错了。问了大佬的思路才知道，直接找2，5的个数就能知道有多少个零了，思想上的分水岭
答案：31

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int x,t=100,c=0,a=0;
    while(t--){
        scanf("%d",&x);
        while(x%2==0){
            a++;
            x/=2;
        }
        while(x%5==0){
            c++;
            x/=5;
        }
    }
    int num=min(a,c);
    printf("%d %d %d\n",a,c,num);
    return 0;
 } 

第四题：测试次数

弱鸡当时只想到二分法三部手机拿来摔……有人讲正确的是使用动态规划，状态dp[i][j],需要多少次测试``状态转移方程假设在k层进行测试手机，手机碎了，手机减少的情况下那么范围变成到k-1，此时的步数为dp[i-1][k-1]+1
如果手机没碎，范围变成k以上的了此时的因为dp[i][j-k]+1
dp[i][j]=min(dp[i][j],max(dp[i-1][j-1]+1,dp[i][j-k]+1))

#include<cstdio>
#include<algorithm>
#include<string.h>
#define INF 0x3f3f3f3f
using namespace std;
int dp[55][1005];
void call(){
    memset(dp,INF,sizeof(dp));
    for(int i=1; i<=55; i++)
        {
            dp[i][0]=0;
            dp[i][1]=1;
        }
        for(int i=2; i<=1005; i++)
            dp[1][i]=i;
    for(int i=2; i<=55; i++)
        for(int j=2; j<=1005; j++)
            for(int k=1; k<j; k++)
                dp[i][j]=min(dp[i][j],max(dp[i-1][k-1]+1,dp[i][j-k]+1));

}
int main ()
{
    int m,n;
    call();
    scanf("%d%d",&m,&n);
    printf("%d",dp[m][n]);
    return 0;
 } 

第五题：快排

答案：a,i+1,r,k-i+l-1
想起比赛时不是这个答案，但数组输出时排后的，想不起来当时写的了

第六题：递增三元组

排序暴力枚举输出

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int n,a[100005],b[100005],c[100005];
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    for(int i=0;i<n;i++) scanf("%d",&c[i]);
    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    int num=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            for(int k=0; k<n; k++){
                    if(a[i]<b[j] && b[j]<c[k])  num++;
            }   
    printf("%d\n",num);
    return 0;
}

第七题：螺旋折线

比赛时时间没够，只把递归方程写出来后面的没写

-