2025北师大夏令营机考

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

C - Max MEX

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

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

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

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

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

#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\) 大转化为从零开始，保证模运算的对应关系。

D - AABCC

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

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