竞赛讨论区 > 【题解】2020牛客寒假算法基础集训营第二场

【题解】2020牛客寒假算法基础集训营第二场

头像
咕咕咕_
编辑于 2020-02-21 16:21:27 APP内打开
赞 32 | 收藏 36 | 回复53 | 浏览12074

2020-2-17 G 题数据已加强但未重测此前提交。

A. 做游戏

尽可能让 牛牛的每次出 剪刀/石头/布 对应到 牛可乐出 布/剪刀/石头。

时间复杂度

42841945

B. 排数字

以外不需要考虑。

要让 子串最多一定是 ,这样后面的串可以用前面的 ,数量为 。(可以理解为前面一个 后面 循环)

时间复杂度

42857464

C. 算概率

表示前 道题做对 道的概率

转移时考虑第 道题是否做对,转移方程为:
时间复杂度

42841954

D. 数三角

一个三角形的三边长 最长 )满足 (或存在两条边向量的点积 ),则该三角形为钝角三角形。

枚举三个点判断即可,注意判断共线和不要算重。

时间复杂度

42841973

E. 做计数

两边平方,得 ,显然仅当 都是整数且 为完全平方数时才会对应一个符合条件的

枚举 中所有的完全平方数(完全平方数可以表示为 ,只需要枚举 ),再枚举这个完全平方数的因数,统计答案。

枚举完全平方数 枚举因数,时间复杂度 ,可以进一步优化。

42841984

F. 拿物品

假设物品已经被选完,此时 牛牛选择的物品 属性的价值和是 , 牛可乐选择的物品 属性价值和是

如果 牛牛的 物品与 牛可乐的 交换,则 ,对于 牛牛(目标是最大化 )来说会变得更优仅当 化简就能得到),对于 牛可乐也一样。所以两人都会优先选择 最大的物品。

将物品按照两个属性的和从大到小排序,依次分给两人即可。

排序时间复杂度

42842001

G.判正误

直接计算会 TLE / MLE ,考虑在模意义下进行计算,若 ,则原式有概率成立,多选择一些模数以提高正确率。

42842014

H.施魔法

先将元素按能量值排序,下文默认已排序

可以证明存在一个最优方案,满足每个魔法一定消耗一段连续的元素。

表示用掉前 个元素的最小代价。

图片说明

维护 的前缀最小值就能 转移了。

DP 过程时间复杂度

42842367

I.建通道

首先将权值去重(权值相等的点连接代价为 ),设去重后有 个点,接下来找到最小的二进制位 ,满足存在 的这个二进制位是 且存在 的这个二进制位是 ,答案就是 (相当于所有这位是 的点与 点连边,是 的点与 点连边)。

排序和去重以外时间复杂度 ,没有卡 ,好像两个 也过了。

42852180

J. 求函数

注意: 时视

对加号左右分别用线段树维护,考虑如何合并两个相邻区间

区间

一棵线段树维护 ,另一棵维护 即可。

同阶,时间复杂度

42842027


C 题:不太懂为什么这么少人过。UPD:好像是因为不懂模意义下运算...emmmmmmm

D 题:使用浮点数请考虑精度问题 ,没 eps 说卡精度就有点那啥..。

G 题:考虑到这个题卡固定模数比卡字符串哈希轻松很多(只要让结果是模数的 lcm 即可)就卡了一些模数,有一些数据不知为何没传上去;使用 math 库中的 pow 函数可以通过,是真的没想到(由于 Yes 的数据都比较有特点,可能被编译器优化了)。以及请不要再纠结哪个模数能AC哪个不能,因为模数相比最终结果小太多,很多模数可能被卡(不管是不是刻意),应该做的是多选一些模数。

以及可能还有一些小问题影响了做题体验,这里说声抱歉

关于样例强度:没有任何义务提供强样例

推锅:赛时提问的回答有个别态度不好,那不是我

有其他问题请在评论中提出~

53条回帖

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

等你来战

查看全部

热门推荐