NGC5457's Site

分类： OI

  • 随记 – 二月七日 – 初探二分图建模

    看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签，试图二分图时只晓得将题目中同一类的元素转化为点，将相对关系转化为边。但实际上，二分图也可以表示其他的二元逻辑关系，例如包含、排除。

    例如[NOIP2010 提高组] 关押罪犯，一个经典做法是将罪犯转化为点集，将冲突关系符合一定条件的相互连边，然后二分答案作二分图匹配。（扩展域并查集实质上也是在贪心的基础上，运用“二分图匹配”的思想检查方案合法性……对吧？）

    再例如AtCoder ABC 228 G – Digits on Grid，计数DP的转移也是在行、列元素分别作为左部、右部，以方格中的元素作为边权的二分图上进行的。

    这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时，我认为应当用可重集作为二分图的左部和右部。但是这样一来，如何进行匹配呢？正解则是将数组$i$包含元素$a_i$的逻辑关系转化为边——左部为各个数组，右部为相同的元素。可以发现，能够有解的充分必要条件是“每个元素均统共出现了偶数次”，同时“每个数组含有偶数个元素”，那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么？它有一个更专业的术语，曰欧拉回路。事实上，一张无向图存在欧拉回路，当且仅当不存在度数为奇的节点。所以，我们直接求解一条欧拉回路，将从左部到右部遍历的边记作$L$，从右部到左部遍历的边记作$R$，就是一个正确的解。

  • CF1624D – Finding Zero – 题解与思路重现

    给大家表演一个一场下青

    CodeForces Round 770 Div.2 Problem D – Finding Zero

    一道非常有意思的交互和构造题。

    考虑能否固定两个数$x, y$，通过它们的相对大小关系，确定其他数中是否存在$0$或最大值$a_{\text{max}}$。

    经过一番推导，我们发现，设$x \geq y$的情况下，对于三元组$(a_i=x, a_j=y, a_k=z)$，有$$g(i, j, k)\newline
    =\max(a_i, a_j, a_k) – \min(a_i, a_j, a_k)=
    \begin{cases}z-y, & z > x \\
    x-y, & z \in [y, x]\\
    x-z, & z < y\end{cases}$$。所以，设$x=6, y=4$以上式结果为因变量，$z$为自变量，应有以下图像：

    （更多…）

  • 随记 – 二月四日 – 将树形结构序列化的几种办法

    DFS序列（$\mathrm{dfn}$）

    在没有或存在一定限制条件的情况下，以DFS遍历经过的节点顺序构成的序列。记$\mathrm{dfn}(x)$为第一次访问该节点的时间戳，$\mathrm{seq}(t)$为访问序为$t$的节点。

    容易发现，节点$x$的子树节点的$\mathrm{dfn}$一定是一段连续的区间。故我们可以使用数据结构方便地维护子树的信息。

    （更多…）

  • AtCoder ARC134C – The Majority – 简略题解与思路重现

    AtCoder ARC 134 C – The Majority

    如此ruzhi的一道题目竟花去两小时有余，比赛结束也没写出来，实在惭愧。

    拿到题目，很快想到一种DP：令$f(i, j, k)$表示“考虑到第$i$个盒子，第$1$种小球用去$j$个，第$2, 3, \dots, n$种小球用去$k$个”的方案数。容易转移。

    然后发现$a_i$是$10^9$级别。同时题目告诉我们，相同类别小球无法区分，所以要是上述做法正确，为什么要分别给出$a_2, a_3, \dots$呢？如何在转移时确保每一种小球的使用次数正确？立刻想到正解与$\mathrm{O}(a_i)$基本无关。

    （更多…）

  • AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP

    昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。

    由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。

    今天查看题解，发现有几个重要的，从未考虑过的trick：

    1. 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
    2. 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。

    （更多…）

  • 转载 – How to come up with the solutions: techniques – MikeMirzayanov’s blog

  • 随记 – 一月十八日 – 关于分块

    终于体会到了“看了题解都可能写不出来”的绝望了——CF925E May Holidays。

    自以为已经对“分块”的思想有了一定掌握，到头来发现自己还只会最基本的、应用最广泛的值域分块。只是题见得不够多罢了。

    考虑一种实际操作中不会使用的求区间第$k$大的算法。设块长为$S$，我们将序列分成$\mathrm{O}(\dfrac{n}{S})$块，每一块内直接对元素排序。对于一个询问$[l, r]$，我们二分答案。猜测答案为$d$，在中间的每一整块内二分出$\leq d$的元素数量，两侧暴力查找。这样的复杂度是$\mathrm{O}(\dfrac{len}{S} \log^2 n+S \log n)$的，其中$len$代表区间长。

    这告诉我们，分块的目的不仅可以让较大的值域范围内的统计变得更高效，还可以使得元素（部分）有序，适用范围更加广泛。就连分块这种暴力数据结构使用时都需灵活变通，其他算法又何尝不是如此。

    （更多…）

  • 随记 – 一月十三日

    看来还是每天写些随记才好。做题时发现、学会的一些令人啧啧称奇的绝妙性质，以后可能有用。

    关于异或

    异或和具有区间可减性。可以通过前缀异或和快速求出某个区间所有元素的异或。

    区间内，多种元素数量奇偶性的统计问题，可以转化为状压后的异或和。

    （更多…）

  • 转载 – 欧几里得算法、裴蜀定理、扩展欧几里得算法、中国剩余定理和扩展中国剩余定理 – AH_ljq的洛谷博客

  • AcWing 159 奶牛矩阵 – 简略题解

    AcWing 159 – 奶牛矩阵

    这道题的题意让我们想起了最小循环节。我们先不考虑这个矩阵的具体位置。由题可知，只要扩展的矩阵覆盖原矩阵即可。考虑以下图形：

    黑线为原矩阵。红线是一种最小子矩阵的划分。请看绿色和蓝色矩形，它们分别是没有占够一整个矩形宽度的左右边界，以及对应到每个完整的子矩形中的位置。如果我们以灰线为界，将最小子矩形平移至与灰线之间对齐，则最小子矩形的扩展就从原矩形的最左端开始。上下两端的处理同理。这与之前的划分显然是等价的。因此，我们可以只考虑从左端、顶端开始的子矩阵的划分。

    （更多…）