小明の雜貨鋪

P2756 飞行员配对方案问题 P2756 飞行员配对方案问题 - 洛谷 二分图最大匹配，用最大流跑也没问题 1234567891011121314151617181920212223242526272829signed main(){ int n, m; cin >> m >> n; MaxFlow maxflow(n + 5); int s = n + 1; int t = n + 2; for(int i = 1; i <= m; i++){ maxflow.add(s, i, 1); } for(int i = m + 1; i <= n; i++){ maxflow.add(i, t, 1); } int u, v; while(cin >> u >> v){ if(u == -1 && v == -1)break; ...

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

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

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

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

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

二叉树 先序遍历：先遍历根节点，然后遍历左节点，最后遍历右节点 中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（大概可以理解为把树平面投影至二维从左到右） 后序遍历：先遍历左节点，然后遍历右节点，最后遍历根节点 树上差分 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]...

和 ⩾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); ...

在树上，我们可以任选一个节点作为根节点，从而定义出每个节点的深度和每棵子树的根。 在 DP 的状态表示中，第一维通常是节点编号，第二维代表状态基 。大多数时候，我们采用 递归 的方式实现树形动态规划。对于每一个节点 xxx，先递归它的每一个子节点上进行 DP ，在 回溯时，从子节点向节点 xxx 进行状态转移。 有根树的树形 DP 树背包 有根树，有点权。mmm 元点集 SSS 满足：若子节点 ∈S\in S∈S，则父节点 ∈S\in S∈S。最大化 SSS 点权和。 123456789101112int n, m, w[N], dp[N][M];auto dfs = [&](this auto&& dfs, int u) -> void { dp[u][1] = w[u]; for (auto& v : E[u]) { dfs(v); for (int k = m; k >= 1; --k) { for (int i = k; i...