Czj's Blog

2025北师大夏令营机考

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

本次机考时长 \(90 min\) ，共 \(5\) 题，难度大致为普及。采用学校内部 OJ 进行判题，题目只提供纸质版，OJ 中只做提交。排名以 ACM 标准为主，若过题数为零则参考部分分。

C - Max MEX

本题在考试中以英文题面形式给出。关键点在于对 \(MEX\) 的定义有概念，难度较低。本题在洛谷中也有收录：AT_abc290_c [ABC290C] Max MEX - 洛谷

P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G - 洛谷

根据题目中所求的“最大的最小距离”可以联想到通过二分答案+贪心来解决。

P1057 [NOIP 2008 普及组] 传球游戏 - 洛谷

本题中强调“球只能传到左右两侧”，可以联想到状态转移，考察了对动态规划的掌握程度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
/*
每个人只能将球传给左右
可以发现数据范围为较小的 30，但依旧不能 dfs，因为 2^30 会超时
考虑用动态规划，因为每个人的当次传球不影响后续的传球
并且考虑第 i 个人在第 j 次传球后，其获得球的方案数一定是由左右的上一次获得球的次数贡献的
即 dp[i][j] = dp[l][j-1]+dp[r][j-1]
*/
const int N = 39;
int n,m,dp[N][N];
int main() {
	cin>>n>>m;
	// 在初始的第 0 次传球时 1 号手上有球
	dp[1][0] = 1;
	for(int j = 1;j<=m;j++)
	{
		// 对于每一次
		for(int i = 1;i<=n;i++)
		{
			// 对于每个人
			int l = i==1?n:i-1,r = i==n?1:i+1;
			dp[i][j] = dp[l][j-1]+dp[r][j-1];
		}
	}
	// 最后答案为传球 m 次后 1 号得到球的次数
	cout<<dp[1][m];
	return 0;
}

C - Even Digits

实际机考时提供中文题面，翻译可以参考：AT_abc336_c [ABC336C] Even Digits - 洛谷

主要难点在于将问题转化为 \(5\) 进制，同时需要将题目中的第 \(n\) 大转化为从零开始，以对应模运算 \([0,n-1]\) 的值域范围。

1
cpp

D - AABCC

实际机考时提供中文题面，翻译可以参考：AT_abc300_d [ABC300D] AABCC - 洛谷

事实上只需要先预处理出 \(10^6\) 内的质数（根据值域得到的判断）再进行三重枚举并剪枝即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
/*
要求质数 a b c 在 a<b<c 的情况下由 a^2 * b * c^2 不大于 n 能组合得到的数字种类
给定的 n <= 1e12 因此可以发现组合的最大值域为 2^2 * 3 * p(1e6)^2
因此只需要预处理出 1 - 1e6 的所有质数，就可以保证他们按照式子相乘之后可以得到所有 1e12 之内的数字
*/
const int N = 1e6+9;

ll p[N];
bool st[N];
int idx;
void init() {
	for (int i = 2; i < N; i++) {
		if (!st[i])p[idx++] = i;
		for (int j = 0; j < idx; j++) {
			if (p[j]*i > N)break;
			st[p[j]*i] = 1;
			if (i % p[j] == 0)break; // 每个数只被最小因子筛掉
		}
	}
}
set<ll>s;
int main() {
	cin >> n;
	init();
	// 三重循环检查给定的式子得到的值
	for (int i = 0; i < idx - 2; i++) {
		ll t = p[i] * p[i] * p[i + 1] * p[i + 2] * p[i + 2];
		if (t > n)break;
		for (int j = i + 1; j < idx - 1; j++) {
			ll t = p[i] * p[i] * p[j] * p[j + 1] * p[j + 1];
			if (t > n)break;
			for (int k = j + 1; k < idx; k++) {
				ll t = p[i] * p[i] * p[j] * p[k] * p[k];
				if (t > n)break;
				s.insert(t);
			}
		}
	}
	cout << s.size();
	return 0;
}