NGC5457's Site

分类： OI

  • AtCoder ARC138D – Differ by K bits 简略题解

    考虑这个排列是怎样生成的。转述一下题意，可以发现，$\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K$，也即全集$\text{msk}=2^N-1$的一个大小为$K$的子集。

    由于这是一个环排列，我们不妨令$P_0=0$。这样一来，$P_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K$。结合上文可知，这是一个相邻元素二进制位恰相差$K$位的格雷码问题。有$K=1$时，满足条件的$S_j$恰有$N$个，也就是$N$位格雷码。

    考虑推广。我们发现，如果按照类格雷码的方式生成排列，则所有的$S_j$应构成异或空间，其大小应当恰为$2^N$，并且由线性空间知识可以得到，该线性空间的秩（基的大小）应当恰为$N$。这恰好符合$N$位格雷码的构造。因此，只要满足上述条件，就一定能够生成符合题意的排列。

    可以证明，除了$2\mid K \lor (K=N \land N>1)$以外，总是有满足条件的线性空间生成的。

    下述解法的时间复杂度$\operatorname{O}\left(\dbinom{N}{K}+2^N\right)$。 （更多…）

  • 随记 – 四月九日 – 利用二进制数高效枚举集合

    以下所有操作均可以通过递归DFS每一位并作相应判断实现。但以下写法实现简洁、常数较小，不失为一种优美的技巧。

    下文采用$S_i$表示第$i$个集合，$\text{msk}$表示其二进制表示。

    简单集合运算

    • 并：$S_1 \cup S_2 \leftarrow \text{msk}_1 \mid \text{msk}_2$
    • 交：$S_1 \cap S_2 \leftarrow \text{msk}_1\space\&\space\text{msk}_2$
    • 差：$S_1 \setminus S_2 \leftarrow \text{msk}_1\space\&\space(\sim\text{msk}_2)$
    • （相对于该二进制数类型最大值的）补集：$\sim\text{msk}$
    • 对称差集：$S_1 \Delta S_2 \leftarrow {\text{msk}_1}^{\space\land}\space \text{msk}_2$

    （更多…）

  • 随记 – 三月二十八日 – 介值定理

    介值定理

    若有连续函数$f: [a, b] \mapsto \mathbb{R}$，且不失一般性地，令$a< b, f(a)< f(b)$，则对于任意实数$x\in [f(a), f(b)]$，存在$c \in (a, b), f(c)=x$。

    容易由实数完备性证明。直观理解，即可以画出一段连续曲线，其两端点分别为$(a, f(a)), (b, f(b))$，而笔不离开纸面。

    离散函数值上的介值定理

    若存在函数$f(x) \in \mathbb{Z}, x \in \mathbb{Z}$，且满足$|f(x)-f(x+1)|\leq 1$，则对于$a<b, f(a)<f(b)$，若有整数$x \in [f(a), f(b)]$，存在一个$c \in (a, b), f(c)=x$。

    证明显然。

    在OI中的实际意义？

    我们常遇到这样一类函数：在某些数列上进行统计，邻项函数值之间的差为$\{-1, 0, 1\}$，如括号序前缀和（$\text{‘(‘} \rightarrow +1, \text{‘)’} \rightarrow -1$），则可以通过上述性质判断某两点之间函数值是否存在。

    例如CF1695C – Zero Path，本质上路径上数字和是一个满足上述条件的整数离散函数。

    再例如CF1658F – Juju and Binary String，可以将题意转化为一个函数$f(x) \in [0, n], x \in [0, n] \land \exists x_p, f(x_p) >0$，且满足上述性质；同时有函数$g(x)=x, x \in [1, n]$，则可以证明一定存在$x_0, g(x_0)=f(x_0)$。

  • 随记 – THUPC 2022 初赛 J – 画图 7KB的大模拟……？

    考虑合并若干重叠线段。使其有序化后考虑每两个线段的交，如果其为空则新建一条独立线段，反之合并。

    最后应当恰好有$7$条水平线段，$8$条垂直线段，否则依题意不可能拼凑出“$\textbf{THUPC}$”图形。

    DFS搜索组成每个字母的所有可能线段组合。需要合理剪枝，亦可以使用二进制状态压缩减小常数。时间复杂度理论上限为$\mathrm{O}(7^5\times 8^5)$，实际远远达不到。

    赛时1A（实际上因为无主函数返回值RE了两次）$7\text{KB}$代码：
    （更多…）

  • CF1649F – Serious Business – 题解与思路重现

    CodeForces Round #755 Div.2 F / Div.1 D Serious Business

    此题整整困了我一天半，耗费了好几张草稿纸。实在走投无路，翻看题解，却发现正解曾经近在咫尺。有必要稍作整理。

    考虑DP。

    错误转移1

    这道题与清理班次（《算法竞赛进阶指南》上的一道例题）过于相似，都是“给定一些段落$[l_p, r_p]$，选择其中一些完整覆盖$[l_0,r_0]$，求最小花费”的形式。记上述花费为$f(l_0, r_0)$。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在$x_2$位置从第$2$行转到第$3$行，利用数据结构维护所有$x_1\leq x_2$，在$x_1$转移到第二行，解锁到达$x_2$的最小代价。对于各行前缀和，我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在$\mathrm{O}(n \log n)$的时间内，计算出对于一个固定的起点$l_0$，所有$f(l_0, r_0), r_0 \in [l_0, n], \exists p, r_p=r_0$的值。 （更多…）

  • 随记 – 三月四日 – DP求解强制包含部分元素的序列计数问题

    被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。为什么题解TMD是错的？

    即$g(i,j,k)$表示“每个位置有$i$类元素可选，且序列中必须包含指定的$j$类元素的，长度为$k$的序列的个数”。形式化地讲，我们需要统计满足以下条件的序列的个数：$\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b$。

    通过容斥原理，我们可以计算出至少有$0,1,2,\dots,j$个$T$中的元素没有被包含在序列中的序列的个数，然后乘上容斥系数累加既是答案。也即：
    $$g(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}$$。通俗地讲，我们在 $j$ 个元素中选择 $x$ 个，并强制使得它们不出现在序列中，其余元素任选。除去组合数的预处理时间，复杂度为$\mathrm{O}(j)$。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal，可以使用上述计算而非DP求解（虽然DP更加简洁直观）。

    （更多…）

  • MOCK CSP-S 20220302 D – Trees 题解转录

    考虑一棵无根树的生成方式：需要决定一个好的顺序从而达到不重不漏地生成所有 $n$ 个点的无根树。

    类似有向无环图的拓扑排序，可以定义一种无根树的“拓扑排序”：每一轮将当前的叶子删去。这样可以很容易算出直径。设删除的轮数为 $r$，则当最终剩余一个孤点时，直径 $d=2r$，否则直径 $d=2r-1$。为了生成无根树，我们考虑进行逆操作，在当前的树上加叶子。在此之前，为了不重不漏地对无根树进行表示，我们考虑如下的唯一表示方法：设 $\text{dis}(x)$ 为节点 $x$ 在添加叶子过程中第几轮被添加上树的。对于$S=\{x\mid \text{dis}(x)=\text{const}\}$（也即同一层的节点），显然两棵有标号无根树同构但标号不同，当且仅当每个上述节点$x$的叶子节点的标号集合不同。我们总是将 $x$ 标号小的先行添加为其儿子。这样就不会出现因“两棵树本身同构，子节点编号集合相同导致重复计数的问题”。同时，为了方便、准确地计算，我们严格规定，新加入的 $k$ 个叶子节点在新树上就是全部的叶子节点。也即在旧树上的所有叶子节点在新树上至少有一个儿子。 （更多…）

  • 随记 – 二月二十四日 – 一个集合的子集的子集数之和

    有集合$S$，$|S|=n$，则有$$\sum\limits_{T \subseteq S}2^{|T|}=\sum\limits_{k=0}^{n}2^k\dbinom{n}{k}=3^n$$。因此，若我们枚举集合，枚举集合的子集的子集做状压DP时，可以得到正确的复杂度$\mathrm{O}(3^n)$而非错误的$\mathrm{O}(2^n\times 2^n)=\mathrm{O}(4^n)$。参见AtCoder ABC 187 F – Close Group。

    可以这样证明：考虑某个子集的子集$P \subseteq T \subseteq S$，则$S$中的每个元素有三种状态：$a\in P$，$a \notin P, a \in T$，$a \notin T, a \in S$。显然这样可以唯一表示$S$，$T$以及$P$，对应了所有子集的拆分方案。故原式成立。

  • FHQ Treap 学习笔记

    UPD 02.15：更新了区间操作部分。

    约莫半月前练习专题时，发现几道解法多样的题目，其中需要运用一些中高级数据结构。苦于之前没有学习过平衡树，便挑选了一种易于上手、实现简单的平衡树学习，也即FHQ Treap。由11年国家队队员范浩强发明。

    为书写方便，文章中可能将直接使用$p$代指某节点的随机权值，$\text{val}$代指节点关键码（即记录的数值），$h$代指树高，$\text{siz}$代指子树大小，$\text{cnt}$代指节点副本数（相同关键码的节点），$\text{rt}$存储根节点编号。

    （更多…）

  • 斐波那契数列 – 一些性质与推论

    广义斐波那契数列

    定义：任何形如$f_i=f_{i-1}+f_{i-2}, f_1=x,f_2=y$的数列，称为广义斐波那契数列。

    $F_1=F_2=1$的斐波那契数列的通项公式

    $$F_n=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$$

    证明方法多样，可惜我都不会。知乎 – 斐波那契通项公式是怎样推导出来的？

    下文中以$F_n$代指斐波那契数列的第$n$项，$f_n$代表广义斐波那契数列的第$n$项。

    （更多…）