2020-07-19 12:24 已编辑没上过大学 C++

关注

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

题目链接

A - 攀登

简单模拟所有情况即可。

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

B - Badeline

模拟即可。

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

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

C - Celestial Resort

$\gcd(x,y,z,...)$ 表示求这一堆数的最大公倍数， $lcm(x,y,z,...)$ 表示这一堆数的最小公倍数。

令

$q=lcm_{i=1}^{n}(a_i)$

则有

$\sum\limits_{i=1}^{n}b_i=\sum\limits_{i=1}^{n}\frac{p}{a_i}$

那么如何求 $q$ 呢，显然使用传统的求最小公倍数的方法不可行（ $lcm(x,y)=\frac{x\cdot y}{\gcd(x,y)}$ ），因为最小公倍数的实际大小可能会很大，而这种求法也无法进行取模操作。

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

$a_i=\prod\limits_{j=1}^{m}{p_j}^{c_{i,j}}$

其中 $p_j$ 是质数。

这样所有数的最小公倍数就是 $q=\prod\limits_{j=1}^{m}{p_j}^{\max\limits_{i=1}^{n}c_{i,j}}$ 。

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

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

D - 清理杂物

题意转换：实现一个最近最少使用页面置换算法，每一次操作的时间复杂度是 $O(1)$ 。

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

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

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

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

当然有其他 $O(m\log(m))$ 的做法也可以通过。

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

E - 注意风

F - Mirror Temple

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

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

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

也可以排序加搜索通过本题。时间复杂度 $O(n\log(n)+q)$ 。

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

G - 倒放

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

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

H - 羽毛

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

令 $dp[i][j]$ 表示的是羽毛在第 $j$ 秒时停留在 $a$ 点的走过的边权之和的期望。

如果某个点 $u$ 没有出边，则加一条从 $u$ 到 $v$ 边权为 $0$ 的边即可。

那么显然有 $dp[any][0]=0$ 。

转移：

$dp[v][j]=\sum\limits_{u,w\in v\text{的入边}}^{}\frac{dp[u][j-1]+w}{len(u)}(j>0)$

其中 $len(u)$ 表示 $u$ 点的出边个数。

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

$\begin{pmatrix}\frac{num(0,0)}{len(0)} & \frac{num(0,1)}{len(0)} & \frac{num(0,2)}{len(0)} & \cdots & \frac{num(0,n-1)}{len(0)} & \frac{\sum\limits_{v,w\in 0\text{的出边}}w}{len(0)} \\ \frac{num(1,0)}{len(1)} & \frac{num(1,1)}{len(1)} & \frac{num(1,2)}{len(1)} & \cdots & \frac{num(1,n-1)}{len(1)} & \frac{\sum\limits_{v,w\in 1\text{的出边}}w}{len(1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \frac{num(n-1,0)}{len(n-1)} & \frac{num(n-1,1)}{len(n-1)} & \frac{num(n-1,2)}{len(n-1)} & \cdots & \frac{num(n-1,n-1)}{len(n-1)} & \frac{\sum\limits_{v,w\in n-1\text{的出边}}}{len(n-1)} \\ 0 & 0 & 0 & \cdots & 0 & 1 \end{pmatrix}\begin{pmatrix}dp[0][j] \\ dp[1][j] \\ \vdots \\ dp[n-1][j] \\ 1\end{pmatrix}=\begin{pmatrix}dp[0][j+1] \\ dp[1][j+1] \\ \vdots \\ dp[n-1][j+1] \\ 1\end{pmatrix}$

其中 $num(i,j)$ 表示点 $i$ 到点 $j$ 的边的数量，题目中点的编号为 $i$ 则矩阵中是 $i-1$ 。

逆元可以 $O(m)$ 预处理，于是复杂度降至 $O(n^3\log(t)+m)$ 。

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

I - 合作

对串建出AC自动机。

令 $dp[i][j]$ 表示第 $i$ 位走到AC自动机上 $j$ 的状态的方案数，然后跑数位dp即可。

（AC自动机fail树上数位dp）

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

J - 登顶

枚举所有区间的右端点，假设当前枚举到 $j$ ，令 $b_i$ 表示区间 $[i,j]$ 的最大值， $c_i$ 表示区间 $[i,j]$ 的最小值，那么答案增加 $\sum\limits_{i=1}^{j}b_i\cdot c_i$ 。

从 $j$ 枚举到 $j+1$ ，b数组和c数组所更新的部分是一段连续的区间而且更新的这段区间的值是 $v_{j+1}$ 。

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

需要注意最终答案可能会超过 $2^{63}-1$ ，但不会超过 $2^{64}-1$ ，需要使用unsigned long long或者__int128去代替long long。

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

K - 草莓失踪

因为斐波那契数在 $[1,10^5]$ 范围内的数量很少，只有二十几个。

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

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

全部评论

推荐最新楼层

甘樂哟

广州大学 Java

黎爷在编译器没反应过来的时候就A了，所以不用考虑

4 回复分享

发布于 2020-07-18 22:35

你滴寒王7

门头沟学院 C++

黎爷我想问下E题是不是有种情况没有考虑, 他第一段向右移动的距离 a 特别特别长，第二段像左移动的距离 b 特别特别长，第三段距离很小可以无视。同时他这一整个周期的距离由于 a 和 b 互相抵消导致也很短，然后 a 虽然很长但是他不足以一次性直接到达右边他可能两边的距离是 m=a+x ，然后经过几次周期运动的铺垫他可能当前距离达到 x，然后一次 a 一举到达右边

2 回复分享

发布于 2020-07-18 22:21

김태연0309

北京航空航天大学全栈开发

题目不错！都挺有意思得，喜欢~~~ J 有点想不动了，看了题解觉得有点意思！

1 回复分享

发布于 2020-07-19 16:12

肖战公关团队

楼主

没上过大学 C++

E题题解：https://blog.nowcoder.net/n/2c953483a71346149fe31921a47d44a3

点赞回复分享