Odalys

同济大学《线性代数》前四章部分内容 其中，$p$ 是一个 $1\to m$ 的排列，$t$ 是其逆序对数。 Lemma 0.2.1. 行列式与其转置行列式相同 Lemma 0.2.2. 上三角矩阵行列式等于其主对角线之积 Lemma 0.2.3. 行列式交换两行（列），行列式变号 Lemma 0.2.4. 行列式可提某行（列）公因子 由上述两条得 行列式任意两行（列）成…

由 [AGC001F] Wide Swap 可知一个结论，若 $i < j,|h_i-h_j|> k$ 则无论怎么交换，$h_i,h_j$ 的相对位置不会改变。 据此，我们暴力连边，每条边表示 $h_i$ 必须得在 $h_j$，然后用一个堆拓扑一遍即可得出最小字典序 考虑使用数据结构优化这个建图方式 考虑使用建一棵权值主席树，上面全是虚点，每次加入新的 $h_i$ 我们在叶子上…

打牛牛题不会吉吉！

real: 40 + 20 + 0 expect: 40 + 20 + 0 need: 100 + 20 + 0 links sol 从大到小排序 设 $dp_{i,j,k}$ 表示选到第 $i$ 个元素，前面还有 $j$ 个元素未匹配，当前总和为 $k$ 的方案数 $a_i$ 第 $i$ 位权值 转移 分别表示这一位匹配与否，还有一个只由当前一个元素组成的集合。 考虑系数 我是大…

real: 68 + 0 + 0 expect: 100 + 40 + 0 T1 被卡常了，T2 被输入埋了 links sol ​ 枚举个$gcd$ ，使用 $Dirichlet$ 前缀和优化。 ​ 一种题解做法是枚举第 $i$ 个位置有贡献然后使用积分。 ​ 实际上可以下一步转换不必使用积分，而是考虑每个位置，他们的可取值域要每次相对来说会乘一个阶乘，而给他们任意取…

信息存在叶子上，即 Leafty 性质，每个点维护一个权值 $v$ ，一个信息大小 $siz$ ，叶子 $siz = 1,val=v$ ，其他点 $siz$ 直接合并，val=val_ 这样，点数是 $2n$ 的，中序遍历是单调递增的，利用 $val$ 可实现查值查 rk。 利用单旋和双旋来维护重量平衡 重量平衡大概是搞一个常数 $\alpha$ ，若左右子树有一个比另一个…

首先可以发现满足条件的 $s_{i-1}$ 一定会是 $s_{i}$ 的后缀，考虑反证，若存在不是后缀，那一定是中间一段，把后面切掉不会使得答案更劣。 然后就考虑在 SAM 的 $\texttt{parents-tree}$ 上做一些事情，我们已经知道满足条件的 $s_{i-1}$ 一定是 $s_{i}$ 的一个祖先，但这并没有考虑到满足出现两次这样一个限制，我们来观察满足限制…

一些国外OI的Lists

​ 在我初读《百年孤独》时，曾被一桩 “悬案” 所困扰，那就是小美人蕾梅黛丝在婚期前一周意外身亡。当时的我将死因归结于下一页中阿玛兰妲向上帝祈求导致鸦片酊误落于蕾梅黛丝的咖啡中这样一个魔幻的事情，我既因为一个美丽纯洁的女孩子这样莫名其妙的死去而感到不解，又抱着对 “文学家无闲笔” 这样一种感觉而始终保持着一种警觉。在接下来的阅读中，我找到了一个可以说服我的答…

人类智慧 考虑 $a_0=a_{n+1}=\texttt{INF}$ 。 那可以二分中间一个端点，若他是下降的由于最后一项是上升故后面一定有个合法答案，反之亦然。 贪心。 考虑两个栈，若与栈顶有一个不同则直接放更优，否则。。。。讨论一下 看到就会想到二进制分拆 考虑 $[1,2^n-1]$ 如何构造，大概是每个点表示一个二进制位，向外连的边都是 $2$ 的整次幂… 这样…