第二周周测题解

前言

这套题中涉及到的知识点有 模拟、前缀和、贪心、快速排序、动态规划、结构体、栈、队列、dfs、bfs等。题目偏简单。
在写代码时，可以用函数来实现单独的功能，比如第二题实现一个判断素数的函数，第三题实现一个将数字分解相加并乘以3加1的函数等。能使代码变得简洁明了， 方便后面的调试和修改。

7-0 当日天数

昨天热身赛的最后一题，但很多人没写出来，计算日期的这类问题，蓝桥杯基本每年都会考，所以就写一下思路和题解供参考。

编程计算某年某月某日当天，是当年的第几天。 说明：1）当年1月1日是第1天；2）每月按月大，月小，闰年等情况，各月天数有不同（31，30，28，29）；3）闰年按4年一闰，100年不闰，400年再闰计算。

输入格式:
用空格分隔的三个正整数（表示年，月，日的整数），均是合法的数据。

输出格式:
直接输出年-月-日：整数。表示当日是第几天。年号占4位，不足4位时补前导零，月和日各占2位，不足2位也补前导零。

输入样例:

2020 3 3

输出样例:

2020-03-03:63

首先是格式，使用printf(%02d, month); d前面加一个02的意思是 如果数字不够2位数的话就在前面补0，scanf 与printf 还有许多用法，可以在网上或者自己试验，多了解一下。
题目大致思路是：模拟每一天的增加，到达月底最后一天，月份加一，月份到达年底最后一个月，年份加一，注意每过一年还需要判断一下是不是闰年。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//用一个数组存每个月有多少天
int arr[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main(){
	int y, m, d, ans = 1;
	cin >> y >> m >> d;
	//闰年的话2月就是29天，注意如果题目是遍历好多年的，每过一年就把arr[2]变为28，防止出错。
	if(y%4==0&&y%100!=0||y%400==0) arr[2] = 29;
	int i = 1, j = 1; // 记录月和天
	while(1){
		if(i == m && j==d) break;
		j++; ans++;
		// 如果天数大于当月的天数， 月数加一，天数变为0。
		// 如果月数大于12，年数加一，月数变为0，本题不需要。
		if(j > arr[i]){
			i++, j = 1;
		}
	}
	printf("%04d-%02d-%02d:%d",y,m,d,ans);
}

7-1 西安距离

题目中要求只能走与x轴或y轴水平的直线，因此不是求两点之间的直线距离，而求|(x2-x1)|+|(y2-y1)|的值。注意求绝对值。代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << abs(c-a)+abs(d-b);
}

7-2 判断素数

本题的目标很简单，就是判断一个给定的正整数是否素数。

判断一个数是否为素数只需遍历到$\sqrt{n}$即可，注意1不是素数。代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int jud(int n){
	if(n == 1) return 0;
	for(int i = 2; i <= sqrt(n); i++){
		if(n%i == 0) return 0;
	}
	return 1;
}

int main(){
	int n, a;
	cin >> n;
	while(n--){
		cin >> a;
		if(jud(a)) cout << "Yes" << endl;
		else cout << "No" << endl; 
	}
}

7-3 掉入陷阱的数字

用一个变量记录上一次的数字是多少，如果这次跟上次相同就结束。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//将n各位数字相加求和.再将其和乘以3后加上1
int resolve(int n){
	int ans = 0;
	while(n){
		ans += n%10;
		n /= 10;
	}
	return 3*ans+1;
}

int main(){
	int n, f;  // f用来记录上一次的数字。
	cin >> n;
	for(int i = 1; ; i++){
		f = n;
		n = resolve(n);
		cout << i << ":" << n << endl;
		if(f == n) break;
	}
	return 0;
}

7-4 跳一跳

模拟即可。用一个变量标记连续几次跳到中心，没跳到中心就清0。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int n, ans = 0, f = 1;
	while(cin >> n, n!=0){
		if(n == 2) {
			ans += f*2; f++;
		}else{
			ans++; f = 1;
		}
	}
	cout << ans; 
}

7-5 看电影

贪心算法，根据电影的结束时间从小到大排序，用一个变量记录当前时间，遍历寻找满足 电影开始时间>=当前时间的电影，寻找的第一个符合条件的电影就是最优的选择，再将记录时间的变量改为此电影的结束时间。直至遍历结束。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;

struct node{
	int begin, end;
}arr[N];

bool cmp(node a, node b){
	if(a.end == b.end){
		return a.begin < b.begin;
	}
	return a.end < b.end;
}

int main(){
	int n;
	while(cin >> n, n!=0){
		int ans = 0, f = 0; // f用来记录当前的时间
		for(int i = 0; i<n; i++){
			cin >> arr[i].begin >> arr[i].end;
		}
		sort(arr,arr+n,cmp);
		//遍历寻找
		for(int i = 0; i < n; i++){
			if(arr[i].begin >= f){
				ans++;
				f = arr[i].end;
			}
		}
		cout << ans << endl;
	}

}

7-6 求区间和

??
使用前缀和数组，经过预处理后，每次查询只需要O(1)的时间复杂度。
（由于输入的数据量过大，用cin，cout有时候会超时）
即对于一个数字序列。用arr[i]数组储存这串数的前 i 项的和，那么每次寻找序列第a到b号元素的和时就不需要遍历a到b之前的所有数了，只需要计算arr[b] - arr[a-1]的值就行。
比如序列：3 2 4 1 5 6。
arr数组（以1位数组下标）对应的值是：3 5 9 10 15 21。
计算序列第3项到第5项的值就是 arr[5]-arr[2] = 15-5 = 10。
前缀和算法实用性很高，此外还有差分算法，建议不了解的同学在网上看看相关文章。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int mod = 10000019;
int arr[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, a, b, m;
	cin >> n;
	for(int i = 1; i<=n; i++){
		cin >> a;
		arr[i] = (arr[i-1]+a)%mod;
	}
	cin >> m;
	while(m--){
		cin >> a >> b;
		cout << (arr[b]+mod-arr[a-1])%mod << endl;
		// +mod 是为了arr[b]<arr[a]的情况
	}
}

7-7 最大子段和

动态规划的入门题。
设dp[i]为以第i个元素结尾且和最大的连续子数组。
假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素。
即dp[i] = max(dp[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
int dp[N];
int main(){
	int n, ans = 0, a;
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> a;
		dp[i] = max(dp[i-1]+a, a);
		ans = max(dp[i], ans);
	}
	cout << ans;
}

此外由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，即不需要数组储存之前的结果，只需要保留上一次的即可。

7-8 逆波兰表达式求值

考察数据结构中栈的应用。
对于每次输入的元素。如果当前元素是整数，则压入栈；如果是运算符，则将栈顶两个元素弹出做相应运算，再将结果入栈。
最终表达式扫描完后，栈里的数就是结果。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<int> arr;

//将字符串转为数字
int to_int(string str){
	int ans = 0, i = 0, f = 0;
	if(str[0] == '-') {
		f = 1; i = 1;
	}
	for(;i<str.size(); i++){
		ans = ans*10+str[i]-'0';
	}
	if(f) ans = 0-ans;
	return ans;
}

int main(){
	string str;
	while(cin >> str){
		if(str[0] == '+'||str[0] == '-'&&str.size()>1||str[0] == '*'){
			int n2 = arr.top(); arr.pop();
			int n1 = arr.top(); arr.pop();
			if(str[0] == '+') arr.push(n1+n2);
			else if(str[0] == '-') arr.push(n1-n2);
			else arr.push(n1*n2);
		}else{
			arr.push(to_int(str));
		}
	}
	cout << arr.top();
}

7-9 排排排名

直接根据分数与账号的字典序排序就行。输出的时候注意名次可以相等，需要用变量记录上一个人的分数和相等的名次数量，后面再加上。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
struct node{
	string str;
	int n;
}arr[N];

bool cmp(node a, node b){
	if(a.n == b.n){
		return a.str < b.str;
	}
	return a.n > b.n;
}
int main(){
	int n, m, f = 0, last = -1, lastn = 1; 
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> arr[i].str >> arr[i].n;
	sort(arr,arr+n,cmp);
	// f:是当前的名次， last：是上一个人的分数， lastn是有几个拥有last分数的人
	for(int i = 0; i < n; i++){
		if(arr[i].n!=last){
			last = arr[i].n;
			f += lastn; lastn = 1;
		}else lastn++;
        if(f>m) break;
		cout << f <<" "<< arr[i].str << " " << arr[i].n << endl;
	}
}

7-10 白骑士的移动

跟迷宫题类似，不过马的路径跟走迷宫的不太一样，需要注意。寻找最小的步数，所以要用bfs（本题中
dfs应该也不会超时），注意黑战车与黑主教的攻击，遇到障碍后就会停止。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

char arr[15][15];
int vis[15][15], ans = 0, bx, by;
// 马的路径
int d[8] = {2,2,1,1,-1,-1,-2,-2};
int f[8] = {1,-1,2,-2,2,-2,1,-1};

struct node{
	int x, y, v;
};
//黑主教的攻击范围
void disB(int x, int y){
	vis[x][y] = 1;
	for(int i=x+1,j=y+1; i<=8&&j<=8; i++,j++){
		if(arr[i][j] != '.') break;
		vis[i][j] = 1;
	}
	for(int i = x-1, j = y-1; i>=1&&j>=1; i--,j--){
		if(arr[i][j] != '.') break;
		vis[i][j] = 1;	
	}
	for(int i=x+1,j=y-1; i<=8&&j>=1; i++,j--){
		if(arr[i][j] != '.') break;
		vis[i][j] = 1;	
	}
	for(int i=x-1,j=y+1; i>=1&&j<=8; i--,j++){
		if(arr[i][j] != '.') break;
		vis[i][j] = 1;	
	}
}
//黑战车的攻击范围
void disR(int x, int y){
	vis[x][y] = 1;
	for(int i=x+1; i <= 8;i++){
		if(arr[i][y] != '.') break;
		vis[i][y] = 1;
	}
	for(int i=x-1; i >= 1;i--){
		if(arr[i][y] != '.') break;
		vis[i][y] = 1;
	}
	for(int i=y+1; i<= 8;i++){
		if(arr[x][i] != '.') break;
		vis[x][i] = 1;
	}
	for(int i=y-1; i >= 1;i--){
		if(arr[x][i] != '.') break;
		vis[x][i] = 1;
	}
}

void bfs(){
	queue<node> q;
	node b; b.x=bx; b.y=by; b.v = 0;
	q.push(b);
	while(!q.empty()){
		node p = q.front(); q.pop();
		for(int i = 0; i<8; i++){
			int x = p.x+d[i];
			int y = p.y+f[i];
			if(arr[x][y] == 'Q'){
				ans = p.v+1; return;
			}
			if(x>=1 && x<=8 && y>=1 && y<=8 && vis[x][y]==0){
			//	cout << x <<" "<< y << endl;
				vis[x][y] = 1;
				node n; n.x = x; n.y = y; n.v =p.v+1;
				q.push(n);
			}
		
		}
	}
}
//对棋盘中的棋子进行处理
void check(){
	for(int i = 1; i<=8; i++){
		for(int j = 1; j<= 8; j++){
			if(arr[i][j] == 'R'){
				disR(i,j);
			}else if(arr[i][j] == 'B'){
				disB(i,j);
			}else if(arr[i][j] == 'K'){
				bx = i; by = j;
			}
		}
	}
}

int main(){
	for(int i = 1; i<=8; i++){
		for(int j = 1; j<= 8; j++){
			cin >> arr[i][j];
		}
	}
	check();
	bfs();
	if(ans == 0) cout << "Checkmate";
	else cout << ans;
	
}