Posts

原题链接 很神妙的一个题。 首先考虑答案下界，不难注意到对于每页面 $k$ 个链接，共 $n$ 个页面的情形，最远两点间需要不小于 $\lceil \log_k n\rceil$ 次点击。 为什么？因为信息熵。对于 $c$ 次点击和 $k$ 个链接，我们有 $k^c$ 种不同的点击序列，即使它们的终点两两不同，最多也只能覆盖 $k^c$ 个点，而我们一共需要覆盖 $n$ 个点。 当然可能点击少于 $c$ 次，所以长度不超过 $c$ 的序列有 $\frac{k^{c+1}-1}{k-1}$ 种。 $$ \begin{aligned} \frac{k^{c+1}-1}{k-1} &\geq n \\ \log_k(k^{c+1}-1)-\log_k (k-1) &\geq \log_k n \end{aligned} $$当 $n, k$ 趋于无穷大时，左边大约可以视为 $c$。那么 $c$ 自然要取最小的不小于 $\log_k n$ 的整数，也即 $\lceil \log_k n\rceil$。 当然，$k$ 较小时可能有常数级别误差，但问题不大。 然后考虑如何构造。 如果每个点允许三个指针，套用断线树/衡平树的结构是简单的。问题在于本题只有两个指针。 胡乱考虑了一些跳表，但是也无法砍到两个指针。思考了一些环状结构上建立加速索引，但是用处不大。 发现线段树可以利用叶子节点的剩余指针指回根节点，但最远距离是下界的 2 倍左右。 下面是非独立思考部分。 各种树形结构都有对父指针的需求。但叶子指针指回根节点以及环状结构启发了我们。 注意到叶子指针指回根节点只利用了一个指针，不够充分。 我们考虑一棵堆式存储的线段树，但叶子节点的两个指针对 $n$ 取模。 形式化的：节点 $p$ 的两个指针指向节点 $(2p) \bmod n$ 与 $(2p+1) \bmod n$，如果其中一个数为 0，则指针指向 $n$。 ...

问题 给定原串 $s$ 与模式串 $t$。其中模式串可能含有一些 ? 字符（而原串没有），问号可以与任何字符匹配。问模式串与 $s$ 中哪些位置匹配？ 形式化的： 我们称两个字符串相等，当且仅当： 它们长度相等 对于任意一个位置 $i$（$0 \leq i < \mathrm{len}$，$\mathrm{len}$ 是两个字符串的长度），两个字符串在这个位置上的对应字符相等，或至少一个字符串在这个位置上的对应字符是问号。 现在的问题是，求出所有的 $0 \leq i \leq \operatorname{len}(s) - \operatorname{len}(t)$ 满足 $s$ 从 $i$ 开始（包含 $i$），长度为 $\operatorname{len}(t)$ 的子串与 $t$ 相等。 下设 $n := \operatorname{len}(s), \; m := \operatorname{len}(t)$。 bitset 做法 bitset 能够简单高效的解决这个问题，复杂度为 $O(nm/w)$。 具体的：对于每种字符 $c$，我们维护一个长度为 $n$ 的 bitset。bitset 的下标为 $i$ 的位置为 true 当且仅当 $s_i = c$。 注意到，假如 $i$ 是一个匹配的起始点，这意味着 $s_{i+j} = t_j$ 对所有 $0 \leq j < m$ 的 $j$ 成立。反过来： ...

D1 没有想出任何题目的任何非平凡的做法。三个最低档部分分。 D2 怒了，all in T1，然而无法成功 recall 区间 MEX 等于补区间 min 的性质，全在套极小 MEX 区间，只会 2n 做法。 D2T2 不会。T3 看不懂题面。结束了。 我是不是已经不适合学 OI 了。热爱淡化之后，可能也不该留在这里了。 我常常追忆过去。

做到了 ABC448E，感觉很精妙。 题目中有个部分是模意义下等比数列求和。那么来讲讲它的几种做法。 公式 直接套公式。 $$ \sum_{i=0}^n a^i = \frac{a^{n+1}-1}{a-1} $$然后用逆元。不讲。 如果等比数列不是从 1 开始的，提取首项为公因数即可。下面所有讨论都默认 1 为首项。 更好的方法 公式法需要逆元，在逆元不存在时就寄了。而恰好，448E 的模数不是质数。 我们有几种方法来处理这个情况 下文定义 $$ f(l, a) = \sum_{i = 0}^{l-1} a^i $$分治求和 洛谷已经有篇文章讲过这种手法了。我在场上推出来也受到了它的启发。 大概来说，我们将序列平均分为两部分。 $$ f(l, a) = \begin{cases} (1+a^{l/2})x, \; l \text{ is even}\\ x+a^{(l-1)/2}(ax+1), \; l \text{ is odd} \end{cases} $$其中 $x := f(\lfloor \frac{l}{2} \rfloor, a)$。 这样，做分治再套快速幂就可以以 2log 复杂度解决。不过这样不够优秀。 两种优化的分治 维护幂信息 注意到每层递归重算快速幂非常不优。我们在计算 $f(l, a)$ 时顺便维护 $a^l$，在计算完 $x$ 之后将 $a^{\lfloor \frac{l}{2} \rfloor}$ 平方就得到 $a^l$。 ...

引入 给定字符串 $S$ 与模式串 $P$。问 $P$ 的最长的是 $S$ 的子串的前缀的长度。 我会暴力！ $O(nm)$，非常显然。不讲。 喜欢哈希的小朋友们你们好啊！ 注意到答案具备单调性。于是我们使用二分，外加哈希来检验。 复杂度 $O(n\log m)$，其中 $n$ 是 $S$ 的长度，$m$ 是 $P$ 的长度。 已经很优秀了，但是还不够，毒瘤出题人出了 $n=m=3\times 10^7$ 的数据范围！ 等价重写 Hash 的算法相当于二分匹配前缀长度，然后枚举前缀匹配起始点。 重写为另一种等价的形式：枚举前缀匹配的起始点，然后二分产生的匹配的长度。 现在，Hash 的问题在于每次重新二分一看就非常不优。 当然我不是让大家写分散层叠（分散层叠也完全用不上）。但是我们获得了一些优化的可能。 包的 假设现在我们在一个匹配起始点 $i$，有一个长度为 $l$ 的匹配（意味着匹配的结束点在 $e = i + l - 1$）。 考虑一个起始点在 $i$ 之后的匹配：假设起始点为 $j$。 有两种可能： $j \leq e$ $j > e$ 我们先处理所有第一种情况，然后我们重置 $i = e + 1$ 就可以继续处理第二种情况。 注意到第一种情况具备非常神奇的特性：$[j, i + l)$ 这段下标区间内 $S$ 的子串，等于 $P$ 长度为 $i + l - j$ 的前缀，而同时，当前起始点在 $i$ 的匹配中，与这部分对齐的一段后缀也等于这段子串！ ...

原题链接 一句话总结：四个关键点是“支架”。 首先注意到右下角的 $n \times n$ 区域内的雪必须全部清除，否则连目的地都不安全，一定会有人生病。 于是我们只需要在左下和右上两块区域中设法开出一条路来。 注意到有八个点，一旦清扫完成就不需要清扫别的点。这些点是 $(n+1, 1), (n+1, n), (2n, 1), (2n, n), (1, n+1), (1, 2n), (n, n+1), (n, 2n)$。感性理解一下。 事实上，只需要在这些点中取最小代价，就得到了最优答案。 因为任何一种合法答案，都必然包含这八个点中的一个。 回到开头的省流，四个关键点是 $(1, 1), (1, n), (n, 1), (n, n)$。 直观上理解，它们不能全都走别的点的路径离开，必须有一个有属于自己的路。或者说，它们支撑了整个网格的结构，如果不移走其中一个的话就动弹不得。 具体的，我们最终肯定需要挪动这四个点到右下角。那么考虑第一次操作它们所在的任意行列。不可能在不使这四个点都不超出左上角 $n \times n$ 区域的情况下进行一次操作。 那么至少有一个点要移动到有雪的区域，我们需要清理它的落点。这落点一共可能有八个，就是上面列出的那些。 所以必然清理这八个点中的至少一个。同时，清理其中任意一个都足够了，不需要额外清理其他点。所以这八个点的代价取 $\min$ 就是答案。 代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <bits/stdc++.h> using namespace std; int t; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> t; for (int _ = 0; _ < t; ++_) { int n; cin >> n; int64_t term1 = 0; vector c(2 * n + 1, vector<int64_t>(2 * n + 1)); for (int i = 1; i <= 2 * n; ++i) { for (int j = 1; j <= 2 * n; ++j) { cin >> c[i][j]; if (i > n && j > n) { term1 += c[i][j]; } } } int64_t term2 = c[1][n + 1]; term2 = min(term2, c[1][2 * n]); term2 = min(term2, c[n][n + 1]); term2 = min(term2, c[n][2 * n]); term2 = min(term2, c[n + 1][1]); term2 = min(term2, c[n + 1][n]); term2 = min(term2, c[2 * n][1]); term2 = min(term2, c[2 * n][n]); cout << term1 + term2 << '\n'; } return 0; }

原题链接 一句话总结：两个只能动一个 经过艰苦卓绝的努力，我们发现在 $a \geq b$ 时，答案为 $a - b$。原因很简单：这时除了将 $b$ 加一，我们的任何操作都会让 $a$ 变大，而无益于让二者相等。 这就让我们可以用 $b$ 控制 $a$ 的大小，让数据范围中的值域限制有了意义。 注意到执行一次操作 3 就会让 $a$ 变得不小于 $b$。这样就会落入 $a \geq b$ 的情况中，最优策略是固定的了。 所以我们最多执行一次操作 3。 那么，我们需要决策的，就仅仅是在这次操作之前，操作 1 和操作 2 的执行情况。 一种方法是枚举让 $a$ 加了多少，让 $b$ 加了多少。但平方复杂度肯定会超时。 回收伏笔：两个只能动一个。也就是说，操作 1 和操作 2 中至少有一种没有被执行。 证明：假设操作 1 执行了 $i$ 次，操作二执行了 $j$ 次。 那么我们的总代价就是 $i + j + ((a + i) \text{ or } (b + j)) - (b + j)$。 ...

AI 作品。笑点自寻。 不过其实挺深刻的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 #include <iostream> #include <complex> #include <vector> #include <cmath> #include <iomanip> using Complex = std::complex<double>; constexpr double PI = 3.14159265358979323846; // 强制编译器内联，坚决不留任何函数调用栈 #if defined(__GNUC__) || defined(__clang__) #define FORCE_INLINE __attribute__((always_inline)) inline #elif defined(_MSC_VER) #define FORCE_INLINE __forceinline #else #define FORCE_INLINE inline #endif // ========================================================== // 1. 蝴蝶操作（Butterfly）的模板完全展开 // ========================================================== template <int N, int I> struct Butterfly { FORCE_INLINE static void apply(Complex* out) { // 编译期常量计算旋转因子 W_N^I (编译器在 -O3 下会直接将其折叠为常数) constexpr double angle = -2.0 * PI * I / N; const Complex w(std::cos(angle), std::sin(angle)); // 核心蝴蝶计算 Complex t = w * out[I + N / 2]; Complex u = out[I]; out[I] = u + t; out[I + N / 2] = u - t; // 递归实例化下一个蝴蝶操作 Butterfly<N, I + 1>::apply(out); } }; // 蝴蝶操作递归终点 template <int N> struct Butterfly<N, N / 2> { FORCE_INLINE static void apply(Complex* /*out*/) { // 递归终止，什么都不做 } }; // ========================================================== // 2. FFT 递归深度的模板完全展开 (分治阶段) // ========================================================== template <int N, int Stride = 1> struct FFT_Unrolled { FORCE_INLINE static void apply(Complex* out, const Complex* in) { // 1. 编译期静态分治：偶数部分和奇数部分 FFT_Unrolled<N / 2, Stride * 2>::apply(out, in); FFT_Unrolled<N / 2, Stride * 2>::apply(out + N / 2, in + Stride); // 2. 对当前层执行完全展开的蝴蝶操作 Butterfly<N, 0>::apply(out); } }; // FFT 分治递归终点 (N = 1) template <int Stride> struct FFT_Unrolled<1, Stride> { FORCE_INLINE static void apply(Complex* out, const Complex* in) { out[0] = in[0]; // 直接赋值，底层汇编就是一条 MOV 指令 } }; // ========================================================== // 3. 动态分派器 (运行时根据 k 调用对应的实例化代码) // ========================================================== void fft_dispatch(int k, Complex* out, const Complex* in) { switch (k) { case 0: FFT_Unrolled<1>::apply(out, in); break; case 1: FFT_Unrolled<2>::apply(out, in); break; case 2: FFT_Unrolled<4>::apply(out, in); break; case 3: FFT_Unrolled<8>::apply(out, in); break; case 4: FFT_Unrolled<16>::apply(out, in); break; case 5: FFT_Unrolled<32>::apply(out, in); break; case 6: FFT_Unrolled<64>::apply(out, in); break; // 你可以继续写到 7, 8... 但建议不要超过 10，否则编译器会崩溃 default: std::cerr << "K out of bounds for unrolled FFT!" << std::endl; } } // ========================================================== // 4. 测试代码 // ========================================================== int main() { constexpr int K = 3; constexpr int N = 1 << K; // N = 8 std::vector<Complex> in(N); std::vector<Complex> out(N); // 构造一个简单的测试信号 for (int i = 0; i < N; ++i) { in[i] = Complex(i, 0); } // 调用 K=3 的展开 FFT fft_dispatch(K, out.data(), in.data()); // 打印结果 std::cout << std::fixed << std::setprecision(2); for (int i = 0; i < N; ++i) { std::cout << "out[" << i << "] = " << out[i].real() << " + " << out[i].imag() << "i\n"; } return 0; }

考虑这么一个题目： 维护整数多重集，支持插入删除，查询全局 xor 和以及全局加一。 如果不考虑全局加一，就是唐题。不过全局加一和异或本质不兼容，比较难搞。 本文介绍的就是用以解决这一问题的技巧。 考虑维护一棵 01 Trie。与普通的用于按位贪心的 Trie 不同，这棵 Trie 按照从低位往高位的顺序。 简单来说，根节点是从低往高第 0 位，是一个超级源点。它的两个孩子是从低往高第 1 位，位权为 1，这两个孩子的孩子（即深度为 2 的那一层节点）的位权为 2，以此类推。 插入、删除和普通 01 Trie 相同。 查询全局 xor 和也比较好做。我们在每个节点上维护 count（子树中的元素计数）和 xor_sum（子树中元素的异或和）。 加法是重点。 注意到最低位为 0 的元素加一之后最低位为 1，而最低位为 1 的元素加一之后最低位为 0，并产生一个进位。 那么从根节点出发，先交换两个儿子，然后递归操作那个本次操作前当前位为 1 的子树。 结束了。 扩展：全局异或上一个数 考虑维护全局懒标记：Trie 中的一个值 v 的实际值是 v xor tag。 全局异或就变成了对 tag 的简单更新。 现在考虑如何在有 tag 的情况下做全局加一。 很简单：套用之前交换子树和递归进位的逻辑。不过，注意 Trie 中当前位为 1 的子树未必是真实产生进位的子树，因为 tag 的当前位可能为 1，这时，Trie 中的 1 子树的真实值为 0，反而是 0 子树的真实值为 1。

省流：gemini 3.1 Pro 对这个经典难题提出了一个优于暴力的做法。 区间加区间异或和怎么做？ 具体的，你需要维护一个整数数组，支持两种操作： 将一个连续区间内所有元素加上一个整数 查询一个连续区间内的元素的异或和 这个题有任何比较好的做法吗？ 这是一个在算法竞赛（如 Codeforces、Luogu）中非常经典的高级数据结构难题。 区间加（Addition）和区间异或和（XOR Sum）在本质上是“不兼容”的。因为加法会产生进位（Carry），一个加法操作可能会同时改变多个连续的高位，这导致传统的线段树（Segment Tree）无法在 $O(\log n)$ 的时间内合并和下传 Lazy Tag。 目前解决这个问题最通用且高效的经典做法是：分块（Square Root Decomposition / Block Decomposition），结合按位拆分与二分查找。 以下是详细的做法和原理解析： 核心思想：按位拆分 + 余数定理 我们要查询区间异或和，实际上等价于：对于每一位 $k$（$k \in [0, 30]$），统计区间内该位为 $1$ 的数字个数。如果个数为奇数，那么异或和的第 $k$ 位就是 $1$。 假设一个数字原来是 $x$，被加上了 $v$。那么 $x+v$ 的第 $k$ 位是否为 $1$，完全取决于它们对 $2^{k+1}$ 的余数。 具体规律如下： 设 $M = 2^{k+1}$， $H = 2^k$。 那么 $(x + v)$ 的第 $k$ 位为 $1$，当且仅当： $$ (x \bmod M + v \bmod M) \bmod M \ge H $$如果我们将 $y = x \bmod M$ 看作原数组的属性， $V = v \bmod M$ 看作懒标记（Lazy Tag），因为 $y \in [0, M-1]$ 且 $V \in [0, M-1]$，上述条件其实等价于 $y$ 落在了两个连续的区间内： ...