邏輯與算法
邏輯與算法 (0) 問題 (0) 原創問題 (0) 模板 (0) 知識 (0)DP 動態規劃與優化 (0)Ad-Hoc (0)GameTheory 博弈論 (0)GraphTheory 圖論 (0)01 (0)ACMM (0)Combinatorics 組合論 (0)String (0) 賽事 (0)Contest (0)EducationalCodeforces (0)Atcoder (0)Codeforces (0) if (typeof window.explorerInit === 'undefined') { window.explorerInit = true; const style = document.createElement('style'); style.innerHTML = '.explorer-folder:hover {background-color: var(--body-bg-shadow); }'; ...
快写
12345678910for (int i = 0; i < N; i++) { std::cin >> A[i];}auto g = A;std::ranges::sort(g);g.erase(std::ranges::unique(g).begin(), g.end());for (auto& x : A) { x = std::ranges::lower_bound(g, x) - g.begin();} chmax 123456789template<class T>void chmax(T& x, const T& other) { if (x < other) x = other;}template<class T>void chmin(T& x, const T& other) { if (x > other) x = other;} 树...
ABC437G
ABC437G - Colorful Christmas Tree 一道题建了三个新图，算上原树总共四个图 ww 给定 NNN 点树，每个节点初始被染成 012 三种颜色之一。 执行以下操作 N−1N-1N−1 次：选择一条当前存在、且两端点颜色不同的边，将其删除，然后将这条边两端点的颜色，按照 0 →\to→ 1 →\to→ 2 →\to→ 0 的循环顺序变为下一种颜色。 判断是否存在一种合法的删边顺序，能够把树上的边全部删完。若存在，输出之。 Step.1 转化为匹配 在全过程中，顶点 vvv 处于颜色 kkk 时参与删除，这个操作次数确定，记为 Av,kA_{v, k}Av,k。这给定了每个点在特定颜色下需要消耗的额度，因此这本质上是一个匹配问题。 建图： 点：将一个点 vvv 拆成 Av,kA_{v,k}Av,k 个点 (v,k)(v,k)(v,k)。 边：对于一条边 u−vu-vu−v，如果 (u,k1)(u,k_{1})(u,k1) 和 (v,k2)(v,k_{2})(v,k2) 颜色不同，则连边 (u,k1)−(v,k2)(u, k_1)-(v,...
交互
CF2210E CF2210E. Binary Strings are Simple? 交互。 猜测长度为 NNN 的 01 串。 每次询问子串 S[l…r]S[l\dots r]S[l…r]，返回子串所有循环移位的逆序对数 mod 子串长度的集合大小。 询问的代价为 Nr−l+1\dfrac{N}{r-l+1}r−l+1N，总询问代价不超过 max(30,3N)\max(30,3 N)max(30,3N)。 最多可以猜测 222 次。 当循环左移 1 时贡献是 −c0=c1−n-c_0=c_1-n−c0=c1−n，否则是 c1c_1c1，逆序对在模意义下的增量总是 c1c_1c1。因此询问实际是 #{x:x=kc1 mod N,k∈[1,N]}=Ngcd(N,c1)\#\{x : x=kc_1\bmod N, k\in[1,N]\} = \displaystyle\frac{N}{\gcd(N,c_1)}#{x:x=kc1modN,k∈[1,N]}=gcd(N,c1)N。 奇偶。在仅知道...
2025 ICPC 沈阳 C
2025 ICPC 沈阳 C 【题意】第一次运行给定 NNN 个正整数 Xi∈[1,M]X_{i} \in [1,M]Xi∈[1,M]，为每个数构造一个长度为 3M3 M3M 的序列，每个序列中 111 到 MMM 的整数恰好出现 3 次。jury 独立地将每个序列映射成二进制序列，第二次运行需要从这些二进制序列中解密出每个 XiX_{i}Xi。 很牛的题。喜欢 communication。 【思路】既然是 3M3M3M 且恰好出现 3 次，我们就分成三段，每段是长为 MMM 的 permutation。第一段就设为 1,2,…,M1,2,\dots,M1,2,…,M，这样直接知道每个字符映射成 0 还是 1 了。然后想想后面两个 permutation 怎么搞才能保证是单射。 最简单的方法是 rotation（循环移位），直接移 XiX_{i}Xi 位。 可以吗？有个小问题，如果映射出的序列有周期 TTT，那就分不出来了。比如原串是 1010，移位后是 0101，移了 1 还是 3 不得而知。 如何修正？什么串没有周期？素数！给...
FWT
123456789101112131415161718192021222324252627282930313233#include <vector>#include <utility> // for std::swaptemplate <typename T>void FWT(std::vector<T>& f, T m00, T m01, T m10, T m11) { const int N = f.size(); for (int k = 1; k < N; k <<= 1) { for (int j = 0; j < N; j += (k << 1)) { for (int i = 0; i < k; i++) { T& u = f[i + j]; T& v = f[i + j + k]; ...
多组数据
...
ABC461G
ABC461G - Graph Problem 2026 NNN 点 MMM 边简单无向图，在点权 www 满足如下条件时，求 ∑w∗\sum{w_*}∑w∗ 的最大值。 对每个点 iii，wi∈{0,1,2}w_i \in \lbrace 0, 1, 2 \rbracewi∈{0,1,2}。 对每个边 (u,v)(u,v)(u,v)，wu+wv∈{0,1,2}w_{u}+w_{v} \in \lbrace 0, 1, 2 \rbracewu+wv∈{0,1,2}。 拆点，令 wi=wi0+wi1w_{i}=w_{i_{0}}+w_{i_{1}}wi=wi0+wi1，并钦定 wi0,wi1∈{0,1}w_{i_{0}},w_{i_{1}} \in \lbrace 0, 1 \rbracewi0,wi1∈{0,1}，问题将三个权选择化为每个点的选与不选。希望所选点最多。 考虑边的约束 wu0+wu1+wv0+wv1∈{0,1,2}w_{u_{0}}+w_{u_{1}}+w_{v_{0}}+w_{v_{1}} \in \lbrace 0, 1,...
Fast Exponentiation
快速幂 Fast Exponentiation 1234567891011// Quick powertemplate<class T>constexpr T qpow(T a, u64 n) { T res = identity(a); for (; n; n /= 2, a *= a) { if (n & 1) { res *= a; } } return res;} 矩阵快速幂 1234567891011121314151617181920212223242526272829// ---------------- Matrix ---------------- //using Matrix = std::array<std::array<Z, 64>, 64>; // change here for different size or typeconstexpr Matrix...