小明の雜貨鋪

multiset 的 maintain 法 枚举左端点，使用大小根堆 maintain 求出所有右端点的答案。时间复杂度 Θ(n2log⁡n)\Theta(n^{2}\log n)Θ(n2logn)。 例 1 求 {a}\lbrace a \rbrace{a} 的所有子序列的中位数，数据范围：n⩽2000, 0⩽ai⩽109n \leqslant 2000,\ 0 \leqslant a_{i} \leqslant 10^{9}n⩽2000, 0⩽ai​⩽109。 12345678910111213141516171819202122int n = read();for (int i = 1; i <= n; i++) a[i] = read();for (int i = 1; i <= n; i++) { priority_queue<int, vector<int>> L; priority_queue<int, vector<int>, greater<>> R; int mid =...

效率更高的 __builtin_popcount() 函数，即 123456789template <typename T>  unsigned int __builtin_popcount(T u) {      u = (u & 0x55555555) + ((u >> 1) & 0x55555555);      u = (u & 0x33333333) + ((u >> 2) & 0x33333333);      u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);      u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);      u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);      return u;  } 二分转化为 01...

和 ⩾s\geqslant s⩾s 的最短子区间 12345678910111213141516171819void eachT() { int n = read(), s = read(); vector<ll> pre(n + 1); for (int i = 1; i <= n; ++i) { pre[i] = pre[i - 1] + read(); } int ans = inf; for (int l = 1, r = 1; l <= n; l++) { while (r < n && pre[r] - pre[l - 1] < s) { // 当前不满足 r++; } if (pre[r] - pre[l - 1] >= s) { ans = min(ans, r - l + 1); ...

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

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

树上思维 2024 CCPC 济南 L. Intersection of Paths 在树上选择 kkk 条路径，路径的 2k2k2k 个端点必须互不相同。最大化被所有路径包含的边权之和。有多次询问，每次询问会临时修改一条边的边权。每次询问的 k 可能不同。 节点数、询问数 5×1055 \times 10^{5}5×105。 可能被端点两两不同的 kkk 条路径包含的边，需要满足把这条边去掉之后，形成的两个连通块大小都大于等于 kkk。在 kkk 固定的情况下，这些边形成了一棵树。所以答案就是这棵树的直径。 kkk 变化的时候怎么办？注意到 k+1k + 1k+1 的树被 kkk 的树完全包含，所以可以将所有询问按 k 从小到大排序，依次处理。 问题变为：每次询问临时修改一条边的边权，以及在 kkk 变大时永久删掉若干条边，求树直径。删掉边可以转化为将边权改成 000。 这就是经典的动态树直径问题。 复杂度 Θ(nlog⁡n+q(log⁡n+log⁡q))\Theta(n \log n + q(\log n + \log...

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

用于解决多阶段的优化问题。在总体最优策略无法给出的情况下，每一步的选择都是求局部最优解：当求目标函数值最大时，选择当前最大值；当求目标函数值最小时，选择当前最小值。 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，可以填...

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

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