Colythme

首先有一个性质 对于 $n \ge 11$，操作 $1$ 必定有解 一个来自 $\text{Okami}$ 的严谨证明： 考虑互不相同的数 $x, y, z, …$，则有 123xx y x+yx y z x+y x+z y+z x+y+z 也就是对于 $n$ 个互不相同的数它们显然可以拼出 $2^n - 1$，那么根据抽屉原理，则有 $2^n - 1 \ge 1000$ 时必定有解，则命题成立 那么剩下的就直接 $\text{bitset}$ 优化背包就好了（注意可以直接背包因为若集合 $X$ 和 $Y$ 同时选了一个数，那么它们同时去除该数也是相等的），至于操作 $2$ 的影响则直接树状数组统计每个数要立方几次，由于 $\bmod V$，那么直接倍增处理即可 单词询问复杂度 $O (\frac{(r - l + 1)^2V}{32})$ 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 ...

这题真的是写到心态爆炸。。 一道边分治 + 虚树 前置知识边分治顾名思义，就是选择一条边，类似点分治对所有经过该边的路径进行处理，但与点分治不同的是，边分治可能会被菊花图卡到 $O (n^2)$，故此时需要重构树，将之变为度数不超过三的二叉树 树重构通过建立新的虚点进行重构，但要满足加入的虚点不影响最后答案计算 12345678910111213141516171819void rebuild (int root, int father) { int nf = 0; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; LL w = Link[i].w; if (v == father) continue; if (! nf) { Insert (root, v, w), Insert (v, root, w); nf = root; } else { int k = ++ m; // 虚点 Insert (nf, k, 0), ...

斯坦那树百度释义 斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。 即最小斯坦那树即为并非选择所有的结点，而是选择一部分结点，为保证它们连通，且求解最小开销 题解斯坦那树模板 发现直接表示点的存在性没有意义 设函数 $f[i][state]$ 表示：对于点 $i$，其它结点与其连通情况 那么有两种转移 其一、由其子集转移$$f[i][state] = \min\limits_{sub \in state} \{f[i][sub] + f[i][\complement_{state}sub] - value_i\}$$之所以要减去 $value_i$ 是因为会算重 附：枚举子集的方法 1for (int sub = state & (state - 1); sub; sub = (sub - 1) & state) 其二、由相邻当前状态下结点转移$$f[i][state] = \min\limits_{state_p = tru ...

计数问题也许可以转化为矩阵乘法形式 比如若该题没有不能在一条边上重复走的条件限制，那么直接将邻接矩阵转化为矩阵乘法即可 故 矩阵乘法计数对于计数问题，若可以将 $n$ 个点表示成 $n \times n$ 的矩阵，并且可以保证中途转移对象不会变化，即可用矩阵乘法计数 至于该题那么考虑该题，加入了不能重复在一条边上走的限制，那么最简单的思想就是拆点，并且让改点屏蔽掉当前方向，但是如果考虑边，一条无向边可以拆成两条有向边，那拆出来的就比点少很多了，故考虑点边转化 那么只要在起始点加一条超级源边，同样矩阵乘法即可统计答案 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110#include <io ...

第一次做到这种倍增题，有点有趣 首先区间内的每个点对应相等用并查集维护一下就好了，显然最后的答案就是（并查集个数为 $t$） $9 \cdot 10^{t - 1}$ 当然这样会造成 $O (n^2)$ 的复杂度，那么通过倍增来优化，即将区间二进制拆分，然后每次将 $[l_1, l_1 + 2^k - 1]$ 与 $[l_2, l_2 +2^k - 1]$ 合并，其中 $k$ 为二进制拆分结果所得幂次的部分，那么这样修改就变成 $O (n \log n)$ 了 对于查询，显然是不能直接查询了，那么就通过由大区间到小区间的传递（即将大区间拆分为左右两段，然后分别与之祖先拆分得左右两段合并）来将信息转移到最小的（即以点为单位的）区间段上 那么最后即 $O (n)$ 查询并查集个数即可 故该倍增整体思想即为：将以点为单位处理改为以幂次区间段为单位处理 $\rightarrow$ 将幂次区间段的信息转移到小区间直至单位区间 $\rightarrow$ 答案处理 代码12345678910111213141516171819202122232425262728293031323334353637 ...

前置「Hall定理」 二分图G中的两部分顶点组成的集合分别为X, Y(假设有|X|≤|Y||X|≤|Y|)。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，|W|≤|N(W) 题解由于最坏情况任选 $k$ 个是选一端连续的区间 $[l, r]$，根据Hall定理的 $|W| \le N(W)$ 可以得到$$\begin{aligned}sum[l, r] &\le (r - l + 1 + d) \cdot k \\sum[l, r] - (r - l +1) \cdot k &\le d \cdot k\end{aligned}$$那么就可以在线段树中将每个点的权值设为 $value - k$，然后维护最大子段和 $sumax$ 那么最后 $sumax \le d \cdot k ? TAK : NIE$ 即可 代码1234567891011121314151617181920212223242526272 ...

题意在一棵树上选出 $k$ 条可相交的链使得被覆盖的点数最多，求该最大值 题解说实话这个解法是真的厉害 显然题目可以看作选出 $k \times 2$ 个叶子节点，然后将它们互相连接最终覆盖的点的最大值 再考虑删去选中的 $k \times 2$ 个叶子节点后，向内一层的点最多只会有 $k \times 2$ 个点有贡献 同理继续内推 于是上述过程即由叶子节点开始拓扑，对于拓扑的每一层，令点 $i$ 拓扑深度为 $depth_i$，$total_i$ 表示拓扑深度为 $i$ 的点的个数，即，将每一个拓扑层重新看作叶子节点，再在当前拓扑层中选出至多 $k \times 2$ 个“叶子节点”，故$$\min (k \times 2, total_i)$$即为拓扑深度为 $i$ 的层的答案贡献 将它们累加起来即可 复杂度 $O (n)$ 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 ...

主要题意求字符串$S$与$T$不同的子串总数 题解先考虑$l = 1, r = |T|$的情况： 因为任意子串为字符串前缀的某些后缀，那么令$Lim[i]$表示$T[1…i]$在$S$上所能匹配的最大长度，$Posi[i]$表示$T$的后缀自动机上的点$i$的$endpos$集合中最靠前的位置，那么答案即为 $$Ans = \sum\limits_{i = 1}^{nodes} \max (0, Len[i] - min (Len[Father[i]], Lim[Posi[i]]))$$ 接下来考虑$l, r$任意的情况： 原来能否在$S$的后缀自动机上往下走的判断依据只有当前节点是否存在$c$边，那么有了$l, r$的限制，就多需要判断向下的这个节点的$endpos$是否有存在于$[l + len, r]$（$len$表示已匹配长度）区间的位置，$endpos$集合用动态开点线段树维护一下就好了 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 ...

题意求解 $1 \le x \le n, ~ 1 \le y \le m$ 中满足在 $k$ 进制下 $\frac{x}{y}$ 是有限循环小数的个数 题解很好然后我一开始在计算器上敲了半个小时然后由于眼瞎并且归纳能力差并没有发现规律 设 $\frac{x}{y}$ 的循环节长度为 $l$，则有$$\begin{aligned}\frac{xk^l}{y} - \left\lfloor\frac{xk^l}{y}\right\rfloor &= \frac{x}{y} - \left\lfloor\frac{x}{y}\right\rfloor \\xk^l - \left\lfloor\frac{xk^l}{y}\right\rfloor y &= x - \left\lfloor\frac{x}{y}\right\rfloor y \\xk^l &\equiv x \pmod y \\k &\equiv 1 \pmod y\end{aligned}$$也就是说只要满足 $y \bot k$ 即可满足题意，故可将问题化为$$\begin{aligned ...

首先易得方程，且经过变换有 $$\begin{aligned} f_i &= \min\limits_{dist_i - lim_i \le dist_j} \{f_j + (dist_i - dist_j)p_i + q_i\} \\ f_j &= p_idist_j + f_i - dist_ip_i - q_i \end{aligned}​$$ 在一条直线上时，斜率优化可以用普通$CDQ​$分治实现（会不会过于麻烦？），那么对于在树上斜率优化时，考虑点分治 这时就在点分治中运用$CDQ$分治的思想，即使用在当前重心管辖范围内的通向根节点的那一条链上的节点来更新其它节点就好了 注意在分治中的斜率优化时在凸包上加点和更新右侧节点答案要同时进行，不然当前最优解可能会在后面由于斜率被删去，导致答案错误，还有由于下面代码是由深度由小到大处理的，所以是反着维护下凸包，即上凸包 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...