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哪个不能，因为模数相比最终结果小太多，很多模数可能被卡（不管是不是刻意），应该做的是多选一些模数。

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

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

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

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