0103abc 的网站

Official Solution. 设 $f_{i,0/1}$ 表示当前处理完了以 $i$ 为根的子树，且 $i$ 号结点通关，当前不在 / 在 $i$ 号点放存档，最小期望通关代价是多少。 显然对于通关概率为 $\frac1{pi}$ 的 $i$ 结点而言，期望需要花费 $pi$...

有向图博弈问题考虑从外侧不断删除必败状态。设 $W$ 为当前没有确定为必败的状态组成的集合。则考虑对每个点 $u$ 如果其属于 $A$ 集合那么只要存在一条出边通往 $W$ 集合即可；如果其属于 $B$ 集合必须保证其所有出边都能通往 $W$ 集合。设满足这个条件的充电站组成的集合为 $P$（即...

先观察性质，三个串 $A,B,C$（$A\ge B,C$）可以组成三角形当且仅当 $BC>A$ 或 $CB>A$ 成立。因此考虑对串的大小关系做分类讨论。 $A=B\ge C$ 容易证明此时 $A,B,C$ 三个串一定可以构成合法的三角形。记 $cnts$ 表示给定的字符串中有多少个串恰好为...

先考虑 $L\le 49$ 怎么做。此时把平面划分为 $2n-1$ 条反对角线，则每条反对角线必然被恰好翻转一个位置的值。对每条反对角线设一个校验位使得该对角线上所有奇数行位置上元素的异或和都为 $0$。反转完路径后考虑重新计算这个异或和，若收到的奇数行异或和为 $1$...

这里记 $d(A,B)$ 为 $A,B$ 两个点在三维空间中的曼哈顿距离。 先特判掉一些 corner case： $n=1$ 是容易解决的。 如果有一个传送器 $Ai$ 满足 $d(P,Ai)=d(Q,A_i)$，则答案为 $1$。 否则，若存在两个传送器满足其中一个距离 $P$...

不需要线代和 GF 的 $2\log$ 做法，感觉应该不太能继续优化时间复杂度了。 先考虑一个线性的暴力做法。设 $f(n)$ 为答案，则初始条件为 $f(1)=f(2)=1$，转移方程为 $f(n)=\sum\limits_{i=\lceil\frac...

AI 使用声明：前半部分和最后的线性算答案部分做法是 ChatGPT 教我的。 被官方题解的一大堆积分吓哭了，所以这里给出一个完全不需要任何高等数学知识的题解。 先不考虑额外加入的一条弦。固定一个 $1\sim 2n$ 的边权排列，设她的 MST 中 $n$ 条边的权值为...

怎么全世界都觉得这个是黑题，来写一个简单做法的题解。 为了方便，后面记 $C_i=\frac{\binom{2i}i}{i+1}$ 为 Catalan 数列。 直接做比较困难，因此考虑容斥。钦定有 $k$ 对公共配对，剩下部分被分成了 $k+1$ 个连续段。若某一段有 $x$...

先找操作的不变量，套路的想到操作前后逆序对奇偶性的变化，在 $i$ 位置进行一次操作会产生 $n-2$ 次交换，而逆序对奇偶性和交换次数奇偶性是相同的，因此若 $n$ 初始为偶数则序列的逆序对数永远不会变化，此时若初始逆序对数量为奇数则必然无解。...

先考虑 $n,m\ge 2$ 的情况。此时记第 $i$ 行内所有元素的和为 $Ri$，第 $j$ 列内所有元素的和为 $Cj$。则一个位置 $(i,j)$ 是合法的当且仅当 $a{i,j}\ge (Ri-a{i,j})+(Cj-a{i,j})$ 即 $Ri+Cj-3a{i,j}\le...