算法每日一题1

2023-04-11

竞赛 / 算法 / 每日一题

Word count: 2.2k | Reading time≈ 10 min

每日一题

每日一题系列旨在督促本人坚持算法练习，并期望将之养成一个习惯。

1、数字三角形

lanqiao505：数字三角形 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月28日22:42:09

tags：动态规划

$\textcolor{red}{分析：}$

定义数字三角形从第一行开始；
相差不超过一是当你到了最后一排才考虑的，当奇数行情况下，最后的一个要加的数一定是最后一行中间那个数；偶数情况下就是中间两个数谁大加谁。可以自己推。
所以动态规划直接从第二排开始，每个数加max（左上，上），最后输出奇数情况一定中间最大，偶数是中间两个其中一个大，所以没必要判断奇偶，就是max（a[n][n/2],a[n][n/2+1]）就行了

题目要求向左下的次数和右下次数相差不超过1，所以可以从次数和对矩阵找规律。设(x,y)为(左下次数，右下次数)
找到如下规律：
(0,0)
(1,0) (0,1)
(2,0) (1,1) (0,2)
(3,0) (2,1) (1,2) (0,3)
(4,0) (3,1) (2,2) (1,3) (0,4)
(5,0) (4,1) (3,2) (2,3) (1,4) (0,5)
可以发现，奇数行次数相差不超过1为中间一个：例如：n=5时，满足条件的为(2,2);
偶数行次数相差不超过1的为中间两个：例如：n=6时，满足条件为(3,2), (2,3)。所以，从左上到右下依次计算最大值并保存，输出时对结果进行判断，若有奇数行，输出最后一行中间的数；若有偶数行，输出最后一行中间两个数中较大的数。

解决代码：

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

int dp[101][101];

int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;++i){// 初始化数据 
		for(int j=1;j<=i;++j){
			cin>>dp[i][j];
		}
	}
	for(int i=2;i<=n;++i){// 从2行开始 
		for(int j=1;j<=i;++j){
			dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]);
		}	
	}
	cout<<max(dp[n][(n+1)/2], dp[n][(n+2)/2]);// 如果n为奇数，那么(n+1)/2与(n+2)/2的值相同
	return 0;
}

2、特别数的和

lanqiao191：特别数的和 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月29日17:03:11

tags：枚举

$\textcolor{red}{分析：}$

通过取余和整除的方式判断一个数是否含有2、0、1、9 四个数。

解决代码：

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

int n;

bool check(int x){// 判断是否包含2、0、1、9 
	while(x){
		int t = x%10;
		x /= 10;
		if(t==2||t==0||t==1||t==9){
			return true;
		}
	}
	return false;
} 

int main() {
	cin>>n;
	int sum = 0;
	for(int i=1;i<=n;++i){
		int tmp = i;
		if(check(tmp)){// 判断是否符合条件 
			sum += tmp;
		}
	} 
	cout<<sum;
	return 0;
}

3、日期问题

lanqiao103：日期问题 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月29日17:05:22

tags：枚举

$\textcolor{red}{分析：}$

根据题意知道，为了方便输出的结果是按照时间顺序的，因此采用从小到大的枚举遍历方式；
具有格式化的输入和输出最好采用C的标准输入和输出更方便。

解决代码：

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

// 输出要按照时间顺序

string str;
int nums[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int year, int month, int day) { // 考虑 month和 day是否符合要求
	if(month<1||month>12)return false;
	if(day<1)return false;
	if(month!=2) { // 考虑非2月份
		if(day>nums[month])return false;
	} else { // 考虑2月份
		int leap = (year%4==0&&year%100!=0)||(year%400==0);// 如果是闰年则leap为1
		if(28+leap<day)return false;// 闰月29天
	}
	return true;
}

int main() {
//	cin>>str;
//	string s1 = str.substr(0, 2);
//	int aa = stoi(s1);
//	string s2 = str.substr(3, 2);
//	int bb = stoi(s2);
//	string s3 = str.substr(6, 2);
//	int cc = stoi(s3);
	int aa, bb, cc;
	scanf("%d/%d/%d", &aa, &bb, &cc);// 对于有格式要求的输入输出，使用C语言的输入和输出更加简便 
	for(int x=19600101; x<=20591231; ++x) { // 枚举遍历
		int year = x/10000, month = x%10000/100, day = x%100;
		if(check(year, month, day)) {
			if( aa==year%100&&bb==month&&cc==day||
				aa==month&&bb==day&&cc==year%100||
				aa==day&&bb==month&&cc==year%100 )
				printf("%d-%02d-%02d\n", year, month, day);// 格式控制符 %02d 指定每个数值的宽度为2，不足两位则在前面补0
		}
	}
	return 0;
}

4、灌溉

lanqiao551：灌溉 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月29日17:07:50

tags：枚举

$\textcolor{red}{分析：}$

采用曼哈顿距离解决本题会非常简单；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 使用曼哈顿距离解决本题会非常简单

int n, m, t, k;// 注意定义变量的时候不要重复了 
int r[101], c[101]; 

int main() {
	cin>>n>>m>>t;
	int cnt = 0;
	for(int i=1;i<=t;++i){// 初始化位置坐标 
		cin>>r[i]>>c[i];
	}
	cin>>k;
	// 找出矩阵中的点与已知点之间的曼哈顿距离 
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			for(int l=1;l<=t;++l){
				int d = abs(r[l]-i)+abs(c[l]-j);// 求曼哈顿距离 
				if(d<=k){// 如果不大于k，则表明在k分钟内能够灌溉到当前位置 
					cnt++;
					break;// 只要与已知的点有一个满足就行，不然可能会计算重复s 
				}
			}
		}
	}
	cout<<cnt;
	return 0;
}

5、火星人

lanqiao572：火星人 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月29日18:16:34

tags：排列型枚举

$\textcolor{red}{分析：}$

本题最关键的就是巧妙的运用next_permutation()的特性，从输入的排列开始继续往后排列M次得到的就是最终的结果；

解决代码：

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

const int N = 1e4+10;
int order[N];
int n, m;

int main() {
	cin>>n;
	cin>>m;
	for(int i=1;i<=n;++i){
		cin>>order[i];
	}
	for(int i=1;i<=m;++i){
		next_permutation(order+1, order+1+n);// 由当前排列往下继续m次就得到了最后改变后的排列结果 
	}
	for(int i=1;i<=n;++i){
		cout<<order[i]<<" ";
	}
	return 0;
}

6、日志统计

lanqiao179：日志统计 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月29日22:12

tags：尺取

$\textcolor{red}{分析：}$

首先我们必须根据题意中的区间[T, T+D)，并将该区间作为一个滑动窗口；
为了更好的方便使用滑动窗口，我们必须将输入的ts与id依据ts进行升序排序，这样从第一个ts开始进行区间滑动；滑动的条件是：当h[i].ts>=h[l].ts+D时我们需要将区间的左边界向后移动，这里可以定义l来控制左边界的移动，又ts之间并不是等差变化，因此这里不能使用r来控制右区间的移动，而只能根据区间[T, T+D)来移动左边界。
值得注意的是id是从0开始到100000结束，而不是从1开始的。

解决代码：

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

const int len = 1e5+10;
int N, D, K;
int ts, id;
int l, r;
struct node{
	int ts, id;
}; 

bool comp(node&a, node&b){
	return a.ts<b.ts;
}

node h[len];
bool ish[len];
int likeNum[len];

int main() {
	l = 1;// 控制移动窗口的左边界 
	cin>>N>>D>>K;
	for(int i=1;i<=N;++i){
		cin>>h[i].ts>>h[i].id;
	}
	sort(h+1, h+1+N, comp);// 按照ts进行降序排序 
	for(int i=1;i<=N;++i){
		likeNum[h[i].id]++;// 对应点赞数增加 
		while(h[i].ts>=h[l].ts+D)likeNum[h[l++].id]--;// 保证时间在左闭右开区间之内 
		if(likeNum[h[i].id]>=K)ish[h[i].id] = true;// 满足热帖的条件 
	}
	for(int i=0;i<=1e5;++i){// id是从0开始到100000结束 
		if(ish[i]){
			cout<<i<<endl;
		}
	}
	return 0;
}

7、回文判定

lanqiao1371：题库 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月29日

tags：尺取

$\textcolor{red}{分析：}$

本题主要采用双指针反向搜索的方式进行处理；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 回文判定——双指针反向搜索 
int main() {
	string s;
	cin>>s;
	int l = 0;
	int r = s.length()-1;
	if(l == r)cout<<"Y";
	else{
		while(l<r){
			if(s[l]!=s[r]){
				cout<<"N";
				return 0;
			}
			l++;
			r--;
		}
		cout<<"Y";
	}
	return 0;
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.