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 - 交互
博弈 CF1991E. Coloring Game (1900) 有一个由 nnn 个顶点和 mmm 条边组成的无向图。每个顶点可以用三种颜色之一着色。初始时，所有顶点都未着色。 Alice 和 Bob 正在玩一个包含 nnn 轮的游戏。在每一轮中，都会发生以下两个步骤： Alice 选择两种不同的颜色。 Bob 选择一个未着色的结点，并用 Alice 选择的两种颜色之一为其着色。 如果存在连接两个相同颜色结点的边，则 Alice 获胜。否则 Bob 获胜。给你这个图。决定想扮演哪位玩家并赢得游戏，然后与交互库玩这个游戏。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475void eachT() { int n, m; cin >> n >> m; ...
XCPC wiki - 并查集 Disjoint Set Union (Uno-Find Set)
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 =...
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) 土曜日 (Janu.25) 消费 生产者、初级消费者、次级消费者……我，或者说人类，也是消费者。 消费这种行为我们已经很熟悉了。买衣服，买电脑，吃喝玩乐，衣食住行，只要给钱，我们都能买到。 有话讲：买书如山倒，看书如抽丝。消费社会给了我们一个错觉，它鼓励我们消费，让我们认为只要消费，就能拥有。 但是很多东西仅仅消费，是无法拥有的、我们给了钱，这只是代表我们支付了第一次，如果你真正想要拥有这个东西，你还需要调集自己的精力，去支付第二次。比如从没翻开的书，从没点开过的游戏，从没使用的软件…… 所以正常的逻辑，应该是我们在确定第二次支付一定会发生的时候，才进行第一次支付。也可以认为，买东西只能叫「交易」，当每天在用这个东西的时候，才是真正的「消费」。 可是这种理性消费模式，又怎么对得起这个物资极度发达的消费社会呢？ 你买下一个东西，只能叫做交易，当你每天在用这个东西的时候，才叫做消费。 ...
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; ...
Codeforces Round 998 (Div. 3) A - G
2060A - Fibonacciness 暴力枚举所有的 a3a_{3}a3。 12345678910111213141516171819202122232425#include <bits/stdc++.h>using ll = long long;using namespace std;int main() { int t; cin >> t; while (t--) { int a1, a2, a4, a5; cin >> a1 >> a2 >> a4 >> a5; int res = 0; for (int a3 = -100; a3 <= 100; a3++) { int cnt = 0; cnt += a1 + a2 == a3; cnt += a2 + a3 == a4; cnt += a3...
Codeforces Round 997 (Div. 2) A - E
2056A - Shape Perimeter 12345678910111213141516171819202122232425#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, m; cin >> n >> m; int res = 4 * m * n; for (int i = 0, a, b; i < n; i++) { cin >> a >> b; if (i) res -= m - a + m - b << 1;...
〔主机註記〕第 49 周主机註記 (Janu.13 - Janu.19)
第 49 周主机註記 月曜日 (Janu.13) 火曜日 (Janu.14) 水曜日 (Janu.15) 木曜日 (Janu.16) 金曜日 (Janu.17) 土曜日 (Janu.18) 日曜日 (Janu.19)
Codeforces Round 996 (Div. 2) A - D
2055A - Two Frogs 1234567891011121314151617#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { int t; cin >> t; while (t--) { int n, a, b; cin >> n >> a >> b; cout << ((a - b) % 2 == 0 ? "YES" : "NO") << endl; } return 0;} 2055B - Crafting 如果存在多个 ai<bia_{i}<b_{i}ai<bi 就无解，因为 A 加一的时候 B 减一，B 加一的时候 A 又要减一，这两者不可能同时增加。 现在只需要把一个 aia_{i}ai...
