牛客练习赛 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 在哪边取到，在右边取到的是一段前缀，这段前缀的贡献可以用与法一相同的方法算。在左边取到的是一段后缀，可以用类似的方法算，但复杂度还是 。总复杂度同上。

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

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