2500 + 构造题 CF1344B Monopole Magnets CF1344B Monopole Magnets 题解 CF1385E Directing Edges CF1385E Directing Edges 题解 CF1416B Make Them Equal CF1416B Make Them Equal GCJ2015 还原集合 GCJ2015 还原集合 题解 CF1391D 505 CF1391D 505 题解 CF1380D Berserk And Fireball CF1380D Berserk And Fireball 题解 CF1375E Inversion SwapSort CF1375E Inversion SwapSort 题解 CF449C Jzzhu and Apples CF449C Jzzhu and Apples 题解 CF1559D2 Mocha and Diana (Hard Version) CF1559D2 Mocha and Diana (Hard Version) 题解

emmm 这里大概会记录一下 $vp$ 的场次和一些想法吧。 Codeforces Round #691 (Div. 2) 反正我是心态崩了，就是 $A, B$ 其中 $A$ 直接猜结论，然后 $B$ 是一个找规律的题目，因为画出来之后可以发现矩阵是规则的。对于 $C$ 题直接秒杀了不多说了。 $D$ 看起来是可撤销贪心实际上是 $\tt Dp$。 E 题解 F 题解 总结一下就是说还是要从多方面进行思考，对于看起来比较复杂的题目是否有简化的方案。同时不要放过任何可能的突破点。

退役记 现在是星期天的下午，标题上面的日期已经标记出来了，是我退役之后的第一个周末。 确实是一个很小的角色吧，谁实话就是一个炮灰罢了。 但是毕竟还是有学弟和学妹们的，希望至少为 $XHZX$ 留下一点东西吧。 我是从初一开始接触信息的，已经算比较晚了。仅仅在每个星期五（还不一定有的）社团时间 $2\ hours$。来联系编程。 之后在每天的中午放弃午休的时间进行编程的学习。 运气很好在初二的那一年进入了初赛，以 $90$ 分的成绩。之后显然只有一个 $2=$，毕竟您想想这是浙江呀，仅仅写出来了两题是完全不可能拿到一等的，而刚刚接触的我甚至只知道模拟和贪心，建图也是临时背板子出来的，用的是 $\tt vector$ 的建图（这是我之后和 $\tt vector$ 的情缘的基础）。 当时 $YWZX$ 是只要有普及一等就可以直接面试的，普及二等只是给了一个提前批的名额， 但是我们成绩都还不错都不需要，也算间接为学校提供了一个名额吧。 之后通过奇妙的原因（想知道的可以私信我）考试到了 $HL$，也就是初三的那一年开始正是学习编程。 之前的奖项： 普及二等。 之后开始停课，真正认识了 ...

虚树浅谈 我们就直接进入主题了，毕竟还有 $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], st[e ...

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$ 的最小代价。 直接分类讨论暴力转移即可。 12345678910111 ...

#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^x - f(B - ...

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 \ j - 1 \en ...

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