牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共4篇）

线段树/莫队杂题

高速公路(road) 如果直接维护一个点到其它点的距离，维护起来很困难。不妨转换思路，考虑每个点对答案的贡献，设询问区间为$l,r$，则点$i$的贡献为$(i-l)*(r-i)*w[i]=(-i^2+(l+r)*i-l*r)*w[i]$。对于$i^2*w[i],i*w[i],w[i...

线段树莫队分块

2019-07-26

0 420

模拟64 题解

A. trade 暴力dp，复杂度$O(n^2)$。然后70分等死。考试快结束的时候，突发奇想。快速改了滚动数组，将第二维的上界设为1000。即只考虑同时存1000个货物，然后突然过了大样例。其实只是想多偷一点分，然后就A了，就非常偷税。所以正解其实是基于堆操作的反悔贪心。...

贪心莫队组合计数并查集

2019-10-08

0 350

模拟69 题解

A. chess 想一下合法方案是怎样的。因为要保证每一个正方形合法，所以新加的一列中棋子个数等于刚刚删去一列的棋子个数。当$m$很大的情况下，$mod\ n$相同的列转移系数都是相同的。接着考虑，其实$m\ mod\ n$列转移了$m/n+1$次，而$n-m\ mod \ n$列转移...

dp 组合计数单调栈莫队离线并查集

2019-10-12

0 304

省选模拟88 题解

A. 或许容易发现 $u,v$ 联通仅当 $u \oplus v$ 能被集合 $S$ 通过 $\oplus$ 运算表出。所以只需要维护线性基内元素个数。然后暴力的做法就是直接线段树分治。然后有一个能进行删除的离线操作是，不断尝试用被删除最晚的替换线性基中的元素。 B. 这就是 ...

线性基莫队根号分治 dp 状压

2020-05-05

0 381