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

请注意,文章中部分理解可能已被笔者废弃,本文最后更新于:7 个月前

链接


题目列表

RANk.png

A-傻子楼梯 ?

题目链接 Attempted

队列模拟即可

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

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

B-cold爱吃小蛋糕√

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

也就是,会浪费 K2\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(n2)O(n^2)的做法吗。

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

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

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

F-你一定会种树吧2.0

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

G-郑老板爱玩博弈论√

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

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

H-琴

题目链接 Attempted

数学 - 数论 - 整除分块

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

I-简单数学2.0

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

J-简单水题√

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

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

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

K-学不会的知识*

L-写不完了 *