https://codeforces.com/gym/102769?f0a28=1
A
- 题意：
- 给你 r 个红球，b 个蓝球，
- 求选择 2 个红球的概率
- 题解：
- 组合数 gcd
#include #includeB#include using namespace std; using ll = long long; using T = int; T rad(); // quick read const int inf = 0x3f3f3f3f; #define rf(i, n) for (int i = 1; i <= (n); ++i) const int max_size = 5 + 100; const int maxn = 5 + 100; int c(int n, int m) { int ret = 1; for (int dwn = 1, up = n; dwn <= m; ++dwn, --up) { ret = ret * up / dwn; } return ret; } int main() { int q = rad(); rf(i, q) { int r = rad(), b = rad(); int up = c(r, 2), dwn = c(r + b, 2); int g = __gcd(up, dwn); printf("Case #%d: %d/%dn", i, up / g, dwn / g); } } T rad() { T back = 0; int ch = 0, posi = 0; for (; ch < '0' || ch > '9'; ch = getchar()) posi = ch ^ '-'; for (; ch >= '0' && ch <= '9'; ch = getchar()) back = (back << 1) + (back << 3) + (ch & 0xf); return posi ? back : -back; }
-
题意：
- 有一个地图，地图的点有好坏之分
- 矩形边界不能有坏点
- 两种操作：
- 改变地图某点的状态
- 求经过某点的最大矩形
-
题解（可能，我也没过，看不到数据的模拟题就是毒瘤）：
- 修改：维护
l
[
i
]
[
j
]
,
r
[
i
]
[
j
]
,
u
[
i
]
[
j
]
l[i][j], r[i][j], u[i][j]
l[i][j],r[i][j],u[i][j]，分别表示点
(
i
,
j
)
(i, j)
(i,j) 左边，右边，上面第一个坏点的横/纵坐标。
- 更改所在行列即可
- 查询点
(
x
,
y
)
(x, y)
(x,y)：考虑点在最优矩形下边界的情况：
- 倒序枚举顶边 i ∈ [ 1 , x − 1 ] i in [1, x - 1] i∈[1,x−1]
- 这一行的某些列可能是坏点，导致这一列不能作为边框的边界，移动后对相关列打标记。
- 直接寻找底的每一列第一个出现坏点的行，当 i 移动过这行的时候，就把这些列标记。
- 寻找最大的左右边界
n
l
,
n
r
nl, nr
nl,nr
- 问题转化：寻找区间内，第一个不为 1 的点
- 路径压缩并查集维护
- s = max ( s , ( r − l + 1 ) ∗ ( x − j + 1 ) ) s = max(s, (r - l + 1) * (x - j + 1)) s=max(s,(r−l+1)∗(x−j+1))
- 不在最优矩形下边界的情况，对称地考虑即可
- 修改：维护
l
[
i
]
[
j
]
,
r
[
i
]
[
j
]
,
u
[
i
]
[
j
]
l[i][j], r[i][j], u[i][j]
l[i][j],r[i][j],u[i][j]，分别表示点
(
i
,
j
)
(i, j)
(i,j) 左边，右边，上面第一个坏点的横/纵坐标。
列标记的过程可以用并查集维护，因为是一段连续的区间，维护这段连续的、不能选的列的左右端点即可。
这里给出一个测试样例，以供参考：
1 5 11 100 #.#######.# ##.#####.## ###.###.### ####.#.#### ########### 2 4 6 2 5 6 1 2 3 1 2 9 2 5 6E
- 题意：
- 每个人的成绩有两种可能
- 及格线为最高成绩的 m%
- 求最多多少人及格
- 题解：
- 双指针
- 从小到大枚举区间右端点
- 维护区间内的人数
- treap
- 树状数组
- 双指针
#include #includeF#include using namespace std; using ll = long long; using T = int; T rad(); // quick read const int inf = 0x3f3f3f3f; #define rf(i, n) for (int i = 1; i <= (n); ++i) const int maxn = 5 + 2e5; struct Node { int val, id; bool operator<(const Node &r) const { return val != r.val ? val < r.val : id < r.id; } }; int n, m; Node a[maxn << 1]; int cnt[maxn]; int main() { int Q = rad(); rf(q, Q) { n = rad(), m = rad(); rf(i, n) { a[i].val = rad(), a[i].id = i; a[i + n].val = rad(), a[i + n].id = i; } sort(a + 1, a + 1 + 2 * n); memset(cnt, 0, sizeof(cnt)); int l = 1, r = 1; ll num = 0; for (; num < n; ++r) if (++cnt[a[r].id] == 1) num++; while ((ll)a[l].val * 100 < (ll)a[r - 1].val * m) { if (--cnt[a[l].id] == 0) --num; ++l; } ll ans = 0; for (ans = num; r <= 2 * n; ++r) { if (++cnt[a[r].id] == 1) ++num; while ((ll)a[l].val * 100 < (ll)a[r].val * m) { if (--cnt[a[l].id] == 0) --num; ++l; } ans = max(ans, num); } printf("Case #%d: %lldn", q, ans); } } T rad() { T back = 0; int ch = 0, posi = 0; for (; ch < '0' || ch > '9'; ch = getchar()) posi = ch ^ '-'; for (; ch >= '0' && ch <= '9'; ch = getchar()) back = (back << 1) + (back << 3) + (ch & 0xf); return posi ? back : -back; }
- 题意：
- 无向图，选择一些点，
- 每个点将使 “计数值” 减 1，每条边将使 “计数值” 加 1
- 求最大 “计数值”
- 题解：
- 贪心 连通块
- 对于一个连通块，多选择一个点不会使解变差（因为至少多了一条边）
- 所以总是选择完整的连通块
- 累加正贡献的连通块的 “计数值”
- 贪心 连通块
#include #includeG#include using namespace std; using ll = long long; using T = int; T rad(); // quick read const int inf = 0x3f3f3f3f; #define rf(i, n) for (int i = 1; i <= (n); ++i) const int max_size = 5 + 1e6; const int maxn = 5 + 3e5; int tot; struct Node { int to; Node *nex; } pool[max_size << 1], *head[maxn]; inline void add(int l, int r) { pool[++tot] = {r, head[l]}; head[l] = pool + tot; } int n, m; bool visit[maxn]; inline void init() { tot = 0; memset(head, 0, sizeof(Node *) * (n + 5)); memset(visit, 0, sizeof(bool) * (n + 5)); visit[0] = 1; } void dfs(int u, int &vertex, int &edg) { visit[u] = 1, vertex++; // 顶点计数 for (auto now = head[u]; now; now = now->nex) { int v = now->to; edg++; // 边计数 if (visit[v]) continue; dfs(v, vertex, edg); } } int main() { int Q = rad(); rf(q, Q) { n = rad(), m = rad(); init(); rf(i, m) { int l = rad(), r = rad(); add(l, r), add(r, l); } int ans = 0; rf(i, n) { if (!visit[i]) { int vertex = 0, edg = 0; dfs(i, vertex, edg); ans += max(0, edg / 2 - vertex); } } printf("Case #%d: %dn", q, ans); } } T rad() { T back = 0; int ch = 0, posi = 0; for (; ch < '0' || ch > '9'; ch = getchar()) posi = ch ^ '-'; for (; ch >= '0' && ch <= '9'; ch = getchar()) back = (back << 1) + (back << 3) + (ch & 0xf); return posi ? back : -back; }
- 题意：
- x 是 good number，指 ⌊ x k ⌋ lfloor sqrt[k] x rfloor ⌊kx ⌋ 整除 x x x
- 求 [0, n] 之间 good number 的数量
- 题解：
- 分块
- 设 i = ⌊ x k ⌋ i = lfloor sqrt[k] x rfloor i=⌊kx ⌋
- ∵ ⌊ x k ⌋ ∣ x because lfloor sqrt[k] x rfloor | x ∵⌊kx ⌋∣x
- ∴ x ∈ [ i k , ( i + 1 ) k ) therefore x in [i^k, (i + 1)^k) ∴x∈[ik,(i+1)k)
- 枚举
i
,
i
k
∈
[
0
,
n
]
i, i^k in [0, n]
i,ik∈[0,n]
- 对
∀
j
∈
[
i
k
,
(
i
+
1
)
k
)
,
i
∣
j
forall j in [i ^k, (i + 1)^k), i | j
∀j∈[ik,(i+1)k),i∣j 计数
- 等差数列在区间中的通项数量
- 对
∀
j
∈
[
i
k
,
(
i
+
1
)
k
)
,
i
∣
j
forall j in [i ^k, (i + 1)^k), i | j
∀j∈[ik,(i+1)k),i∣j 计数
- 注意特判
k
>
31
k > 31
k>31，
- 溢出了
- 而且显然此时 [ 1 , 2 k ) [1, 2^k) [1,2k) 覆盖所有 x x x
- 分块
#include #includeI#include using namespace std; using ll = long long; using T = int; T rad(); // quick read const int inf = 0x3f3f3f3f; #define rf(i, n) for (int i = 1; i <= (n); ++i) const int max_size = 5 + 100; const int maxn = 5 + 100; ll qpow(ll base, int k) { ll ret = 1; for (; k; base *= base, k >>= 1) { if (k & 1) ret *= base; } return ret; } int n, k; int main() { // rf(i, 10) cout << qpow(2, i) << " "; int Q = rad(); rf(q, Q) { n = rad(), k = rad(); int cnt = 0; if (k == 1 || k > 31) cnt = n; else for (int i = 1; 1; ++i) { ll l = qpow(i, k); if (l > n) break; int r = min(qpow(i + 1, k), n + 1LL); cnt += (r - 1 - l) / i + 1; // 等差数列通项数量 // for (int j = l; j < r; ++j) { // if (j % i == 0) cnt++; // } } printf("Case #%d: %dn", q, cnt); } } T rad() { T back = 0; int ch = 0, posi = 0; for (; ch < '0' || ch > '9'; ch = getchar()) posi = ch ^ '-'; for (; ch >= '0' && ch <= '9'; ch = getchar()) back = (back << 1) + (back << 3) + (ch & 0xf); return posi ? back : -back; }
-
题意：
- 研究二维向量，有两种操作，
- 获得一个向量
- 查询某向量是否是已知向量的线性组合
- 每次查询成立，我们都能获得一个权值 w
- 问 q 次操作后，最终权值是多少
- 研究二维向量，有两种操作，
-
题解：
- 辗转相除法 向量分解
- 已有 0 个向量时，一定不成立
- 已有 1 个向量时，判断是否共线
- 已有 2 个向量时，
- 设其分别为 a ⃗ , b ⃗ vec a, vec b a ,b ，
- 使用向量的辗转相除法，获得同基底的另一组向量
a
⃗
0
,
b
⃗
0
vec a_0, vec b_0
a
0,b
0，其中：
- a ⃗ 0 vec a_0 a 0 的第一个分量为 0，
- b ⃗ 0 vec b_0 b 0 的第二个分量小于 a ⃗ 0 vec a_0 a 0 的第一个分量（辗转相除法后直接取模）。
- 本质上是第一个分量的辗转相除法，只不过所有四则运算作用于所有分量，从而线性得到保证。
- 于是，对于方程 x ⃗ = k 1 a ⃗ 0 + k 2 b ⃗ 0 vec x = k_1 vec a_0 + k_2 vec b_0 x =k1a 0+k2b 0 中， k 2 k_2 k2 已知，判断 k 1 k_1 k1 是否存在即可（ ∵ because ∵ 只有 b ⃗ 0 vec b_0 b 0 对第一个分量有贡献）。
- 已有多个向量时，
- 对于新向量 c ⃗ vec c c 与 b ⃗ 0 vec b_0 b 0，作辗转相除法，消去 c ⃗ vec c c 的第一个分量
- 显然， a ⃗ 0 vec a_0 a 0 和 c ⃗ vec c c 的自由组合是 a ⃗ g vec a_{g} a g 的倍数， a ⃗ g vec a_{g} a g 的第一个分量是前两者的最大公因数。
- 更新 b ⃗ 0 vec b_0 b 0 的第二个分量
- 此时，问题回到向量数量为 2 的情况
- 辗转相除法 向量分解
#include #includeK#include #include using namespace std; using ll = long long; using T = int; T rad(); // quick read const int inf = 0x3f3f3f3f; #define rf(i, n) for (int i = 1; i <= (n); ++i) const int max_size = 5 + 100; const int maxn = 5 + 100; struct Node { ll x, y; bool operator<(const Node &r) const { return x != r.x ? x < r.x : y < r.y; } Node operator*(ll r) const { return Node{x * r, y * r}; } Node operator-(const Node &r) const { return Node{x - r.x, y - r.y}; } }; // 使用线性组合消除 a.x void zhanzhuan(Node &a, Node &b) { while (a.x != 0) { // printf("%d %d %d %dn", a.x, a.y, b.x, b.y); b = b - a * (b.x / a.x); swap(a, b); } } vector a; inline void update() { if (a.size() <= 1) return; if (a.size() == 2) { zhanzhuan(a[0], a[1]); a[1].y %= a[0].y; return; } zhanzhuan(a[2], a[1]); a[0].y = __gcd(a[0].y, a[2].y); a[1].y %= a[0].y; a.pop_back(); } inline bool check(int x, int y) { if (a.size() == 0) return 0; if (a.size() == 1) return x * a[0].y == y * a[0].x; return x % a[1].x == 0 &&(y - x / a[1].x * a[1].y) % a[0].y == 0; } int main() { int Q = rad(); rf(q, Q) { int n = rad(); ll cnt = 0; a.clear(); rf(i, n) { int op = rad(); if (op == 1) { int x = rad(), y = rad(); a.push_back({x, y}); update(); // printf("now: "); // for (auto p : a) // printf("%d %d ", p.x, p.y); // puts(""); } else if (op == 2) { int x = rad(), y = rad(), w = rad(); if (check(x, y)) cnt += w; } else if (op == 3) { } } printf("Case #%d: %lldn", q, cnt); } } T rad() { T back = 0; int ch = 0, posi = 0; for (; ch < '0' || ch > '9'; ch = getchar()) posi = ch ^ '-'; for (; ch >= '0' && ch <= '9'; ch = getchar()) back = (back << 1) + (back << 3) + (ch & 0xf); return posi ? back : -back; }
- 题意：
- 有根树的树根有无数个棋子
- 你可以使一个棋子移动一步
- 求走完所有顶点的最少步数
- 题解：
- 树型dp
- 状态转移
- f [ i ] [ 1 / 0 ] f[i][1/0] f[i][1/0]：从根开始，到遍历完子树 i 为止，是否回到 i 的路径长
- d i s [ u ] dis[u] dis[u]：从根到 u 的距离
- f [ u ] [ 0 ] = min { f [ u ] [ 1 ] + f [ v ] [ 0 ] − d i s [ u ] , 前 面 的 子 树 回 来 ， 当 前 子 树 不 回 来 f [ u ] [ 0 ] + f [ v ] [ 1 ] − d i s [ u ] + 1 , 前 面 的 子 树 不 回 来 ， 当 前 子 树 回 来 f [ u ] [ 0 ] + f [ v ] [ 0 ] , 新 派 一 个 棋 子 f[u][0] = min begin{cases}f[u][1] + f[v][0] - dis[u], & 前面的子树回来，当前子树不回来 \ f[u][0] + f[v][1] - dis[u] + 1, & 前面的子树不回来，当前子树回来 \ f[u][0] + f[v][0], & 新派一个棋子end{cases} f[u][0]=min⎩⎪⎨⎪⎧f[u][1]+f[v][0]−dis[u],f[u][0]+f[v][1]−dis[u]+1,f[u][0]+f[v][0],前面的子树回来，当前子树不回来前面的子树不回来，当前子树回来新派一个棋子
- f [ u ] [ 1 ] = d i s [ u ] + ∑ ( f [ v ] [ 1 ] − d i s [ u ] + 1 ) f[u][1] = dis[u] + sum(f[v][1] - dis[u] + 1) f[u][1]=dis[u]+∑(f[v][1]−dis[u]+1)
- 边界：
- f [ u ] [ 0 ] = d i s [ u ] f[u][0] = dis[u] f[u][0]=dis[u]
- f [ u ] [ 1 ] = d i s [ u ] f[u][1] = dis[u] f[u][1]=dis[u]
- 状态转移
- 树型dp
#include #include#include #include using namespace std; using ll = long long; using T = int; T rad(); // quick read const int inf = 0x3f3f3f3f; #define rf(i, n) for (int i = 1; i <= (n); ++i) const int max_size = 5 + 100; const int maxn = 5 + 1e6; int n; vector adj[maxn]; inline void add(int l, int r) { adj[l].push_back(r); } int dis[maxn]; int f[maxn][2]; void dfs(int u, int p) { dis[u] = dis[p] + 1; f[u][0] = dis[u], f[u][1] = dis[u]; for (auto v : adj[u]) { if (v == p) continue; dfs(v, u); f[u][0] = min(min(f[u][1] + f[v][0] - dis[u], f[u][0] + f[v][1] - dis[u] + 1), f[u][0] + f[v][0]); f[u][1] += f[v][1] - dis[u] + 1; } } inline void init() { for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 0; i <= n; ++i) dis[i] = 0; for (int i = 0; i <= n; ++i) f[i][0] = 0, f[i][1] = 0; dis[0] = -1; } #define show(s, t, a) for (int i = s; i <= t; ++i) printf("%d ", a); puts(""); int main() { int Q = rad(); rf(q, Q) { n = rad(); init(); for (int i = 2; i <= n; ++i) { int tmp = rad(); add(i, tmp), add(tmp, i); } dfs(1, 0); // show(1, n, f[i][0]); // show(1, n, f[i][1]); // show(1, n, dis[i]); printf("Case #%d: %dn", q, f[1][0]); } } T rad() { T back = 0; int ch = 0, posi = 0; for (; ch < '0' || ch > '9'; ch = getchar()) posi = ch ^ '-'; for (; ch >= '0' && ch <= '9'; ch = getchar()) back = (back << 1) + (back << 3) + (ch & 0xf); return posi ? back : -back; }
