爱吃素
牛妹是一个爱吃素的小女孩，所以很多素数都害怕被她吃掉。
一天，两个数字aaa和bbb为了防止被吃掉，决定和彼此相乘在一起，这样被吃掉的风险就会大大降低，但仍有一定的可能被吃掉，请你判断他们相乘后是否仍有被吃掉的风险。
也就是说，请你判断a×ba\times ba×b是否是素数。
素数是指大于111的正整数中，有且仅有两个因子的数。
输入描述:
输入第一行是一个整数T(1≤T≤10)T(1\leq T\leq 10)T(1≤T≤10)，表示测试组数。接下来TTT行，每一行两个整数a,b(1≤a,b≤1011)a,b(1\leq a,b\leq 10^{11})a,b(1≤a,b≤1011)。
输出描述:
对于每一行输入，若输入满足a×ba\times ba×b是素数，输出一行"YES"，否则输出一行"NO"（没有引号）。
#include <iostream>
#include <cmath>#define int long longusing namespace std;bool is_prime(int x)
{if(x < 2) return false;for(int i = 2; i <= sqrt(x); i++){if(x % i == 0) return false;}return true;}
signed main()
{int t;cin >> t;while (t--){int a, b;cin >> a >> b;int x = min(a, b), y = max(a, b);if (x == 1){if (is_prime(y))cout << "YES" << endl;else cout << "NO" << endl;}else {cout << "NO" << endl;}}return 0;
}
相差不超过k的最多数
描述
给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过 �k 。问最多能选择多少个数？
输入描述：
第一行输入两个正整数 �n和�k。
第二行输入 �n 个正整数��a**i，用空格隔开，表示这个数组。
输出描述：
一个正整数，代表能选的最多数量。
数据范围：
1≤�≤2×1051≤n≤2×105
1≤�,��≤1091≤k,a**i≤109
#include <iostream>
#include <algorithm>using namespace std;
const int N = 2e5+10;
int n, k;
int a[N];int main()
{cin >> n >> k;for (int i = 0; i < n; ++i)cin >> a[i];sort(a, a + n);int ans = 1;for (int left = 0, right = 0; right < n; ++right){while (abs(a[right] - a[left]) > k)++left;if (abs(a[right] - a[left]) <= k)ans = max(ans, right - left + 1);}cout << ans << endl;return 0;
}
最长公共子序列
描述
给定两个字符串 s1 和 s2，长度为 n 和 m 。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 “arcaea” 的子序列有 “ara” 、 “rcaa” 等。但 “car” 、 “aaae” 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。
数据范围 : 1≤�,�≤10001≤m,n≤1000 。保证字符串中的字符只有小写字母。
要求：空间复杂度 �(��)O(m**n)，时间复杂度 �(��)O(m**n)
进阶：空间复杂度 �(���(�,�))O(min(m,n))，时间复杂度 �(��)O(m**n)
输入描述：
第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。
接下来第二行和第三行分别输入一个字符串 s1 和 s2。
输出描述：
输出两个字符串的最长公共子序列的长度
#include <iostream>
#include <string>using namespace std;
int n, m;
const int N = 1010;
int dp[N][N];
string s, t;
int main()
{cin >> n >> m;cin >> s >> t;for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){if (s[i] == t[j]){dp[i+1][j+1] = dp[i][j] + 1;}else {dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);}}}cout << dp[n][m] << endl;return 0;
}