竞赛讨论区 > 广州大学第十四届ACM大学生程序设计竞赛题解

广州大学第十四届ACM大学生程序设计竞赛题解

头像
yuzining
编辑于 2020-07-19 12:24:18 APP内打开
赞 7 | 收藏 0 | 回复5 | 浏览2341

题目链接

A - 攀登

简单模拟所有情况即可。

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299107

B - Badeline

模拟即可。

假设第秒时Madeline的位置时,用一个数组存第秒时Madeline的位置,这样Badeline的位置都可以知道。

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299111

C - Celestial Resort

表示求这一堆数的最大公倍数,表示这一堆数的最小公倍数。

则有

那么如何求呢,显然使用传统的求最小公倍数的方法不可行(),因为最小公倍数的实际大小可能会很大,而这种求法也无法进行取模操作。

这时就需要用算术基本定理(唯一分解定理)去求了。

其中是质数。

这样所有数的最小公倍数就是

然后对于式子中的除的操作相当于乘以的逆元,再求和这题就做完了。

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299114

D - 清理杂物

题意转换:实现一个最近最少使用页面置换算法,每一次操作的时间复杂度是

需要用到一个双端链表来实现,链表头的优先级最高,链表尾的优先级最低。那么这时候如果加进来一个物品,如果链表里面有的,就先把这个物品在链表中删除。然后链表里面就没有这个物品了,之后再把这个物品插入到链表的头中就完成了操作。插入完成后如果这个链表的长度大于等于,那么就删除链表末尾的物品。

这样就涉及到一个问题,我如何知道这个物品在不在链表里面呢, 如果在的话在链表的什么位置呢?此时使用哈希表即可解决问题。C++中可以这样写unordered_map<int, listNode*>,如果链表中不存在则listNode*nullptr即可。而这里的哈希表中的key是,可以开大小为个的数组而不是用哈希表的方式这样会更快。(虽然哈希表理论复杂度是,实际还需要考虑哈希冲突的问题,而且哈希表的常数会更大)

链表可以一开始就分配好内存,避免后续动态分配内存的常数过大。

题解代码都比较丑 仅供参考

当然有其他的做法也可以通过。

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299115

E - 注意风


F - Mirror Temple

首先知道任意两个同一行或者同一列的都能到达,那么只需要将任意两个同行的红色泡泡和任意两个同列的红色泡泡在并查集中合并一起就可以了。

考虑代表第列的某一个红色泡泡,表示第行的某一个红色泡泡。如果新加入一个红色泡泡的坐标是,那么这个红色泡泡和第个红色泡泡在并查集中合并,同时这个红色泡泡也和第个红色泡泡在并查集中合并。(同行或同列不存在其他红色泡泡时就不需要合并了)

合并完了之后每一次询问看下第个红色泡泡和第个红色泡泡是不是在同一个集合内就可完成本题。时间复杂度

也可以排序加搜索通过本题。时间复杂度

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299121

G - 倒放

签到题。读取一行然后反转字符串输出即可。

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44288683

H - 羽毛

首先考虑如何用dp​去解决这个问题。

表示的是羽毛在第秒时停留在点的走过的边权之和的期望。

如果某个点没有出边,则加一条从边权为的边即可。

那么显然有

转移:

其中表示点的出边个数。

很显然这样直接转移的复杂度相当大。可以看出每一次转移其实基本都是相同的,而且总共点的数量不多,考虑用矩阵快速幂加速这个转移。

其中表示点到点的边的数量,题目中点的编号为则矩阵中是

逆元可以预处理,于是复杂度降至

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299123

I - 合作

对串建出AC自动机。

表示第位走到AC自动机上的状态的方案数,然后跑数位dp即可。

(AC自动机fail树上数位dp)

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299126

J - 登顶

枚举所有区间的右端点,假设当前枚举到,令表示区间的最大值,表示区间的最小值,那么答案增加

枚举到,b数组和c数组所更新的部分是一段连续的区间而且更新的这段区间的值是

考虑用一个可以区间覆盖和区间查询求和的线段树进行数据的更新,然后用两个单调栈来确定需要更新的区间的位置。

需要注意最终答案可能会超过,但不会超过,需要使用unsigned long long或者__int128去代替long long

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299128

K - 草莓失踪

因为斐波那契数在范围内的数量很少,只有二十几个。

那么枚举的复杂度不会很高,然后对于而言用完全背包的方式处理即可。

标程:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299129

5条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐