小明の雜貨鋪

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]; }}//...

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,\ |\ ,\ \&,\...

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

平面计算几何 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899using T = double;const double eps = 1e-9, pi = acos(-1.0);int sgn(T x) { return (fabs(x) <= eps) ? 0 : (x < 0 ? -1 : 1);}struct P { T x, y; P() : x(0), y(0) {} P(T x, T y) : x(x), y(y) {} // P(T r, double alpha, int _) : x(r * cos(alpha)), y(r *...

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

2024 牛客多校 9I - Interesting Numbers [[…/contests/2024 牛客多校 /2024-08-13：2024 牛客暑期多校训练营 9|2024-08-13：2024 牛客暑期多校训练营 9]] 1234567891011121314151617181920import mathn = int(input())l, r = map(int, input().split())def slove(k) : wei = 10 ** (n // 2) half1 = k // wei half2 = k % wei half3 = 10 ** (n // 2) sqr1 = math.isqrt(half1) sqr2 = math.isqrt(half2) sqr3 = math.isqrt(half3) if sqr3 * sqr3 == half3: sqr3 -= 1 if half1 == sqr1 ** 2: return sqr1 *...

博弈 CF1991E. Coloring Game (1900) 有一个由 nnn 个顶点和 mmm 条边组成的无向图。每个顶点可以用三种颜色之一着色。初始时，所有顶点都未着色。 Alice 和 Bob 正在玩一个包含 nnn 轮的游戏。在每一轮中，都会发生以下两个步骤： Alice 选择两种不同的颜色。 Bob 选择一个未着色的结点，并用 Alice 选择的两种颜色之一为其着色。 如果存在连接两个相同颜色结点的边，则 Alice 获胜。否则 Bob 获胜。给你这个图。决定想扮演哪位玩家并赢得游戏，然后与交互库玩这个游戏。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475void eachT() { int n, m; cin >> n >> m; ...

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

树上思维 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...

2024 东北四省 K / CC 网络赛模拟 C. Tasks Link [[…/contests/2024-09-07-2024 CCPC 网络赛热身赛 |2024-09-07-2024 CCPC 网络赛热身赛]] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253int n;cin >> n;using node = struct { int l, r, b, id; };vector<node> a(n);for (int i = 0; i < n; ++i) { cin >> a[i].l >> a[i].b; a[i].id = i;}sort(a.begin(), a.end(), [&](node a, node b) { return a.l == b.l ? a.b < b.b : a.l <...