鸽了好多天，今天终于开始写了233... 分块思想 实际上分块并不能算一种数据结构？ 分块的基本思想是，将原来的数据经过适当的划分(分成一个个块的样子)。 每次修改和询问时，都把一个块内元素当作整体处理，而边角直接暴力。 莫队就是基于分块思想实现的。 分块的复杂度主要取决于块长，根据均值不等式，块长为\(\mathjaxcal{O}(\sqrt n)\)时最优。当然不能一概而论。详细分析可以阅

其实很早就想学一下这类问题了,不过因为各种原因鸽到现在... links: 普通版 加强版 加强版的加强版 普通版 看大佬的博客学习了一下. 有一个很好懂的\(\mathjaxcal{O}(n^3)\)的\(dp\)方法. 设\(f-i\)表示大小为\(i\)的无标号树的组成方式. 儿子的子树大小为\(i-1\),假设有三个儿子大小为\(a,b,c\),\(0\leq a\leq b\leq

题目 给定一张\(N\)个点\(M\)条边的无向图，每条边要染一个编号在\(1\)到\(K\)的颜色。 你可以对一张染色了的图进行若干次操作，每次操作形如，在图中选择一个简单环（即不经过相同点的环），并且将其颜色逆（顺）时针旋转一个单位。 两种染色方案被认为是本质相同的，当且仅当其中一种染色后的图经过若干次操作后可以变成另一种染色后的图。 问有多少本质不同的染色方案，输出对\(10^9+7\)取模

Problem A. Alternating Paths 还没改啊,先鸽着吧... # Problem B. Dispatch Money 假设区间\([l,r]\)的逆序对数是\(f_{l,r}\). 显然\(f_{l,r}=f_{l+1,r}+f_{l,r-1}-f_{l+1,r-1}+[P-l>P-r]\). 即\(f_{l,r} + f_{l+1,r-1} \geq f_{l+1,r

Problem A. Good Subsegments \[2^{a-l}+2^{a_{l+1}}+...+2^{a-r}=2^x\] 可以发现,\(x\leq max(a-l,a_{l+1}...a-r)+log-2^{r-l+1}\). 所以固定一个端点时,枚举\(x\)的值去验证有没有等于\(2^x\)的区间是可行的. 但是\(2^x\)可能很大,高精度很麻烦也会\(TLE\),那怎么办呢?

写完一次就 AC 了是我没想到的... 可以假设增加了\(c\)亮度. 即求\(\sum\limits_{i=1}^{n}(x-i-y-i+c)^2\)的最小值. 把式子展开, \(\sum\limits_{i=1}^{n}x-i^2+\sum\limits_{i=1}^{n}{y-i}^2+nc^2+2c( \sum\limits_{i=1}^{n}(x-i-y-i))-2 \sum\limi

题目链接:https://loj.ac/problem/535 虽然写几个不同的方法写了三个小时,做这道题收获还是挺大/cy. 题目 \(n\)个烟火排成一排，从左到右高度分别为\(h-1,h-2,...,h-n\) ，这些高度两两不同。 每次 Yoko 可以选择两个相邻的烟火交换，这样的交换可以进行任意多次。 每次 Yoko 还可以选择两个不相邻的烟火交换，但这样的交换至多进行一次。 你的任

link 看完题目很容易想到二分答案,只用考虑怎么检验答案合法. 因为是一颗树的形态,所以在树上\(dfs\)时候修建赛道就行了. 对当前节点\(u\)分类讨论一下: 1. 儿子所代表的子树尽量内部修建赛道,因为这样一定不会更劣. 2. 把不能内部修建的最大的路径值返回给\(u\),看看它能不能和其他的不能单独修建的路径组合在一起. 这样得到的答案一定是当前最优的,且不会有边被重复使用. 因为不想

如果把原式化为卷积形式，就可以用\(FFT\)优化。　　 \(E_j=\frac{F_j}{q_j}=\sum\limits_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum\limits_{i=j+1}^{n}\frac{q_i}{(i-j)^2}\) \(E_j=\frac{F_j}{q_j}=\sum\limits_{i=0}^{j}\frac{q_i}{(i-j)^2

题目链接 从\(n\)片雪花里面选\(i\)个的方案数是\(\tbinom{n}{i}\)个. 根据Cayley定理,\(i\)个有标号的点形成无根树的方案数是\(i^{i-2}\). 所以选择\(i\)片雪花时的方案数是\(\tbinom{n}{i}i^{i-2}\). 对于一个区间答案是\(\sum\limits_{i=l}^{r}\tbinom{n}{i}i^{i-2}\). 因为询问较多可