【C++】 —— 笔试刷题day_30

一、爱吃素

题目解析

这道题，简单来说就是给定两个数a和b，然后让我们判断a*b是否是素数。

算法思路

这道题还是比较简单的

首先，输入两个数a和b，这两个数的数据范围都是[1, 10^11]；10的11次方，那a*b不就是10的22次方了，这么大的数，long long也是存不下的；

所以我们不能直接去判断a*b是否是素数。

那我们该如何去判断呢？

我们知道素数是指：大于1的正整数中，只存在两个因子（就是1和这个数本身）。

那我们要判断a*b是否是素数，它只有两个因子，那不就是a和b吗，所以a和b一个数等于1，且另外一个数是素数。

所以这里我们只需要判断a和b其中一个数等于1，另一个数是一个素数即可。（也就不用考虑数据范围的问题了）

代码实现

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

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

题目解析

对于这道题，给定一个数组nums，然后让我们在这个数组中找出一些数，这些数的任意两个数之差的绝对值不超过k；

求我们找出这些数中，数据个数的最大值。

简单来说就是找到一些数，这些数中的最大值和最小值之差不超过k；然后让我们求这些数在数据的最大个数。

算法思路

OK啊，对于这道题，给的数据是乱序的，我们不好找；所以我们可以试着现将数据进行排序；

排序

我们排序之后，数据有序了，发现我们找到这一些数一定是连续的；

了解过滑动窗口的相信已经有思路了：滑动窗口求最长的连续子区间

对于一个有序的数组，我们要找一段连续的子区间，这一段区间的最大值和最小值只差不超过k。

这里因为我们数组是有序的，我们不用记录区间内的最大值和最小值，因为right指向的位置就是最大值，left指向的位置就最小值。

我们只需记录并更新最终结果即可。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
int arr[N];
int n,k;
int main()
{cin>>n>>k;for(int i = 0;i<n;i++)  cin>>arr[i];sort(arr,arr+n);int l = 0,r = 0;int ret = 0;while(r < n){while(arr[r] - arr[l] > k)  l++;ret = max(ret, r - l + 1);r++;}cout<<ret<<endl;return 0;
}

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

题目解析

对于这道题，给定两个字符串s1和s2，然后让我们找到这两个字符串中最长公共子序列的长度；

**子序列：**字符串的一部分，可以不连续；例如abcde的一个子序列bde；

算法思路

我们看到这道题，如果没有了解过动态规划的话，可以是能想到的就只有暴力解法了；

当然暴力解法态麻烦了，这里就不叙述了；

来看这道题应该如何去解决：

我们要求这两个字符串的最长公共子序列的长度，那我们就可以记录一个字符串某一个子串和另一个字符串的某一个子串的最长公共子序列的长度，这样我们在遍历两个子串，找到一个相同的字符时，就可以直接拿到两个字符串前面子串的最长公共子序列的长度。

所以这道题思路就显而易见了：动态规划

• 状态表示： dp[i][j]表示s1中[1,i]子串和s2中[1,j]子串的最长公共子序列的长度。

• 状态转移方程： 我们遍历两个字符，遍历到某一个位置(s1的i位置，s2的j位置)

  如果这两个位置字符相等s1[i] == s2[j]，此时最长公共子序列的长度就等于s1中[1,i-1]和s2中[1,j-1]子串的最长公共子序列长度加1；

  如果这两个位置字符不相等s1[i] != s2[j]，但是我们s1[i]可能等于s2[j-1]，s2[j]也可能等于s1[i-1]，所以此时最长公共子序列长度就等于：s1中[1,i-1]和s2中[1,j]子串的最长公共子序列长度和s1中[1,i]和s2中[1,j-1]子串的最长公共子序列长度的最大值。

  所以，当s1[i] == s2[j]时，dp[i][j] = dp[i-1][j-1] + 1；当s1[i] != s2[j]时，dp[i][j] = max(dp[i][j-1], dp[i-1][j])。

代码实现

#include <iostream>
using namespace std;
const int N = 1010;
int dp[N][N];
char s1[N];
char s2[N];
int n, m;
int main() {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][j - 1], dp[i - 1][j]);}}cout << dp[n][m] << endl;return 0;
}

到这里，本篇文章内容就结束了。
继续加油啊！！！