【刷题汇总 -- 爱吃素、相差不超过k的最多数、最长公共子序列(一)】

今日刷题汇总 - day026

1、爱吃素

1.1、题目

1.2、思路

读完题知道，让判断两个正整数相乘之后是否是素数。当数据量太大时，考虑会超过范围，所以对于大数不能简单的相乘后判断。那么首先要清楚素数的性质，素数(质数)指除了能被1或本身外整除的数。根据题目和示例分析，可分类讨论解决，当a=1时判断b是否是素数，因为ab = 1b = b直接判断b的结果，把结果保留后，再当b=1时，判断a是否为素数，最后两个结果或上即可，都说明a*b为素数。那么接下来，就是程序实现。

1.3、程序实现

首先，按照题目要求写好输入，然后根据思路分析对ab分类讨论，当a = 1且b是素数或者b =1且a为素数则，ab为素数输出“YES"即可，否则输出“NO"。其中封装一个isprim函数潘顿是否为素数，值得注意的是数据范围的问题，采用long long即可。

#include <iostream>
#include <cmath>
using namespace std;bool isprim(long long x)
{if(x < 2)return false;for(int i = 2;i <= sqrt(x);i++){if(x % i == 0)return false;}return true;
}int main()
{int T;cin >> T;long long  a,b;while(T--){cin >> a >> b;if((a == 1 && isprim(b)) || (b == 1 && isprim(a))){cout << "YES" << endl;}elsecout << "NO" << endl;}return 0;
}

2、相差不超过k的最多数

2.1、题目

2.2、思路

读完题知道，给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过 k。问最多能选择多少个数？读完题知道，根据蛮力法的思路就是把数组sort排序，然后从左向右枚举所有情况，判定能够选择最多数的方案即可，但是这样子right会有很多的回溯，所以既然两个指针相同的方向遍历。且具有k约束差值大小，所以很容易想到了适用滑动窗口进行优化。那么滑动窗口就需要确定：
(1)、进窗口，right所指的元素直接进窗口即可。
(2)、判断窗口，当窗口大于k，即：arr[right] - arr[left] > k ，
(3)、出窗口，然后left++滑动窗口，元素个数也跟着减少，即为出窗口；
(4)、更新结果，更新区间的元素个数即可，保持最多的元素个数到ret变量中即可；
那么接下来，就是程序实现。

2.3、程序实现 – 滑动窗口

首先，按照题目要求写好输入，然后进行排序预处理，接着根据思路分析采用滑动窗口思路优化蛮力法，因为这里控制的是元素个数，所以直接进窗口，知道判断窗口，再出窗口滑动窗口，然后更新每一个出之后的结果，最后遍历完后得到最多元素个数ret，输出ret即可。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 2e5 + 10;
int arr[N];int main()
{int n,k;cin >> n >> k;for(int i = 0;i < n;i++)cin >> arr[i];//排序sort(arr,arr+n);int left = 0;int right = 0;int ret = 1;//元素个数至少为1while(right < n){//进窗口 + 判断窗口 + 滑动窗口while(arr[right] - arr[left] > k){left++;}//更新结果ret = max(ret,right - left + 1);right++;}cout << ret << endl;return 0;
}

3、最长公共子序列(一)

3.1、题目

3.2、思路

读完题知道，与之前最长回文子序列类似，而这里是给定两个字符串 s1 和 s2，长度为 n 和 m 。求两个字符串最长公共子序列的长度。所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。对于这种选择删与不删很容易想到0/1背包等dp类问题，所以采用dp思路根据题目和示例分析，需要确定状态表示和状态转移方程。
状态表示： dp[i][j] 表示：字符串s1中[0, i] 区间与字符串s2中[0, j] 区间内所有的子序列中，最长公共子序列的长度是多少。
状态转移⽅程：根据最后⼀个位置的字符情况，划分情况：
a.选择最后一个位置：s1[i] == s2[j]：dp[i][j] = dp[i - 1][j - 1] + 1；
b.不选择最后一个位置：s1[i] != s2[j]：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。
初始化：为了防⽌越界，我们把字符串的起始位置从1开始计算。
那么接下来，就是程序实现。

3.3、程序实现 – dp

推导确定状态表示和状态转移方程即可。
状态表示： dp[i][j] 表示：字符串s1中[0, i] 区间与字符串s2中[0, j] 区间内所有的子序列中，最长公共子序列的长度是多少。
状态转移⽅程：根据最后⼀个位置的字符情况，划分情况：
a.选择最后一个位置：s1[i] == s2[j]：dp[i][j] = dp[i - 1][j - 1] + 1；
b.不选择最后一个位置：s1[i] != s2[j]：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。
初始化：为了防⽌越界，我们把字符串的起始位置从1开始计算。

#include <iostream>
using namespace std;const int N = 1010;
char s1[N];
char s2[N];//dp[i][j]表示：字符串s1中[0, i] 区间与字符串s2中[0, j] 区间内所有的子序列中，最长公共子序列的长度是多少。
int dp[N][N];int main()
{int n,m;cin >> n >> m;for(int i = 1;i <= n;i++)cin >> s1[i];for(int i = 1;i <= m;i++)cin >> s2[i];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;//前一个位置的最长子序列+自己本身elsedp[i][j] = max(dp[i-1][j],dp[i][j-1]);//前面区间的最大值}}cout << dp[n][m] << endl;return 0;
}

4、题目链接

🌟爱吃素
🌟相差不超过k的最多数
🌟最长公共子序列(一)