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 有 $x$ 个，那么就说明可以拆出来 $x$ 个集合 mex 至少为 1，此时答案增加 $x$ （这一步是考虑这些集合对答案的贡献）。

再考虑有多少个集合的 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 传递

$dp[i][j][0/1]$ 表示目前 A 青蛙在第 $i$ 个石子，B 青蛙在第 $j$ 个石子，0/1 表示目前哪只青蛙拿跳跃器。

每次转移有 4 种情况，要么 A 青蛙跳跃，要么 B 青蛙跳跃，要么传递跳跃器。

如果这样写 $dp$ 的话，我们会发现 $dp[i][j][0]$ 可以转移到 $dp[i][j][1]$ ，而 $dp[i][j][1]$ 也可以转移到 $dp[i][j][0]$ ，不满足无后效性。但本题是一个求 min 的 $dp$ ，多次求 min 不会出错，所以可以在原地多转移几次，保证对于某一位置 $i,j$ ，无论第三维是 0 还是 1，都转移到了最优解。

每次跳跃都是跳跃到下一个石子就行，不必跨越多个石子跳跃。因为本题考虑的是最少传递次数，和跳跃次数无关。

#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;
}