12届集美大学校赛题解

12届集美大学校赛题解

官方难度排序参考：

• Easy：GBJHD
• Medium：CAEL
• Hard：KIF

A. 地砖

题意：n×m 的矩形，向每个格子中填充字母，使得所有同字母联通块必须为正方形。最小化从上到下、从左到右的字典序。

题解：最小化字典序是经典的贪心问题。按照从上到下、从左到右的顺序枚举每一个未填充格子的颜色，判断是否可行。

B. 逃离蜂巢

题意：有 n 个陷阱，每拆除一个陷阱，生命值先加 a 再减去 b。任意时刻生命值必须为正数，求最优顺序下拆除最多陷阱。

题解：按 a-b 从大到小排序，按顺序拿取即可。

C. 加密通讯

题意：给出一个 01 字符串若干子串 1 的个数的奇偶性，构造最小字典序的解。

题解：考虑该串的前缀异或和 \(s[i]\)，则 \(parity[l,r]=s[r] \wedge s[l-1]\)。经典的 2-SAT 问题。从 0 开始计算，如果遇到没算过的位置 i，让位置 i 的前缀和与位置 i-1 的前缀和值相等。

D. 简易量筒

题意：有一条河以及 n 个杯子，每个杯子有一个容量。使用这些杯子，能否量出对应体积的水？

题解：能够量出的体积为 \(\sum_{i=1}^nA_ix_i\)（\(x_i\) 是整数），按照扩展欧几里得定理，一定为 \(gcd(A_1,A_2,...,A_n)\) 的倍数。

E. 复杂量筒

题意：有 n 个量筒，第 i 个量筒为 \(i!\)。求量出 \(l \sim r\) 中所有整数体积各一次每个量筒需要用几次。

题解：最优方案贪心，优先选取 n 号量筒。对于 \(l\sim r\) 中的每个数，写成 \(k*n!+b(b<n!)\) 的形式，k 的部分是等差数列求和，b 的部分预处理前缀和快速得出。

G. 电话

题意：给出一个电话键盘和一个号码，求手指移动的总长。

题解：打表预处理按键的位置，直接计算，时间复杂度 \(O(n)\)。

H. 花坛

题意：求有多少种合法的方案在 n×m 花坛中放满至多 4 种花，满足不存在同行同种花距离 ≤3，不存在同列同种花距离 ≤3。

题解：考虑任意同行或同列连续四格必定互异。确定左上 4×4 格后，其余格子全部固定。暴搜左上格子即可。

J. 分子测序

题意：求三维空间中任意三点不共线、任意四点不共面的 n 个顶点的凸多面体有多少个面。

题解：考虑新添加一个顶点，看作在其中一个面上向外扩展出一个四面体，新增加 4-2=2 个面，答案为 \(2n-4\)。

L. 董事会

题意：有 n 个石子组成一个环，每个石子有一个颜色。对于每个 0≤k≤n，判断是否能删除连续的 k 个石子，使得剩下的任意相邻两个石子不同色。