ZUCC2015新生选拔赛
引言
考虑到一本招生,略微提高难度;预计可做题4-5道,然而没到预期。
A. 五则计算器
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1606
解题报告:水题。
分支结构的应用,做不出建议转专业。
B. 土鸡爱数数
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1607
解题报告:水题。
gets容易受到系统环境影响,建议使用scanf输入。
本来查询次数 $q$ 较大,需要预先处理出每个字符的总数,再处理询问。
C. 土鸡拜火教
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1608
解题报告:逻辑题。数学归纳法。
输出 $n - m + 1$ 即可。
证明部分详见一个关于数学归纳法的悖论问题:到底是第 N 天有 N 个红眼睛自杀,还是什么都不会发生? - 知乎
D. 汪洋的绯闻
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1609
解题报告:数学题。
递推公式为 $f_{n} = f_{n-1} + (n-1)f_{n-2}$。
第 $n$ 个人如果跟外人脱单,剩下 $n-1$ 个人有 $f_{n-1}$ 种情况;
如果跟 $n-1$ 里的其中一个人脱单,有 $n-1$ 种选择,而剩下 $n-2$ 个人有 $f_{n-2}$ 种情况,根据乘法原理相乘即可。
E. 土鸡摩天楼
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1610
解题报告:模拟题。
先用数组记录零到九的 $LED$ 灯亮灭情况,然后用数组记录两种数字间的差异多大。
这样预先处理好,对于输入的 $M$ 每一位,分开来考虑差异范围内数字的情况一共几种,根据乘法原理相乘即可。
F. 检索联系人
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1611
解题报告:模拟题。字符串处理。
主要是处理部分复杂。
需要注意的是,元音只有 $a, e, o, u, i, v$,声母包括 $zh, ch, sh$。
对于一个元音,如果前一个也是元音,则忽略;否则前面必为声母,声母可能一位或两位。
先把所有缩写预先处理好,每次查询只要用strstr函数比较即可。
G. 荣荣的爱情
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1612
解题报告:逻辑题。小学奥数题。
对方是知道月份的:
- 如果该月份内所有日期,在别的月份内都未出现过,则你必然知道答案
- 如果该月份内所有日期,在别的月份内都出现过,则你必然不知道答案
- 如果该月份内所有日期,在别的月份内出现过与未出现过都有,则你不一定知道答案
显然第一第三两种情况,是话语 $2$;第二种情况,是话语 $1$。
所有我们枚举出生月份,加以判断即可。
H. 奏心的土鸡
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1613
解题报告:数学题。
用 $f_n$ 表示土鸡数量,用 $s_n$ 表示总记录数。
根据题意得出 $f_n = f_{n-1} + f_{n-2}$,对其求和计算 $s_n$,很容易发现 $s_n = f_{n+2} - 1$。
因为题目给了你 $f_n, s_n$,直接得到 $s_{n-1}, s_{n-2}$,整个数列昭然若揭。
而且为了简化问题,题目给出数据 $n - k \leq 10$,所以循环十次内就能求出答案。
出题人把 $n$ 的实际值限定在 $32767$ 内,这样还是有人强行用递归导致 $TLE$。
I. 小气的楠楠
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1614
解题报告:贪心题。谷歌面试出过。
先将两个数列排序,然后进行贪心。
两两对应后,有三种情况:同负,异号,同正,即:1
A: - + +
B: - - +
对于同号的两种,通过比较 $A_l B_l$ 与 $A_r B_r$ 的大小,决定取哪一个。
对于异号的部分,假如还需要取k对,那么从小到大取出k个正数作为第一行,从大到小取出k个负数作为第二行,两行都由小到大排列,最后从左到右对应相乘想加即可,切勿交叉相乘
下面是组容易错误的数据,建议替换 $M$ 来理解一下本质:
5 3或4
-1000 1 10 100 1000
-1000 -100 -10 -1 1000
J. 楠楠与瓜瓜
http://acm.zucc.edu.cn/JudgeOnline/problem.php?id=1615
解题报告:构造题。多校2015第九场。
通过相减得出愉悦值之差(记得取模),然后问题转化成寻找相同的两项,这样能很方便构造出相反的策略。
每次找出愉悦值最大的物品合并,愉悦值相减作为新物品的愉悦值。
这样对于 $n$ 个物品,愉悦值最大为 $m$;
第一轮,$n/2$ 次操作之后,愉悦值最大为 $\frac{2m}{n}$;
第二轮,$n/4$ 次操作之后,愉悦值最大为 $\frac{8m}{n^2}$;
第三轮,$n/8$ 次操作之后,愉悦值最大为 $\frac{64m}{n^3}$;
三次之后愉悦值最大只有6了,显然能出解,所以最后倒着 $dfs$ 把分配方法解出来即可。
窝不会告诉你们这题有彩蛋。
后记
刷题很重要,思考不能少;只刷不思考,药丸是吃枣。