bzoj [Lydsy1708月赛]比特战争 其实不是那么想写，但是这题毕竟困扰了我很久，还是动笔了，可能笔者自己也没有很懂，希望大家能谅解一下。本文仅仅是自己的想法罢了。 对于一个连通分量我们可以考虑两种形式也就是要么其自己内部占领，要么是外面来的士兵占领。 如果是外面来的士兵肯定贪心得选取最小的边。 对于最小的边我们不妨考虑一下最小生成树，如果一个连通分量在最终情况下是被外部占领的，那么肯定是选择一个最下的边。如果其不被占领肯定又是一个子问题。 这里通过观察可以得到一个结论，对于最优的答案存在一种构造方案使得对于一个联通块至多只有最小的边被加入。 对于一个联通块如果是被别人占领显然是加入最小的边。 如果其是内部占领之后和其相邻的所有边都不会因为要占领这个联通块而被加入。 我们直接贪心枚举每条边的加入情况即可。 我们不妨考虑从小到大加边，每次更新答案。对于两个联通块其打通的最小花费是 $\max(\max(w, b_v), b_u) \times \min(a_u, a_v)$。我们维护两个值即可。 123456789101112131415161718192021222324 ...

CF855G Harry Vs Voldemort 根据 $\tt\color{black}{h}\color{red} ater$ 的话，这个东西放到现在有 $2800$。 显然恶评。 就是对于一个 $3$ 元组，我们发现本质就是树上两条路径合并的问题，那么我们像淀粉质一样将每个点作为 $\tt Lca$ 计算答案即可。 那么一开始的答案就是 $ans_u = (n - 1) \times (n - 1) - \sum_{v \in son_u} siz_v \times siz_v - (n - siz_u) \times (n - siz_u)$。 本质上就是考虑不取当前的点，任意的点对，为了方便我们就是考虑到 $(i, i)$ 这样的点对，反正也会减去的。 之后考虑加入一条边就是增加一个环，那么我们对于环中的每一个点的答案本质是相同的，我们对于一个环可以一起计算，不妨设其深度最浅的节点为 $u$，整个环的儿子集合为 $son$，整个环的元素个数是 $s$。 都在环上 $s \times (s - 1) \times (s - 2)$。 一个在环上 $2 \ti ...

CF804F Fake bullions 说实话这题根据套路应该很容易做出来，但是感觉想要通过思维做出来 $\dots$ 一个二合一的题目。 $\tt Part\ 1$ 首先考虑题目给定的限制，如果 $u \to v$ 而且 $u$ 的第 $i$ 个人有金条，那么 $v$ 中第 $j$ 个人有假金条当且仅当 $S_ux + i = S_vy + j$ 根据 $\tt Lucas$ 定理可以得到符合条件当且仅当 $\gcd(S_u, S_v) | j - i$。 我们考虑这个的传递性，也就是 $\gcd(\text{path}(u, v)) | j - i$。对于竞赛图我们不妨考虑缩点之后再还原。 因为竞赛图缩点之后的特殊性质，每个点都向后面的所有点连边，所以可以直接根据拓扑序列进行计算。 对于一个点因为同余的性质可以得到 $ans_i = \dfrac{ct_{bel_i}\times S_i}{\gcd(bel_i)}$。 $\tt Part\ 2$ 之后我们可以求出每个点的最大值和最小值称其为 $mx_i, mn_i$。 对于一个集合 $B$ 最可能合法的情 ...

CF762F 其实这个题也不是很复杂。 首先题目背景里说的是一个联通子图！！！ 发现数据范围其实不是很大，我们不妨钦定一个节点为根$S$ 的节点。那么本质上对于 $S$ 中的每一个节点我们都需要对 $T$ 进行一次匹配。 显然因为是联通子图是不可能进行树哈希的，我们考虑进行树形 $Dp$。 不妨考虑设 $f(u, v, S)$ 表示对于 $u \in S, v \in T$ 的情况，已经匹配了 $T$ 中集合 $S$ 的方案数。 但是题目中说明的是无根树，如果再对于 $T$ 钦定一个根的话会产生有些形态没有计算的情况。 所以我们不得不考虑重复计算的情况，也就是一个情况能计算几次。本质就是一个和 $T$ 本质相同的树会被计算几次。 这两个相除即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 ...

说实话这个东西其实挺有趣的。 证明的话其实我不是很会，貌似是用矩阵证明是一个范德蒙德矩阵是有唯一解的。 我们直接举例子来说吧。 $f(n) = f(n - 1) + f(n - 2)$。 设 $F(z) = \sum_{i = 1}^{\infty} f(i) z^i$，显然存在这样的方程满足。 $$F(z)z^2 = F(z)z + F(z)$$那么我们将其移项可以得到： $$F(z)(z^2 - z - 1) = 0$$显然 $F(z)$ 不为 $0$，那么我们让后面的那个东西 $= 0$。其实后面的柿子就是特征方程。 我们容易解出两个解 $z = \frac{1 \pm \sqrt 5}{2}$。 得到 $f(n) = Ax_1^n + Bx_2^n$ 我们带入前面的两个值 $f(1) = f(2) = 1$ 得到 $A = \frac{1}{\sqrt 5}, B = - \frac{1}{\sqrt 5}$ 可以求出通项。 $$f(n) = ...

emmm，先说明一下，作者其实不是很会，有些问题请指出。 $\color{red}\tt \text{定义}$ $\Theta(f(n))$ 表示时间复杂度渐进的上下界。 $\Omega(f(n))$ 表示时间复杂度的下界。 $O(f(n))$ 表示时间复杂度的上界。 $\color{red}\tt Master\ Theorem$ 设递推式 $T(n) = aT\left(\dfrac{n}{b}\right) + f(n)$。 设常数 $\epsilon > 0, k \ge 0$， $$T(n) =\begin{cases}\Theta(n^{\log_ba}), f(n) = O(n^{\log_ba - \epsilon}) \\Theta(f(n)), f(n) = O(n^{\log_ba + \epsilon}) \\Theta(n^{\log_ba}\log^{k + 1}n), f(n) = O(n^{\log_ba} \log^kn)\end{cases}$$ 也就是考虑递归的时候相邻两层之间的公比， ...

CF757G Can Bash Save the Day? 时间复杂度分析好题（大雾）。 将询问拆成几部分，也就是 $dis(u, v) = dep(u) + dep(v) - 2 * dep(Lca(u, v))$。 显然对于 $Lca$ 我们直接进行树链剖分即可。 我们对于每一个 $v$ 维护 $\le l$ 的 $dep(Lca)$ 的贡献，为了节省空间我们直接使用可持久化线段树，进行插入的时候使用标记永久化。 具体来说就是将 $[l, r]$ 这个 $dfs$ 序的区间进行 $+ 1$ 意味着，整个区间加上了 $sumdep_r - sumdep_{l - 1}$ 的贡献，之后为了保证线段树的复杂度是 $\log n$ 我们直接在这里记录标记了几次。然后在进行查询的时候直接下传还有多少次标记没有传完即可。直接像普通线段树下传标记会出现下传了不是属于当前线段树节点的情况。 对于修改的话，发现前缀和只有一个位置变了，也就是只需要修改一个位置。 然后因为本题是卡空间的，我们考虑一次加入点是 $\log n$ 的，一次插入也是 $\log n$ 的，本质就是一次插入需要 $ ...

CF827F Dirty Arkady’s Kitchen 说实话这个拆点和拆边都是可以过的。 发现边是可以重复经过的，那么对于两条边只要考虑奇偶性就好了。 我们考虑对于一条边拆成两部分，一个是起点为奇的，另外一个是偶的。 什么时候一条路径是合法的，也就是说对于一条边 $E$，起点到他的路径上肯定存在一条边的上界是 $\ge E_l$ 的。 注意这里边是会消失的。 然后考虑加边的顺序，比较显然直接是从小到大进行加边。这样对于我们路径的上界肯定是从拓扑序比起小的边得到的，也就是意味着这条边出现的时候肯定是可以走的。 设 $f(i, 0/1)$ 表示到当前点的奇偶性为 $0/1$ 的最晚时间。 如果说当前时刻这条边是不能走的，我们可以考虑将其加入到当前 $u$ 的边集中，之后更新。 因为现在不能走并不意味着不能被其他的边更新。 然后之后更新就是像最短路一样，如果说一条边的终止点在之前被更新过了，那么我们就直接跳过更新。 12345678910111213141516171819202122232425262728293031323334353637383940 ...