题目连接:第九届蓝桥杯试题 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 <bits/stdc++.h>
#define maxn 1005
using namespace std;
struct Node{
int x,y;
}S,Next, Now;
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};
bool vis[maxn][maxn];
string str[maxn];
map<int,int> ma;
int n,m;
bool flag;
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(X >= 0 && Y >= 0 && X < n && Y < n && str[X][Y] == '.') return false;
}
return true;
}
bool in(int x,int y){
if(x >= 0 && y >= 0 && x < n && y < n && str[x][y] == '#' && vis[x][y] == false) return true;
return false;
}
void bfs(int x,int y,int pos){
queue<Node> q;
S.x = x;
S.y = y;
q.push(S);
while(!q.empty()){
Now = q.front();
q.pop();
if(str[Now.x][Now.y] == '#' && Check(Now.x, Now.y)){
ma[pos] = 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)){
vis[Next.x][Next.y] = true;
q.push(Next);
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) cin>>str[i];
memset(vis,false,sizeof(vis));
int ans = 0, cnt = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(str[i][j] == '#' && vis[i][j] == false){
bfs(i, j, cnt);
cnt ++;
}
}
}
for(int i=0;i<cnt;i++){
if(ma[i] == 0) ans ++;
}
printf("%d\n", ans);
return 0;
}
第十题:乘积最大
最后一道题我也不会写,当时是随便暴力了一下过了样例就交了,看了一下别人的题解,确实再给我4个小时我也写不出来...
仔细思考你会发现其实最终答案为负数只有两种情况
①k=n,这n个数都是负数并且n是奇数
②k是奇数,并且这n个数都是负数
其它情况下答案一定为正或者0
为什么呢?一个很简单的证明就是如果你结果为负数,那么你一定可以通过少乘一个负数多乘一个正数,或者少乘一个正数多乘一个负数把答案变成正的
然后正数的情况就好办了
一个很完美的方法就是所有负数取绝对值从大到小排序,所有正数从大到小排序
然后暴力负数选多少个,中间取个最大的就行了
但是这样你肯定不能取模,因为取模就错了,然而直接乘会爆long long
熟练的话你可以写个大整数乘法,不过肯定会超时所以要FFT优化乘法
不会FFT怎么办?
还是将所有负数取绝对值从大到小排序,所有正数从大到小排序
然后一个一个取,每次都取当前最大的数
如果最后刚好为整数,那完美直接输出
如果最后为负数就说明你要调整一下,也就是少乘一个负数多乘一个正数,或者少乘一个正数多乘一个负数,这个时候你只要比一下哪个更大就应该ok!
明年再战...