济南大学第一届ACM校赛

2021-12-19 14:00:00 ~ 2021-12-19 17:00:00

T1：求兔子数量

容易发现每个月增加的兔子数就是这个月的老兔子数

老兔子数则是 3 个月前的兔子数

即递推式 f_i=f_{i-1}+f_{i-3}

\ T2：求最少交换次数使得一个排列有序

很多人都发现了 O(n^2) 暴力做法

就是每次把位置不对的换过来，其实这样换出来的一定是最优解。

但 O(n^2) 只能有 80 分

因为数列是个排列，满足 a_i<=n 且 a_i 两两不同，所以可以提前扫一遍确定每个数字的位置

这样换位置的时候就不用重新扫一遍了，时空复杂度 O(n)

\ T3：输入一个纸牌牌面判断有几个比它大

读入字符即可判断牌面是什么

如果读入的字符是 1, 则牌面是 10

\ T4：求最少几个半径为 r 且圆心在 x 轴上的圆能覆盖所有点

对于每个能量点，能覆盖它的圆的圆心位置集合是一个以自己为圆心，半径为 r 的圆

这个圆与坐标轴相交得到的是一个区间，也就是说，对于每个能量点，能覆盖它的圆的合法圆心位置集合是一段区间。

求出所有点对应的区间

现在问题变成每段区间内都必须有一个圆心，求最少圆心数量

把所有区间按右端点从小到大排序贪心，每次遇到一个区间内没有圆心，就取其右端点作为一个圆心。

显然这样得到的圆心数量一定最小

\ T5：每次可以前进 1-6 格，最多前进 m 次，使经过的格子上的数字和最小

比较裸的 DP

设 f_{i,j} 为前进到第 i 格共使用了 j 个骰子的最小难度和

转移方程比较显然

f_{i,j}=\min_{k=1}^{6} (f_{i-k,j-1})+a_{i}

\ T6：求 $n$ 有多少种不同的斐波那契数分解方案，其中使用的斐波那契数必须不同本来想出 $n<=10^{18}$ 把爆搜卡了，最后只出了 $10^{16}

在这个范围下答案很小，只有 10^7 左右

直接爆搜可能就有不少分

然后加个可行性剪枝就过了……

另外有一种严格 O(logn) 的做法，大概就是先贪心求一个合法的且没有相邻的斐波那契数的分解，然后通过记录斐波那契数的分解状态进行 DP

这里就不详细说了，详情见 P4133 题解