XCPC wiki - 质数与约数
![[…/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 题意 已知...
XCPC wiki - 计算几何
平面计算几何 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 *...
XCPC wiki - 树习题集
树上思维 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。 这就是经典的动态树直径问题。 复杂度 Θ(nlogn+q(logn+logq))\Theta(n \log n + q(\log n + \log...
XCPC wiki - Python
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 *...
XCPC wiki - 组合数学
逆元 模为素数 123456789101112131415constexpr int mod = 998244353;ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res;}int inv(int n) { return qpow(n, mod - 2);} // 1/a (p 是素数) 非固定模数 123456789101112131415161718192021222324252627282930ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}ll exgcd(ll a, ll b, ll& x, ll& y) { if (b ==...
XCPC wiki - 构造
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 <...
XCPC wiki - 交互
博弈 CF1991E. Coloring Game (1900) 有一个由 nnn 个顶点和 mmm 条边组成的无向图。每个顶点可以用三种颜色之一着色。初始时，所有顶点都未着色。 Alice 和 Bob 正在玩一个包含 nnn 轮的游戏。在每一轮中，都会发生以下两个步骤： Alice 选择两种不同的颜色。 Bob 选择一个未着色的结点，并用 Alice 选择的两种颜色之一为其着色。 如果存在连接两个相同颜色结点的边，则 Alice 获胜。否则 Bob 获胜。给你这个图。决定想扮演哪位玩家并赢得游戏，然后与交互库玩这个游戏。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475void eachT() { int n, m; cin >> n >> m; ...
Codeforces Round 1000 (Div. 2) A - E
2063A - Minimal Coprime 称一个区间 [ℓ,r][\ell,r][ℓ,r] 为 minimal coprime，如果它不存在左右端点互素的真子区间， 如果原区间长度 ⩾3\geqslant 3⩾3，考虑真子区间 [ℓ,ℓ+1][\ell,\ell+1][ℓ,ℓ+1]，它左右端点互素，因此不是 minimal coprime； 如果原区间长度 =2=2=2，且 ℓ>1\ell>1ℓ>1，则 ℓ+1=r\ell+1=rℓ+1=r，它自己是互素的，其全部真子区间为 [ℓ,ℓ],[r,r][\ell,\ell],[r,r][ℓ,ℓ],[r,r]，都是左右端点不互素的，是 minimal coprime。 如果原区间长度 =1=1=1，且 ℓ≠1\ell \neq 1ℓ=1，它自己左右端点不互素，不是 minimal coprime； 特别地，[1,1][1,1][1,1] 是 minimal coprime，[1,2][1,2][1,2] 不是 minimal coprime。 综上...
〔主机註記〕第 50 周主机註記 (Janu.20 - Janu.26)
第 50 周主机註記 月曜日 (Janu.20) 火曜日 (Janu.21) 水曜日 (Janu.22) 木曜日 (Janu.23) 錘子 「這題能線段樹嗎？」 「蘑菇說了不要問能做什麽，先說你想要什麽。」 …… 「我會笛卡爾樹。」 「你會個錘子？」 金曜日 (Janu.24) 寫一 我可以寫一千字我好想你。 這才兩天，我的戒斷反應就如此嚴重…… 不敢參加最後一次區域賽…… 界限 0:00 直到睡覺這段時間寫的文字，應歸在前一天還是當天，這我一直沒有統一。 對於我來說，一天的界限並不是 0:00 - 24:00，而是從起床到睡覺，我想對絕大多數人來說也是如此。 活動有連續性，生活有慣性。如果一份工作從晚上持續到第二天淩晨，我會認爲 0:00 後的時間仍是前一天活動的一部分，將這段時間視爲一個整體。就比如說，現在是 Janu.25 的 2:46，我仍在寫金曜日的主机註記，記錄這一天的所思所想。 倒不如說，人的心理狀態和情緒往往具有延續性。前一天晚上的某種情緒狀態，會延續到淩晨 0:00...
IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2) A-F1
2061A - Kevin and Arithmetic 第一个偶数，后面都是奇数。 123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>using ll = long long;using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; int cnt = 0; bool flag = 0; for (int i = 0; i < n; i++) { int x; cin >> x; ...