2022 OI 集训营普及组第一场题解
T1 学习除法
本题等价于判断质数，若原数字为质数，则输出 0，否则输出 1
因为对于每
#include <iostream>
using namespace std;
int main(){
long long n;
cin >> n;
for(int i = 2; i <= n / i; i++){
if(n % i == 0){
cout << 1 << endl;
return 0;
}
}
cout << 0 << endl;
} 一个大于等于 2 的数字，一定可以找到另一个数字可以将它除成质数（素因子分解定理）
T2 拆分
考虑有多少个集合的 mex 可以至少为 1——这些集合必须有一个 0
所以假设 0 有
个，那么就说明可以拆出来 个集合 mex 至少为 1，此时答案增加 （这一步是考虑这些集合对答案的贡献）。
再考虑有多少个集合的 mex 可以至少为 2——这些集合必须有一个 1，并且 mex 至少为 2 的集合的数量一定小于等于 mex 至少为 1 的集合，所以涉及到一个求 min 的操作。
所以假设 0 有
再考虑有多少个集合的 mex 可以至少为 2——这些集合必须有一个 1，并且 mex 至少为 2 的集合的数量一定小于等于 mex 至少为 1 的集合，所以涉及到一个求 min 的操作。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a, cnt[maxn];
int main(){
int n;
cin >> n;
memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n; i++){
cin >> a;
cnt[a]++;
}
int now = cnt[0], ans = now;
for(int i = 1; i <= 1000; i++){
now = min(now, cnt[i]);
ans += now;
}
cout << ans << endl;
} T3 部落
考察 nlogn 求最长上升子序列，求得最长上升子序列之后，我们还要去考虑最上面那一个点是否需要修改高度，进行分类讨论即可。
#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], tp[maxn];
int main(){
int n, pos, p = 1, ans = 0;
cin >> n >> pos;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
tp[1] = a[1];
for(int i = 2; i < pos; i++){
if(a[i] >= tp[p]) tp[++p] = a[i];
else{
int l = 1, r = p, mid = p >> 1;
while(l != r){
if(a[i] < tp[mid]) r = mid;
else l = mid + 1;
mid = (l+r) >> 1;
}
tp[l] = a[i];
}
}
if(a[pos] >= tp[p]){
p++; // 不必修改最上面的点的高度
}else{
a[pos] = 1e9 + 1; // 修改最上面的点的高度，将其变为无穷大
}
ans = pos - p;
p = 1;
tp[1] = a[pos];
for(int i = pos + 1; i <= n; i++){
if(a[i] <= tp[p]) tp[++p] = a[i];
else{
int l = 1, r = p, mid = p >> 1;
while(l != r){
if(a[i] > tp[mid]) r = mid;
else l = mid + 1;
mid = (l + r) >> 1;
}
tp[l] = a[i];
}
}
ans += (n - pos + 1) - p;
cout << ans << endl;
}
T4 传递
每次转移有 4 种情况，要么 A 青蛙跳跃，要么 B 青蛙跳跃，要么传递跳跃器。
如果这样写
每次跳跃都是跳跃到下一个石子就行，不必跨越多个石子跳跃。因为本题考虑的是最少传递次数，和跳跃次数无关。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int a[maxn], b[maxn], dp[maxn][maxn][2];
int main(){
int n, m, k, q;
cin >> n >> m >> k >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
cin >> b[i];
}
a[n+1] = a[n];
b[n+1] = b[n];
memset(dp, 0x3f, sizeof dp);
dp[0][0][0] = 0;
dp[0][0][1] = 1;
for(int step = 0; step <= 2 * n; step++){
for(int j = 0; j <= min(n, step); j++){
int i = step - j;
if(i > n) continue;
for(int k = 0, r = 0; r <= 3; k++, r++){ // 枚举第三维时，在原地转移 4 次，这样 0 1 都被互相求 min
k = r % 2;
if(dp[i][j][k] >= 1e9) continue;
if(abs(a[i] - b[j]) <= q)
dp[i][j][k^1] = min(dp[i][j][k^1], dp[i][j][k] + 1);
if(k == 0){
dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
if(b[j+1] - b[j] <= m){
dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k]);
}
}else{
dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k]);
if(a[i+1] - a[i] <= m){
dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
}
}
}
}
}
cout << min(dp[n][n][0], dp[n][n][1])<< endl;
}
