小明の雜貨鋪

![[…/data/img/e5e92bc7d32828b005d6b7f73694da57_720.jpg]] 素数筛 （欧拉筛） 1234567891011121314vector<int> prime;int mint[N]; // 最小素因子 void init() { for (int i = 2; i < N; i++) { if (!mint[i]) mint[i] = i, prime.push_back(i); for (auto& p : prime) { if (1ll * i * p >= N) break; mint[i * p] = p; if (p == mint[i]) break; } } mint[1] = 1;} 时间复杂度 Θ(n)\Theta(n)Θ(n) VJwin6D - 又见 GCD 题意 已知...

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

DSU01 - Find by Optimized Path Compression 路径压缩优化 12345678910111213141516171819202122232425262728struct DSU { vector<int> p, siz; DSU(int n) : p(n + 1), siz(n + 1, 1) { iota(p.begin(), p.end(), 0); } int find(int x) { while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩 return x; } bool same(int x, int y) { return find(x) == find(y); } bool uno(int x, int y) { x = find(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,\ |\ ,\ \&,\...

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