小明の雜貨鋪

三分法求凸函数最值 求类似开口朝上的二次函数的最小值： 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 <<...

12345678910111213141516171819202122232425262728293031323334353637383940414243444546/** 一维前缀和 **/vector<ll> pre(n + 1);for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + a[i];}// 查询 [l, r)auto get = [&](int l, int r) { return pre[r] - pre[l];};/** 二维前缀和 **/vector s(m + 1, vector<ll>(n + 1));for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { s[x + 1][y + 1] = s[x + 1][y] + s[x][y + 1] - s[x][y] + a[x][y]; }}//...

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) { ...

二分图 Stop the Castle There are n castles and m obstacles on a chessboard. Each castle or obstacle occupies exactly one cell and all occupied cells are distinct. Two castles can attack each other, if they’re on the same row or the same column, and there are no obstacles or other castles between them. Find a way to place the minimum number of additional obstacles onto the chessboard, so that no two castles can attack each...

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{...

用于解决多阶段的优化问题。在总体最优策略无法给出的情况下，每一步的选择都是求局部最优解：当求目标函数值最大时，选择当前最大值；当求目标函数值最小时，选择当前最小值。 CF1930D. Sum over all Substrings 题意 对于一个长度为 LLL 的 01 串 ppp，定义一个长度为 LLL 的 01 串 qqq 关于 ppp 是好的，当且仅当 ∀i∈[1,n]\forall i\in[1,n]∀i∈[1,n] 满足：∃1≤l≤i≤r≤L\exists1\leq l\leq i\leq r\leq L∃1≤l≤i≤r≤L，满足 pip_ipi​ 为 q[l,r]q[l,r]q[l,r] 的区间众数。定义 g(p)g(p)g(p) 为所有关于 ppp 是好的串 qqq 中 111 的个数的最小值。 给定一个长度为 nnn 的 010101 串 sss，求 sss 所有子串的 ggg 的和。 思路 贪心地，每个 pi=1p_{i}=1pi​=1 只需要在左中右三个位置之一选择一个填 111。 从前向后遍历，如果 pi=1p_{i}=1pi​=1，可以填...

Strings 子序列 将若干元素提取出来并不改变相对位置形成的序列，不一定连续。 子串 连续的子序列。 后缀 （Suffix）从某位置到整个串末尾结束的子串。 前缀 （Prefix）从串首开始到某位置结束的子串。 字典序 以第 iii 个字符作为第 iii 关键字进行大小比较，空字符小于字符集内任何字符。

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...

后缀数组 后缀数组 (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)...

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，部分匹配表...