2022—SWJTU寒假选拔赛第二场复盘

链接


题目列表

RANk.png

A-傻子楼梯 ?

题目链接 Attempted

队列模拟即可

要转变方向当且仅当不同方向的人已抵达电梯,且该方向的下一个人还未到达电梯

然而从赛场到现在我一直wa在test7上,现在也不知道怎么错的。

B-cold爱吃小蛋糕√

\(Cold\) 可以无限次吃蛋糕,每次吃掉蛋糕的重量是一个正整数且任意,只要并且不会超过原本蛋糕重量的一半。因为可以无限次合并蛋糕。所以,可以贪心的考虑将所有蛋糕合并,然后次多次将蛋糕吃到 \(K\) 的重量,然后再最后吃一口最重的就是最优解。

也就是,会浪费 \(\frac{K}{2}\) 上取整重量的蛋糕。

C-郑老板玩方块√

题目重述:判断给出的八个坐标能否构成正方体

最开始看到这个大模拟我是非常不想做的,但是看了其他题不是很有把握以及榜单上很多人这道题就写完了(神仙速度)然后就花了不少时间(30min?)把这个搞了出来。

因为只有500组数据,时间很宽裕,我就用了个O(T88*8)的暴力:对于每个点,计算其他七个点与它的距离(直接不用开方),用距离进行个冒泡排序,再判断该点与该点最近的三个点构成的向量长度是否相等,是否垂直。

D-风神瞳√

这是一个最短路模板+无穷背包模板的题目。

首先,用Dij或SPFA跑出出发点 S=1 到每个点的最短距离,对于每个非出发点节点相当于背包的物品:花费时间为 dis[i]*2、收益为 a[i]。每个“物品”有无限个,然后无线背包dp就行。

E-cold不会字符串

我一直没想到做法是因为我把题目:“如果给你一个P串,是否能构造出来一个T串使得cold的代码不通过”看为了“如果给你一个T串,是否能构造出来一个P串使得cold的代码不通过”,话说如果这样改能有低于\(O(n^2)\)的做法吗。

题目的意思是已知这么一段错误的代码然后给我们一个匹配串,问能否构造一个串使得这个算法得到的答案是错误的。

很明显这段代码错误的原因在于指针 没有回溯。那么怎样的串我们可以把它 hack 掉呢

倘若 next[i]>0 的一定会被 hack ,学过KMP的同学知道,KMP就是求解前后缀匹配情况即数组回溯进行匹配的,但改错误代码其没有回溯,因此产生了错误。那么知道了这点以后,甚至可以不用求 next 数组了,直接判断串中是否有与 s[1] 相同的,有相同的必然是next>1了。

F-你一定会种树吧2.0

我知道这是个线段树,但我没时间去改模板了。也确实不想写。

G-郑老板爱玩博弈论√

这道题属于是,一看题面长度吓死人,仔细看后可以算,算出来后直觉离谱的题。因为答案就输出一个0.0000

老板对于每个选择都是 \(\frac{1}{20}\) 的概率,我直接写了个程序跑出来,无论学生取什么数字,期望得分都是 \(0\),

H-琴

题目链接 Attempted

数学 - 数论 - 整除分块

\(O(T\sqrt{n})\)

I-简单数学2.0

考虑离线莫队。 题目相当于找出每段区间里每个数字的所有因子,找到其出现次数最多的因子的个数。 但是 ai 最大可达到 \(1e^6\), 因子数量太多。仔细想想会发现我们并不需要求出所有因子,只需要求出所有质因子即可,又因为一个数的质因子个数非常少(最多不超过 7 个,记为 \(k\)),因此我们可以预处理所有数的质因子后把问题近似为求区间众数。维护每个质因子出现的次数和出现 i 次的质因子的数量,即可离线后使用莫队求解本题。 由于 n 和 q 为同一数量级,总时间复杂度为 \(O(kn\sqrt{n})\)

J-简单水题√

看到棋盘格和从左上角走到右下角,只能向右边或者向下行走首先想到递推。

因为每个格子上只能是\(1\)\(0\),想到可以用路径和表示路过了多少个“\(1\)”和“\(0\)”,为了记录到达每个格子的各种已经路过数量的方案数,对每个格子 \((i,j)\) 还得开个 \(i+j-1\) 来储存各种可能的方案数量。即要开个dp[n][m][n+m]的三维数组,再在二维上对每个格子dp。

然后我用\(dp[510][510][1050]\)写了出来。然后提交直接 ME。于是想了想,压缩了第一纬度空间。

K-学不会的知识*

L-写不完了 *