1797

于 2023.5.10 更新 ： 更正了两处笔误。 考虑如下定义： $A$ 表示满足第一种路径的 $(u,v)$ 集合。 $B$ 表示满足第二种路径的 $(u,v)$ 集合。 $C$ 表示满足前两种路径的 $(u,v)$ 集合。 然后答案显然就是 $|A| + |B| - 2|C|$。先求出这一类的 ......

问题描述 1797. 设计一个验证系统 (Medium) 你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 currentTime 时刻之后 timeToLive 秒过期。如果验证码被更新了，那么它会在 currentTime （可能与之前的 currentT ......

Preface 有趣的一道 ds，赛后不看题解做出来了。 Solution 首先有一个性质：$\varphi(x)$ 经过 $\mathcal{O}(\log x)$ 次迭代后变为 $1$。 证明： 若 $x$ 为奇数，$\varphi(x)=x\sum_{i=1}^{k}\frac{p_i-1}{ ......

题意 这是一道交互题。 定义一个位置 $(x, y)$，移动一步后的位置为 $(x\pm1,y\pm1)$。 你需要找到一个位置 $(x, y)$。 你至多进行 $3$ 次询问，每次询问格式为 ? a b。 交互库会返回 $(x, y)\to (a, b)$ 的最小移动步数。 题解 还是比较有趣的一 ......

个人思路： 线性筛求出来 $\phi(x)$，然后 $x$ 成为 $\phi(x)$ 的儿子，建树。 然后接下来就和 $\phi$ 没关系了，令第 $i$ 个数初始直接对应点在 $a_i$ 上。 1 操作相当于区间跳到父亲 2 操作相当于求区间内所有点到 LCA 的距离之和。 1 暴力删就行了，维护 ......

题目链接：1797. 设计一个验证系统 方法：哈希 解题思路 注意：在判断 $tokenId$ 是否出现过时，使用 $Time.count(tokenId)$，而不是使用 $Time[tokenId]$，因为只要使用之后，$tokenId$ 就会被添加进 $map$ 中，影响后续计数的结果。 代码 ......