ZevenWu

分类

题解(3)

/ 注册

全部文章（共3篇）

题解

题解：非常巧妙的一道题。直接搜索的话是log^3的，如何优化？“<=3”是问题的突破口。我们按照位数划分，0-15为一块，16-31为一块，以此类推，一共分成了4块。由于误差<=3，则设当前查询为x，若数组中有y和x相似，则y和x必然有一块完全相等！我们把每一个数组中的y挂到对应的块的...

2020-05-16

2 542

牛客挑战赛39 C.牛牛的等差数列

solution：显然，<25的质数共有9个：2、3、5、7、11、13、17、19、23.它们的乘积的范围在2e9左右，设为d。一个显然的做法是对每一个质数维护答案。然后就是一个区间加等差数列区间求和，线段树即可。这样是O(9nlogn).也可以只维护一个%d的线段树，最后查询完在%即可。这...

2020-04-18

0 648

牛客挑战赛39 A.聚会

solution：设mx为最大点的坐标，mi为最小点的坐标的绝对值。不妨设mi<mx。则上限为mx。首先有一个结论：一定有一个点在原点。证明如下：分类讨论，不妨设左边叫A，右边叫B。若A<B<0：这种答案就为上限。若A<0<B：在这种情况下，A、B绝对值较小的那一边的所...

2020-04-18

4 704