2018年第九届蓝桥杯B组题解
题目连接：第九届蓝桥杯试题 C\JAVA
第一题：第几天
答案：125
很简单的数一数就好了，但是我当时可能没带脑子，按2010年算的124天。
第二题：明码
答案：387420489
按着题目把这些数转换成8字节的二进制数就可以了，负数的二进制是补码。可以自己写个函数实现一下，实际效果图：
还可以用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;
}第三题：乘积尾零
答案：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;
}第四题：测试次数
答案：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]就是答案
二分方法实现代码：
#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搜索一下把起初的每个岛屿都编上号，顺便把可能会被淹没的岛屿标记下来，然后我是倒着再遍历一遍地图，只要有没有完全淹没的岛屿，就让岛屿数--，最后就剩下完全淹没的岛屿数了。还有一种情况就是有人提到的一个岛屿淹没完以后变成了两个岛屿，那么就在这特判一下就好了。
实现代码：
#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!
明年再战...