2018年第九届蓝桥杯B组题解

时间:2022-09-10 14:55:47


题目连接:第九届蓝桥杯试题 C\JAVA


第一题:第几天

2018年第九届蓝桥杯B组题解

答案:125

很简单的数一数就好了,但是我当时可能没带脑子,按2010年算的124天。


第二题:明码

2018年第九届蓝桥杯B组题解

答案:387420489

按着题目把这些数转换成8字节的二进制数就可以了,负数的二进制是补码。可以自己写个函数实现一下,实际效果图:

2018年第九届蓝桥杯B组题解

2018年第九届蓝桥杯B组题解

还可以用bitset,将一个数转换成8位的二进制数,不足用0补位,然后再将bitset数转换成string然后输出。

实现代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    string str1,str2;
    while(cin>>n>>m){
        bitset<8> b(n);
        str1 = b.to_string();
        int len1 = str1.length();
        for(int i=0;i<len1;i++){
          if(str1[i] == '0')printf(" ");
          else printf("*");
        }
        bitset<8> c(m);
        str2 = c.to_string();
        int len2 = str2.length();
        for(int i=0;i<len2;i++){
          if(str2[i] == '0')printf(" ");
          else printf("*");
        }
        printf("\n");
    }
    return 0;
}


第三题:乘积尾零

2018年第九届蓝桥杯B组题解

答案:31

之前计蒜客的第五次模拟赛有道题是求n!末尾有多少个0,那道题就是求1-n的因子里有多少个5。因为想要出现0,只有当有2和5出现的时候,才会出现0,所以我们只需要求出这么多数,能分解出多少个2和5,小的那个数就是结果。

实现代码:

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
  int n;
  int num1 = 0;
  int num2 = 0;
  while(cin>>n){
    while(1){
      if(n % 2 == 0){
        n /= 2;
        num1++;
      }
       else if(n % 5 == 0){
        n /= 5;
        num2++;
      }
      else {
        break;
      }
    }
  }
  printf("%d\n",num1>num2?num2:num1);
  return 0;
}

第四题:测试次数

2018年第九届蓝桥杯B组题解

答案:19

这是一道谷歌的面试题,应该用dp而不是二分。谷歌面试题:丢鸡蛋

第五题:快速排序

2018年第九届蓝桥杯B组题解

答案:a,i+1,r,k-(i-l+1)

虽然填写别的答案也能过样例,但是这道题的要求是时间复杂度为O(n)。

第六题:递增三元组

2018年第九届蓝桥杯B组题解

可以先对三个数组排序,然后遍历数组b,查找a数组中有多少个小于b[i]的,c数组中有多少个大于b[i]的。

还有就是可以直接线性求出答案,即a[x]表示第一个序列中,有多少个数字等于x,b[],c[]同理那么有:
for i = 100000 → 0
c[i] = c[i]+c[i+1]
b[i] = b[i]*c[i+1]+b[i+1]
a[i] = a[i]*b[i+1]+a[i+1]

最后a[0]就是答案

二分方法实现代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int a[MAXN],b[MAXN],c[MAXN];
int n,sum;

int main()
{
  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);
  sum = 0;
  for(int i=0;i<n;i++){
    int x = (lower_bound(a,a+n,b[i]) - a);
    int y = (n - (upper_bound(c,c+n,b[i]) - c));
    sum += x*y;
  }
  printf("%d\n",sum);
  return 0;
}


第七题:螺旋折线

2018年第九届蓝桥杯B组题解

2018年第九届蓝桥杯B组题解

这道题就把四个象限分一下,然后找规律递推公式就OK了。


第八题:日志统计

2018年第九届蓝桥杯B组题解

这道题就是模拟一下,按id和时间排序,把相同的id,以时间递增的情况排序,然后暴力枚举每个id的赞数,当在规定的时间范围内赞数大于k,标记一下,然后递增输出id就好了。我也不知道我写的对不对,所以就不上代码了。。。


第九题:全球变暖

2018年第九届蓝桥杯B组题解

       这道题应该会有不少人和我一样理解成了最后还剩多少个岛吧。暴力杯变成了阅读理解杯....对于这道题,我们可以用bfs搜索一下把起初的每个岛屿都编上号,顺便把可能会被淹没的岛屿标记下来,然后我是倒着再遍历一遍地图,只要有没有完全淹没的岛屿,就让岛屿数--,最后就剩下完全淹没的岛屿数了。还有一种情况就是有人提到的一个岛屿淹没完以后变成了两个岛屿,那么就在这特判一下就好了。

实现代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct Node{
  int x,y;
  int num;
}Now,Next,S;
char MAP[1005][1005];
int vis[1005][1005];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n,sum;

bool in(int x,int y){
  if(x >= 0 && y >= 0 && x < n && y < n)return true;
  return false;
}

bool Check(int x,int y){
  for(int i=0;i<4;i++){
    int X = x + dir[i][0];
    int Y = y + dir[i][1];
    if(MAP[X][Y] == '.' && in(X,Y))return true;
  }
  return false;
}

void bfs(){
  queue<Node> q;
  S.num = sum;
  q.push(S);
  while(!q.empty()){
    Now = q.front();
    q.pop();
    if(Check(Now.x,Now.y)){
      vis[Now.x][Now.y] = 1;
    }
    for(int i=0;i<4;i++){
      Next.x = Now.x + dir[i][0];
      Next.y = Now.y + dir[i][1];
      if(in(Next.x,Next.y) && MAP[Next.x][Next.y] == '#' && vis[Next.x][Next.y] != 1){
        if(vis[Next.x][Next.y] == 0)vis[Next.x][Next.y] = 2;
        Next.num = Now.num;
        q.push(Next);
      }
    }
  }
  sum++;
  return ;
}

int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%s",MAP[i]);
  }
  memset(vis,0,sizeof(vis));
  sum = 0;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(MAP[i][j] == '#'){
        if(vis[i][j] != 0)continue;
        S.x = i;
        S.y = j;
        bfs();
      }
    }
  }
  for(int i=n-1;i>=0;i--){
    for(int j=n-1;j>=0;j--){
      if(MAP[i][j] == '#' && vis[i][j] == 2){
        sum--;
      }
    }
  }
  printf("%d\n",sum>0?sum:0);
  return 0;
}


第十题:乘积最大

2018年第九届蓝桥杯B组题解


最后一道题我也不会写,当时是随便暴力了一下过了样例就交了,看了一下别人的题解,确实再给我4个小时我也写不出来...

仔细思考你会发现其实最终答案为负数只有两种情况
①k=n,这n个数都是负数并且n是奇数
②k是奇数,并且这n个数都是负数
其它情况下答案一定为正或者0
为什么呢?一个很简单的证明就是如果你结果为负数,那么你一定可以通过少乘一个负数多乘一个正数,或者少乘一个正数多乘一个负数把答案变成正的

然后正数的情况就好办了
一个很完美的方法就是所有负数取绝对值从大到小排序,所有正数从大到小排序
然后暴力负数选多少个,中间取个最大的就行了
但是这样你肯定不能取模,因为取模就错了,然而直接乘会爆long long
熟练的话你可以写个大整数乘法,不过肯定会超时所以要FFT优化乘法
不会FFT怎么办?
还是将所有负数取绝对值从大到小排序,所有正数从大到小排序
然后一个一个取,每次都取当前最大的数
如果最后刚好为整数,那完美直接输出

如果最后为负数就说明你要调整一下,也就是少乘一个负数多乘一个正数,或者少乘一个正数多乘一个负数,这个时候你只要比一下哪个更大就应该ok!


        明年再战...