小明の雜貨鋪

三分法求凸函数最值 求类似开口朝上的二次函数的最小值： 1234567891011121314auto check = [&](int mid) { // 计算... return /* f(mid) */;};int lt = /* 下界 */, rt = /* 上界 */ + 1; // 切记 +1while (lt < rt) { int lm = lt + (rt - lt) / 3, rm = lt + (rt - lt) * 2 / 3; if (check(lm) < check(rm)) lt = lm + 1; else rt = rm;}// now lt = rtcout << "The function reaches its minimum value of " << check(lt) << " at " << lt <<...

char ascii 0 48 9 57 A 65 Z 90 a 97 z 122 经典字典树 主机场 给定一组字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_ns1​,s2​,⋯,sn​，任选 kkk 个 sa1,sa2,⋯ ,sak (ai≠aj)s_{a_1},s_{a_2},\cdots,s_{a_k}\ (a_{i}\ne a_{j})sa1​​,sa2​​,⋯,sak​​ (ai​=aj​)，最小化 max⁡1⩽i,j⩽k,i≠jlcp⁡(sai,saj)\max\limits_{1 \leqslant i,j \leqslant k,i\ne j}^{}\operatorname{lcp}(s_{a_i},s_{a_j})1⩽i,j⩽k,i=jmax​lcp(sai​​,saj​​)。其中 lcp⁡(p,q)\operatorname{lcp}(p,q)lcp(p,q) 是字符串 ppp 和字符串 qqq...

DFS 2024-08-11：2024 PTA 环境测试 D 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657constexpr int dx[] = { 1, 0, 0, -1 };constexpr int dy[] = { 0, -1, 1, 0 };int n, m, k;pair<int, int> a[N];bool check(int black) {    vector<vector<int>> mp(n + 2, vector<int>(m + 2, 0));    vector<vector<int>> vis(n + 2, vector<int>(m + 2, 0));    for (int i = 0; i < black; ++i) { ...

Manacher Algorithm Find the longest substring which is palindrome. 在搜索到 iii 时， cc,ll,rr 已经找到的右边界最大的回文串的中心、左端和右端。 p[i] 以 iii 为中心的最长回文串长度。如果 iii 在最长回文串之中，p[i] 至少是它对称位置的 p[mirror]。利用此性质快速计算 p[i]。 123456789101112131415161718vector<int> manacher(const string& s) { string t = "#"; for (auto c : s) t += c, t += '#'; const int n = t.size(); vector<int> r(n);  // 存储每个字符作为中心的最长回文子串的半径 for (int i = 0, j = 0; i < n; i++) { if (2...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ulll = __uint128_t;constexpr int N = 1e6 + 8;constexpr ull mod = (1ull << 61) - 1;mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());uniform_int_distribution<ull> dist(mod / 2, mod - 1);const ull H = dist(rnd);struct mull { ull x; constexpr...

Brute Force CF1997E. Level Up Monocarp 正在玩一款电脑游戏。他从等级 111 开始。他将依次与 nnn 只怪物战斗，这些怪物的等级从 111 到 nnn 不等。 对于按顺序给出的每个怪物，Monocarp 的遭遇如下： 如果 Monocarp 的等级高于怪物的等级，则怪物会逃跑； 否则，Monocarp 会与怪物战斗。 在每与第 kkk 个怪物战斗（逃跑的怪物不计算在内）后，Monocarp 的等级会增加 111 。因此，他在与 kkk 个怪物战斗后等级变为 222 ，在与 2k2k2k 个怪物战斗后等级变为 333 ，以此类推。 你需要处理 qqq 个查询，每个查询的格式如下： i xi~xi x ：如果参数 kkk 等于 xxx ，Monocarp 是否会与第 iii 个怪物战斗？ 方法一 首先离线询问。 无论用什么方法，k=1k=1k=1 时总是退化为暴力，因此考虑根号分治，当 k<nk<\sqrt{n}k<n​ 时暴力。这部分的复杂度 Θ(nn)\Theta(n\sqrt{...

Given a text s[] and a pattern p[], print all occurrences of p[] in s[]. Brute force solution 最坏时间复杂度 Θ(mn)\Theta(mn)Θ(mn)。 12345678910int i = 0, j = 0;while (i < s.length()) { if (s[i] == T[j]) ++i, ++j; else i = i-j+1, j = 0; if (j == T.length()) { // 匹配成功 printf("[%d-%d] ", i-j, i-1); i = i - j + 1; j = 0; }} KMP Algorithm ——Knuth-Morris-Pratt 字符串查找算法 PMT（Partial Match Table，部分匹配表...

后缀数组 后缀数组 (Suffix Array, SA) 是把字符串的所有 后缀 按 字典序 排序后得到的数组。 定义： 排名数组 rk⁡w(i)\operatorname{rk}_w(i)rkw​(i)：从第 iii 位开始、长度为 www 的子串在所有长度为 www 的子串中的排名； 编号数组 sa⁡w(i)\operatorname{sa}_w(i)saw​(i)：长度为 www 的子串中字典序第 iii 小的一个的开始位置，与排名数组互逆，即 sa⁡(rk⁡(i))=i\operatorname{sa}(\operatorname{rk}(i))=isa(rk(i))=i，rk⁡(sa⁡(i))=i\operatorname{rk}(\operatorname{sa}(i))=irk(sa(i))=i。 用倍增法在 Θ(nlog⁡n)\Theta(n\log n)Θ(nlogn)...

ST Table ST 表 (Sparse Table, 稀疏表) 基于 倍增 思想，用于解决 可重复贡献问题 †^\dagger†，支持在 Θ(1)\Theta(1)Θ(1) 的时间内 区间查询，不支持在线修改。 递推计算所有长度为 222 的幂的区间的结果。对于询问 [l,r)[\mathscr{l}, r)[l,r)，记 k=⌊log⁡2(r−l)⌋k = \lfloor \log_2(r - \mathscr{l}) \rfloork=⌊log2​(r−l)⌋，结果为 [l,l+2k)[\mathscr{l}, \mathscr{l} + 2^k)[l,l+2k) 和 [r−2k,r)[r - 2^k, r)[r−2k,r) 的结果的并。 †:^\dagger:†: 区间询问对应的运算符 ∗*∗ 满足 x∗x=xx*x=xx∗x=x 和结合律 (x∗y)∗z=x∗(y∗z)(x*y)*z=x*(y*z)(x∗y)∗z=x∗(y∗z) ，如 max⁡, min⁡, ∣ , &, gcd⁡\max,\ \min,\ |\ ,\ \&,\...

二叉树 先序遍历：先遍历根节点，然后遍历左节点，最后遍历右节点 中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（大概可以理解为把树平面投影至二维从左到右） 后序遍历：先遍历左节点，然后遍历右节点，最后遍历根节点 树上差分 Adjacent Difference on Tree 问题 每次操作将树上 u→vu\to vu→v 路径上的所有点权增加 ddd，求每个点的点权。 思路 用类似前缀和的思想存储树上的点权。用 val[p] 存储 ppp 节点上方的点权增加值，对于上述操作，按差分思想，只需 12val[u] += d; val[v] += d;val[lca(u,v)] -= d; val[p[lca(u,v)] -= d; 复原时，从根节点开始一步步累加。 1234567void dfs2(int u, int p = 0) { for (auto& v : E[u]) { if (v == p) continue; dfs2(v, u); val[u]...