2018年蓝桥杯省赛题解（无E、J题）

历届真题可直接在官网下载，链接：蓝桥杯大赛历届真题

A：第几天

31+29+31+30+4 = 125

B：明码

十进制转二进制，对于正数，就是不断模2

对于负数，如-128，其二进制取反即为127，于是可以令abs(n)-1，然后再将1和0互换

// 方便查看结果，`1`替换为`*`，`0`替换为`-`
string solve(int n){    //正数的十进制转二进制
	string s = "";
	while(n){
		if(n % 2 == 0){
			s = "-" + s;
		}else{
			s = "*" + s;
		}
		n /= 2;
	}
	while(s.length() != 8){ //首位补0
		s = "-" + s;
	}
	return s;
}
string change(string s){    //各位上的1和0互换
	for(int i = 0; i < s.length(); ++i){
		if(s[i] == '*')
			s[i] = '-';
		else
			s[i] = '*';
	}
	return s;
}
int main(){
	for(int k = 0; k < 10; ++k){
		for(int j = 0; j < 32; ++j){
			int n;
			string ss = "";
			scanf("%d", &n);
			if(n < 0){
				ss = solve(abs(n) - 1); //取反
				ss = change(ss);    //再反过来
			}else{
				ss = solve(n);
			}
			if(j % 2 == 1)
				cout << ss << endl;		
			else
				cout << ss;
		}
		cout << endl;
	}
	return 0;
}

C：乘积尾零

31
分析

只有5*2得10，能构成多少组5和2，乘积的末尾就增加多少个0
若某个数为5的倍数，记录它能提供多少个5
若某个数为2的倍数，记录它能提供多少个2
最后取两个统计量的较小值，即构成的组数

int k = 100, num1 = 0, num2 = 0;
while(k){
	int n;
	scanf("%d", &n);
	while(n % 2 == 0){
		n /= 2;
		num1++;
	}
	while(n % 5 == 0){
		n /= 5;
		num2++;
	}
	k--;
}
cout << min(num1, num2);

D：测试次数

dp[i] [j]表示运气最差条件下，i层楼j部手机最多的测试次数

第k层测试：

未摔坏，去上一层测试 dp[i] [j]= dp[i-k] [j] +1

摔坏，去下一层测试 dp[i] [j]= dp[k-1] [j-1] +1

dp[3] [2] = max(dp[1] [1], dp[1] [2]) + 1

4, 2 1,1 2,2 2,1 1,2

dp[i] [j]= max(dp[k-1] [j-1], dp[i-k] [j])+1 , 1< k< i

	1	2	3
1	1	1	1
2	2	2	2
3	3
4	4
5	5

int dp[1005][5];
for(int i = 1; i <= 1000; ++i){
	dp[i][1] = i;
}
dp[1][2] = 1;
dp[1][3] = 1;
dp[2][2] = 2;
dp[2][3] = 2;
for(int j = 2; j <= 3; ++j){
	for(int i = 3; i <= 1000; ++i){
		int minn = 0x3f3f3f;
		for(int k = 2; k < i; ++k){
			minn = min(minn, max(dp[k-1][j-1], dp[i-k][j]));
		}
		dp[i][j] = minn + 1;
	}
}
cout << dp[1000][3];

F：递增三元组

题目来源：·【Acwing】·递增三元组
分析

遍历数组B[]，分别将数组 A[]、C []从小到大排序
二分数组 A[]查找小于 B[i]的个数，二分数组 C[]查找大于 B[i]的个数，相乘累加即可

***注：
如序列m[]: 1 2 3 3 4
c++提供的lower_bound(m, m+5, 3)-m查找小于等于3的位置，返回下标2
c++提供的upper_bound(m, m+5, 3)-m查找大于3的位置，返回下标4

const int maxn = 1e5 + 5;
int n;
ll a[maxn], b[maxn], c[maxn];

int solve(){
	ll ans = 0;
	sort(a, a+n);
	sort(c, c+n);
	for(int i = 0; i < n; ++i){
		//cout << lower_bound(a, a+n, b[i])-a << upper_bound(c, c+n, b[i])-c<<endl;
		ans += (lower_bound(a, a+n, b[i])-a) * (n - (upper_bound(c, c+n, b[i])-c));
	}
	return ans;
}

G：螺旋折线

题目来源：·【Acwing】·螺旋折线
分析

第一次看到这图就想到：折线内部构成了一个个正方形
如求(-3, -2)点构成的折线，内部可看作边长为8* 1的正方形、8* 2的正方形

于是内部的折线长可通过等差数列求得，最外层的折线长可以分情况求得（正方形所在的左、上、右、下）
——————————————完整代码————————————————

#include <iostream>
#include <algorithm>
#include <cstdio>
typedef long long ll;
using namespace std;

int main(){
	ll x, y;
	scanf("%lld%lld", &x, &y);
	ll ans = 0;
	ll t = max(abs(x), abs(y)) - 1;
	ans += t*(t+1)*4;		//等差数列8*n*(n+1)/2
	cout << ans << endl;
	if(-x - 1 == t && x == y){	//第三象限x=y的点
		ans += 8*-x;
	}else if(-x - 1 == t){	//左
		ans += (y - x);
	}else if(y - 1 == t){	//上
		ans += (x + y + 2*y);
	}else if(x - 1 == t){	//又
		ans += (x - y + 4*x);
	}else{					//下
		ans += (-y - x + 6*-y);
	}
	printf("%lld\n", ans);
	return 0;
}

H：日志统计

题目来源：·【Acwing】·日志统计
分析

典型的一道尺取法题目
front、tail包含了区间d内的日志，tail不断后移，若范围超出d，则front后移；反之，则front不变
因为id的个数最多为$10^5$，而n的规模最大为$10^5$，若使用结构体，内部要使用vector

***注：本题尺取时要对日志时间排序
——————————————完整代码————————————————

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int d, k;
const int maxn = 1e5 + 5;
struct note{
	vector<int> b;
	int ans;
}a[maxn];
void solve(){
	for(int i = 0; i < maxn; ++i){
		if(a[i].b.size() == 0){
			continue;
		}
		sort(a[i].b.begin(), a[i].b.end());
		int front = 0;
		a[i].ans = 0;
		for(int j = 0; j < a[i].b.size(); ++j){	 //尺取a[i].b
			int tail = j;
			if(a[i].b[tail] - a[i].b[front] < d){ //在范围内，累加即可
				a[i].ans++;
				if(a[i].ans >= k){
					cout << i << endl;
					break;
				} 
				continue;
			}						//不在范围内，front后移
			while(a[i].b[tail] - a[i].b[front] >= d){ 
				front++;
				a[i].ans--;
			}
			a[i].ans++;
		}
	}
}
int main(){
	int n;
	scanf("%d%d%d", &n, &d, &k);
	while(n!=0){
		int ts, id;
		scanf("%d%d", &ts, &id);
		a[id].b.push_back(ts);
		n--;
	}
	solve();
	return 0;
}

I：全球变暖

题目来源：·【Acwing】·全球变暖
分析

只有周围有’.’的陆地都要被淹没，求有多少岛屿会被淹没
预先算出有多少个岛屿并不难，bfs或dfs均可，扫描一次，即可遍历到整个岛屿

关于淹没，这里有一个很巧的方法：

在之前扫描的过程，记录陆地（total），同时记录要被淹没的（cnt）
若这个岛屿中total == cnt，则所有的陆地被淹没，ans++

扫描结束后，ans即为淹没的岛屿数
——————————————dfs完整代码————————————————

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1005;
int n;
int total = 0, cnt = 0;
char a[maxn][maxn];		//记录陆地
bool b[maxn][maxn];		//记录可淹没的陆地
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void init(){	//初始化，只有a[i][j]=='#'并且四周有'.'才标记为true
	fill(b[0], b[0]+maxn*maxn, false);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(a[i][j] == '#'){
				for(int k = 0; k < 4; ++k){
					int x = i + dx[k];
					int y = j + dy[k];
					if(a[x][y] == '.'){
						b[i][j] = true;
					}
				}
			}
		}
	}
}
void dfs(int x, int y){	//遍历一块岛屿的所有陆地
	a[x][y] = '.';	//走过的点不在重复走了
	total++;
	if(b[x][y]){
		cnt++;
	}
	for(int i = 0; i < 4; ++i){
		int tx = x + dx[i];
		int ty = y + dy[i];
		if(tx < 0 || ty < 0 || tx >= n || ty >= n || a[tx][ty] == '.'){
			continue;
		}
		dfs(tx, ty);
	}
}
int main(){
	char ch;
	scanf("%d", &n);
	getchar();
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			scanf("%c", &a[i][j]);
		}
		getchar();
	}
	init();
	int ans = 0;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			total = 0;
			cnt = 0;	//提前归零
			if(a[i][j] == '#'){
				dfs(i, j);
				if(total == cnt){
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

——————————————另附上bfs————————————————

struct note{
	int x, y;	
};
void bfs(int x, int y){
	queue<note> q;
	struct note t;
	t.x = x; t.y = y;
	q.push(t);
	while(!q.empty()){
		t = q.front();
		a[t.x][t.y] = '.';
		total++;
		if(b[t.x][t.y]){
			cnt++;
		}
		q.pop();
		for(int i = 0; i < 4; ++i){
			int xe = t.x + dx[i];
			int ye = t.y + dy[i];
			if(xe < 0 || ye < 0 || xe >= n || ye >= n || a[xe][ye] == '.'){
				continue;
			}
			struct note r;
			r.x = xe; r.y = ye;
			q.push(r);
		}
	}
}

题目

蓝桥

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

2017年蓝桥杯省赛题解（无E、F、J题）上一篇

·【蓝桥】·蓝桥-方格分割下一篇