前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2018年第九届蓝桥杯B组题解

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

作者头像
Ch_Zaqdt
发布2019-01-10 14:43:28
2.9K0
发布2019-01-10 14:43:28
举报
文章被收录于专栏:Zaqdt_ACM

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

第一题:第几天

答案:125

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

第二题:明码

答案:387420489

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

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

实现代码:

代码语言:javascript
复制
#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;
}

第三题:乘积尾零

答案:31

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

实现代码:

代码语言:javascript
复制
#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;
}

第四题:测试次数

答案:19

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

第五题:快速排序

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

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

第六题:递增三元组

可以先对三个数组排序,然后遍历数组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]就是答案

二分方法实现代码:

代码语言:javascript
复制
#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;
}

第七题:螺旋折线

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

第八题:日志统计

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

第九题:全球变暖

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

实现代码:

代码语言:javascript
复制
#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;
}

第十题:乘积最大

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

仔细思考你会发现其实最终答案为负数只有两种情况 ①k=n,这n个数都是负数并且n是奇数 ②k是奇数,并且这n个数都是负数 其它情况下答案一定为正或者0 为什么呢?一个很简单的证明就是如果你结果为负数,那么你一定可以通过少乘一个负数多乘一个正数,或者少乘一个正数多乘一个负数把答案变成正的 然后正数的情况就好办了 一个很完美的方法就是所有负数取绝对值从大到小排序,所有正数从大到小排序 然后暴力负数选多少个,中间取个最大的就行了 但是这样你肯定不能取模,因为取模就错了,然而直接乘会爆long long 熟练的话你可以写个大整数乘法,不过肯定会超时所以要FFT优化乘法 不会FFT怎么办? 还是将所有负数取绝对值从大到小排序,所有正数从大到小排序 然后一个一个取,每次都取当前最大的数 如果最后刚好为整数,那完美直接输出

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

        明年再战...

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年04月02日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档