如何使用 Gitbash 首先你需要一个下载地址。 然后我们来和自己的 $\tt github$ 账号进行连接，使用 $\tt SSH$。 我们一下的操作都是在 $\tt gitbash$ 里面进行，也就是鼠标右键出现的那里进去的。 首先检查自己电脑的 $\tt SSHkey$ 是否存在 $ cd ~/.ssh 然后使用 $ ls -al 检查是否存在。 如果连文件夹都不存在的话那肯定是没有的。 如果你需要创建一下 $\tt SSHkey$ 的话，我们使用 $ ssh-keygen -t rsa -C your-email 然后一直回车就可以了。 $\tt your-email$ 就是直接输入你的邮箱。 然后我们找到你保存的文件地址，将 $\tt public$ 的部分复制下来。 我们点到 $\tt github$ 的主页，鼠标放在头像下面，点击 $\tt setting$ 点击 $\tt SSH$ 设置，加入新的钥匙，名字就随便取了，把之前的部分复制在下面的框里。 之后我们检查一下 ssh -T git@github.com 如果成功了就可以了。 然后我们使用 git ...

Link with Balls 给出 $2n$ 个箱子，可以从第 $2x-1$ 箱子取 $kx$ 个球，可以从第 $2x$ 箱子取至多 $x$ 个球，那么最终取 $m$ 个球有几种方法。 每 $n$ 个箱子是本质相同的，我们可以考虑使用生成函数进行计算。 设 $f_i(x) = \sum_{j = 0} ^ i x^j = \frac{1 - z^{i + 1}}{1 - z}$。 设 $g_i(x) = \sum_{j \ge 0} x^{i\times j} = \frac{1}{1 - x^i}$。 之后我们的答案就是 $\prod_{i = 1} ^ n f_i(x) \prod_{i = 1} ^ n g_i(x) = F(x)$。 $$F(x) = \prod_{i = 1} ^ n \frac{1 - x^{i + 1}}{1 - x} \times \prod_{i = 1} ^ n \frac{1}{1 - x^i}$$ 仔细看看就会发现了左边的分子和右边 ...

虚树浅谈 我们就直接进入主题了，毕竟还有 $1 \tt h$ 就要准备去考场了，可能是我退役前的最后一篇学术类的吧。 树上的题目中可能会给出 $\sum k_i \le 5 \times 10^5$ 之类的限制，那么我们常常会考虑到两种东西： 自然根号，也就是本质不同的 $k_i$ 只有 $\sqrt V$ 种。 虚树。 对于给定的一个点集，我们往往不希望这个是一个森林，所以我们钦定加上根节点特判即可。 我们考虑将点集按照 $\tt dfs$ 序进行排序，之后从前向后往栈中加点。我们设 $lc$ 表示当前点和最后加入栈的点的 $\tt Lca$。 如果 $lc = stack(ed)$ 那么意味着还是同样一个子树的链，我们直接加入即可。 不然意味着更换了子树，我们考虑将当前子树的树全部建出，那么因为更换了子树，也就是意味着 $dfn_{lc} \le stack(ed)$ 的，我们考虑退栈直到合法为止。 1while(ed > 1 && dfn[lc] <= dfn[st[ed - 1]]) G.add(st[ed - 1], ...

CF1396C Monster Invaders CF1396C Monster Invaders 建议不要看中文，直接看英文题面，里面有很重要的一句话：一开始都没有装弹，一次只能装一把枪。 这个东西决定了我们贪心的方案，不然的话可能像我以前或者一开始一样当成同时开始冷却 /qd 这边再吐槽一下，之前已知不会订正，现在想想还是挺简单的。 因为 $r_1 \le r_2 \le r_3$。 首先考虑总共只有 $3$ 种打的方案： $a_i \times r_1 + r_3$。 $a_i \times r_1 + r_1 + r_1$。 $r_2 + r_1$。 而且考虑走的方法，我们会考虑一开始直接走到头，之后一次回来，发现距离是 $2d$。 我们考虑相邻两个一起搞定，那么乍一看是 $3d$ 但是每两个相邻之间本质上只有 $d$，均摊一下还是 $2d$。 所以我们只需要考虑相邻的部分，直接考虑当前是否打死，设 $f(i, 0/1)$ 表示当前考虑到位置 $i$，$\tt boss$ 还有血量 $0/1$ 的最小代价。 直接分类讨论暴力转移即可。 ...

#514. 【UR #19】通用测评号 #514. 【UR #19】通用测评号 一个小 $\tt trick$： 对于这样的 $a$ 限制，我们可以无视它，但是代价是无穷项。 感觉感性证明更好理解：对于一个位置多的操作，我们直接不做即可，直接去考虑下一个操作，显然答案是不变的。 考虑填充的结束条件，就是恰好有一个燃料舱是 $b$ 单位的。 而且因为期望是线性的，我们直接对于每个燃料舱进行计算概率即可。最终的答案就是 $(n - 1) \times P$。 我们将 $z = 1$ 带入即可。 那么我们考虑一下这个 $P$ 是怎么计算的，我们不妨考虑拿出最后一个是 $b$ 的燃料舱，那么就是 $n$。为了方便我们设 $f(x)$ 表示进行了 $x$ 次操作的概率函数，也就是 $\dfrac{z^x}{x!n^x}$。 显然最后一个仓就是 $f(B - 1) \times \frac{1}{n} \times n = f(B - 1)$。 之后对于其他仓我们只要保证至少一个是符合条件即可，那么就是 $(e^x - f(A - 1)) \times (e ...

CF1349F1 Slime and Sequences (Easy Version) CF1349F1 Slime and Sequences (Easy Version) 题目中最明显的限制就是： 如果 $i$ 出现，那么必定有 $1 \sim i - 1$ 从小到大出现。 也就是说如果将 $1 \sim i - 1$ 和 $i$ 的位置写出来是一个严格递增的形式。 我们不妨考虑对于每个位置 $i$ 计算数字 $x$ 的答案。 也就是说对于前面的位置我们必须有 $i - 1$ 个上升的数字，来保证其可以出现，当然对于后面都没有影响。 具体来说如果后面出现了，我们不计算贡献。 如果没有出现，显然没算。 我们发现对于一个排列和一个合法的序列是一一对应的，可以考虑对于一个合法的排列，倒着写出 $1$，倒着写出 $2$。 之后有几个上升的肯定就是有多少个合法的当前位置。 后面的位置随便填即可。 答案就是$$ans_x = \sum_{i = 1} ^ n n^{\underline{i}} \times \left<\begin{matrix}i \ ...

CF1404C Fixed Point Removal直接考虑每个数是否可能满足条件，显然对于 $a_i \le i$ 的情况才是可能的。而且发现对于 $\forall j > i$ 是不影响当前状态的。 我们考虑对于每个 $i$ 维护一下其距离条件还有多少位置，也就是 $i - a_i$。我们每一次将前面一个数删去，也就意味着后缀全部 $-1$。这个东西可以拿线段树简单维护。 发现对于 $r$ 只不过是对合法数范围的限制，我们直接维护一下区间合法的数的和即可。 之后我们只需要对于询问离线一下，从大到小按照 $l$ 加点即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211 ...

Splay 入门 其实 $Splay$ 不能算作高速平衡树，但是事实上其代码非常好些只要记住一些细节。而且是平衡树中可以维护动态树的存在的，当然你也可以用 $FHQ-Treap$ 维护 $ETT$。 时间复杂度 我们必须了解一下每个平衡树维护平衡的方式，$Splay$ 是通过旋转，注意是双旋才可以保证复杂度。 我们将一个节点旋转到固定位置的操作称为 $splay$。 当然我们可能存在一次 $splay$ 是 $O(n)$ 的情况，根据势能分析可以得到复杂度是 $O(n \log n)$ 的。 因为是均摊而不是期望，所以我们不能对其进行可持久化操作。 splay 操作 我们需要先知道对于一条链我们会旋转成什么样子： 最终会变成： 我们直接对于当前操作进行模拟即可： 12345678void Rotate(int p) { int f = t[p].fa, ff = t[f].fa, k = pd(p); t[p].fa = ff; if(ff) t[ff].ch[pd(f)] = p; t[f].ch[k] = t[p].ch[!k], t[t ...