相差不超过k的最多数，最长公共子序列(一)，排序子序列，体操队形，青蛙过河

相差不超过k的最多数

• 链接:相差不超过k的最多数
  来源：牛客网

题目描述：

给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过 𝑘 。问最多能选择多少个数？

输入描述:

第一行输入两个正整数 𝑛和𝑘。
第二行输入 𝑛 个正整数𝑎𝑖 ，用空格隔开，表示这个数组。

输出描述:

一个正整数，代表能选的最多数量。
数据范围：1≤𝑛≤2×105 1≤𝑘,𝑎𝑖≤1091≤k,

示例1

输入
5 3
2 1 5 3 2
输出
4

说明
显然，1和5不能同时选。所以最多只能选4个数。

算法原理

双指针

代码

#include <iostream>
using namespace std;
#include <vector>
#include <functional>
int main() {int n,k;cin>>n>>k;vector<int> a(n,0);for(int i = 0;i<n;i++)cin>>a[i];sort(a.begin(),a.end());// for(auto e:a)//     cout<<e<<" ";int left = 0;int len = 0;for(int right = 0;right<n;right++){if(a[right]-a[left]>k){len = max(len,right-left);//cout<<left<<":"<<right<<endl;left++;while(a[right]-a[left]>k)left++;}len = max(len,right-left+1);}cout<<len;return 0;
}

最长公共子序列(一)

• 链接:最长公共子序列(一)
  

算法原理

动态规划

代码

#include <iostream>
using namespace std;
#include <vector>
int main() {int n,m;cin>>n>>m;string s1,s2;cin>>s1>>s2;s1 = " "+s1;s2 = " "+s2;vector<vector<int>> dp(n+1,vector<int>(m+1,0));for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){if(s1[i]==s2[j])dp[i][j] = dp[i-1][j-1]+1;else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}}cout<<dp[n][m];return 0;
}

排序子序列

• 链接:排序子序列
  

算法原理

贪心+模拟

代码

#include <iostream>
using namespace std;
#include <vector>
int main() {int n;cin>>n;vector<int> arr(n,0);for(int i = 0;i<n;i++){cin>>arr[i];}int count = 0;int cur = 1;while(cur<n){//跳过相等的while(arr[cur]==arr[cur-1]){cur++;}if(cur<n&&arr[cur]>arr[cur-1]){while(cur<n&&arr[cur]>arr[cur-1]){cur++;}count++;cur++;}if(cur<n&&arr[cur]<arr[cur-1]){while(cur<n&&arr[cur]<arr[cur-1])cur++;cur++;count++;}//如果只有最后一个元素if(cur==n)count++;}cout<<count<<endl;return 0;
}

体操队形

• 链接:体操队形

算法原理

dfs/递归
决策树

代码

#include <iostream>
using namespace std;
#include <vector>
int n;
vector<int> a;
vector<bool> vis;
vector<int> path = {0};
int count = 0;
void dfs(int pos)
{if(pos>n){count++;return;}for(int i = 1;i<=n;i++){//判断是否满足位置要求if(vis[i]&&(vis[a[i]]==false||a[i]==i)){vis[i] = false;dfs(pos+1);vis[i] = true;}}
}
int main()
{cin>>n;vis.resize(n+1,true);a.resize(n+1,0);for(int i = 1;i<=n;i++)    cin>>a[i];dfs(1);cout<<count<<endl;return 0;
}

[蓝桥杯 2022 省 A] 青蛙过河

题目描述

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 $1$，当石头的高度下降到 $0$ 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 $0$ 是允许的)。

小青蛙一共需要去学校上 $x$ 天课，所以它需要往返 $2x$ 次。当小青蛙具有一个跳跃能力 $y$ 时，它能跳不超过 $y$ 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 $x$ 次课。

输入格式

输入的第一行包含两个整数 $n,x$, 分别表示河的宽度和小青蛙需要去学校的天数。请注意 $2x$ 才是实际过河的次数。

第二行包含 $n-1$ 个非负整数 $H_1,H_2,\cdots ,H_{n-1}$, 其中 $H_i>0$ 表示在河中与 小青蛙的家相距 $i$ 的地方有一块高度为 $H_i$ 的石头，$H_i=0$ 表示这个位置没有石头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

样例 #1

样例输入 #1

5 1
1 0 1 0

样例输出 #1

4

提示

【样例解释】

由于只有两块高度为 $1$ 的石头，所以往返只能各用一块。第 $1$ 块石头和对岸的距离为 $4$，如果小青蛙的跳跃能力为 $3$ 则无法满足要求。所以小青蛙最少需要 $4$ 的跳跃能力。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$n\le 100$;

对于 $60\%$ 的评测用例，$n\le 1000$;

对于所有评测用例，$1\le n\le 10^5,1\le x\le 10^9,0\le H_i\le 10^4$ 。

蓝桥杯 2022 省赛 A 组 F 题。

算法原理

借鉴的别人的解法，这里讲一下思路

• 1. 将问题转换为2x只青蛙过河的问题
     
• 2. 这个解析是站在已知最小y的情况下，推的一些性质，然后用这些性质，来结算y
     
     

代码

#include <iostream>
using namespace std;
#include <vector>int main()
{int n,x;cin>>n>>x;int val;vector<int> v(1,0);while(cin>>val){v.push_back(val);}int right = 1,left = 1;int sum = 0;int y = 0;for( ;right<v.size();right++){sum+=v[right];if(sum>=2*x){y = max(y,right-left+1);sum-=v[left++];while(sum>=2*x){sum-=v[left++];}}}if(y==0){cout<<n;}else{cout<<y;}return 0;
}