竞赛讨论区 > 牛客练习赛 95 题解
头像
Feecle6418
编辑于 2022-01-20 22:32
+ 关注

牛客练习赛 95 题解

A

直接模拟即可。

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50472832

B

由叉积计算面积的公式

可以发现面积是否为整数只与 三个点的 坐标奇偶性有关,并且由于问的是非整数,可以忽略三点共线等情况(这些情况面积是整数 ,不会计入答案)

故只需记录每种奇偶性的坐标的数量, 枚举算答案,复杂度

std https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50472839

C

,则操作等价于区间 减一,要把 变成

差分,相当于每次选择 使 减一、 加一。

从前往后扫描,维护变量 ,扫描 时,先判断 ,若 就让 ,若 ,就用 抵消。若 消完 还消不完就无解。若扫描完后 还有剩余就无解。

若有解,记录下哪个位置的差分和哪个位置的差分抵消的就可以输出方案。可以看 std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50472857

时间复杂度

D

答案可以写成(省略了下取整符号)

意思是,枚举 gcd 的约数是 ,有后面那么多种情况会对答案造成贡献( 都要是 的倍数)。

对后面的东西整除分块,可以把问题转化为:

  • 有一个初值为 的序列。
  • 次操作,区间乘。
  • 最后求所有数的和。

可以用类似差分的方法线性维护,特殊处理乘

std 使用了一些奇技淫巧卡常,但其实完全不卡常也能 3s 左右无压力过,只要复杂度不带 log。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50472873

E

期望线性性,,同时 可以 维护。

具体地说,开个 map 之类的维护这个位置还能用哪些颜色,修改的时候计算以下贡献。

具体的式子可以看 std https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50472879

我觉得后面应该比较容易理解。

F

有两种方法。

法一:建 min 的笛卡尔树,笛卡尔树上启发式合并 trie 树,需要在每个点维护子树内每个位上有几个。

合并时需要把小的那边的所有的放到大的那边查贡献,查询一次是 的,总复杂度

法二:对序列分治,对固定的右端点分类讨论 min 在哪边取到,在右边取到的是一段前缀,这段前缀的贡献可以用与法一相同的方法算。在左边取到的是一段后缀,可以用类似的方法算,但复杂度还是 。总复杂度同上。

其实开 也跑得很快,开 只是为了让选手敢写。

这个题的数据应该还是不算弱吧(

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐