牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共17篇）

线段树/莫队杂题

高速公路(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

模拟13 题解

A. 矩阵游戏　　通过前40%的部分分，我们发现程序复杂度不能为$O(nk)$。　　设$h(i)$表示第$i$行最终乘的总系数，$l(i)$表示第$i$列。　　考虑每个点$(i,j)$，它对最终答案的贡献是$((i-1)*m+j)*h(i)*l(j)$。　　发现可以拆分为$(i-1)...

线段树映射分块 ST表

2019-08-06

0 409

模拟35 题解

A. 公园长度放不进状态，那就把遍历的点的个数放进状态，使长度最小。然后就变成了DAG上最短路问题。设个源点汇点，直接拓扑排序就完了。 B. 计划设$mn(i)$表示左端点选i，最小的愉快的旅行。显然$mn(i)$是单调的，单调指针扫过去就完了。然后对询问...

dp 拓扑排序单调指针分块期望高斯消元

2019-09-03

0 308

模拟49 题解

A. 养花利用根号的一些性质，可以得到很多在最坏情况下$n\sqrt n logn$的算法，然而出题人似乎根本没有给这个算法分的意思。正解是分块。预处理出每个块内对于每个k的答案。对于询问，大块直接统计，小块暴力就可以了。设值域为s，块的大小为q，那么总共有$\frac{n}...

分块 dp 最短路

2019-09-22

0 371

模拟50 题解

A. 施工又是利用了一些结论的题，因为想不到结论，经常做不出这种题。枚举两个不变的边界，那么中间的建筑必定被提高成相同的小于等于边界的高度。于是设$f_i$表示考虑前i个建筑，并且第i个建筑高度不变的最优答案。设对于转移（i，j），中间建筑的最优高度为t，可以写出dp转移方程。拆...

单调栈 dp 分块容斥直径

2019-09-23

0 469

模拟83 题解

A. 最大异或和异或是不进位加法。具有一个很好的性质：$a\ xor\ b=c$ $\rightarrow$ $c\ xor\ b=a$ 若所有点的异或和为$0$,那么显然平手。若异或和不为$0$,先手只要将最高位的$1$选到必胜。 B. 简单的括号序...

dp 结论题组合计数位运算分块最短路

2019-10-23

0 400

模拟91 题解

A. Dove 打扑克显然的结论是：超过$\sqrt n$的牌堆不会超过$\sqrt n$个。所以可以分块维护信息：对于牌数小于$\sqrt n$的，用一个桶维护。对于牌数大于$\sqrt n$的，用$vector$暴力插入删除维护。同时维护答案，为了做到$O(1)$修改，也用分...

分块 dp 线段树猫树位运算

2019-10-28

0 386

省选模拟6 题解

A. Yist 首先考虑怎样的情况答案是不收敛的。操作中涉及到对一个权值非$0$，并且不作除法的点的加法贡献。因为只要最终的答案，可以想到对每个点作为出边的贡献分别处理。部分分提示求出第一次迭代的贡献，发现对于每个点，贡献都是一个等比数列，所以只要代入求和公式就好了。然而暴力做的复...

分块图论后缀自动机 dp 树状数组

2020-01-13

0 393

省选模拟8 题解

A. 序列发现较难维护的是后一个信息。所以考虑直接分块维护。为每个块开一个vector，表示这个块中所有元素对vector中的所有元素依次取过max。因为取max的性质，这个vector中的元素只需要保留单调递增的部分。在查询的时候和暴力重构一些块的时候，可以直接在vector中...

网络流二分图分块线段树

2020-01-17

0 553

省选模拟15 题解

A. 倒计时考虑50%的部分分。分块来削这个数。后四位形成一块，预处理出9991~9999在前五位的最大值为0~9情况下分别会削到的值和削的次数。对于零散的后四位暴力削，这样就可以通过根号预处理，根号削$n$了。容易发现，对于$n$比较大，我们多分几次块，每次用较小一级的块来预处...

网络流后缀自动机分块容斥

2020-02-02

0 366