2020ccpc秦皇岛站

https://codeforces.com/gym/102769?f0a28=1

A

• 题意：
  • 给你 r 个红球，b 个蓝球，
  • 求选择 2 个红球的概率
• 题解：
  • 组合数 gcd

#include <algorithm>
#include <cstring>
#include <iostream>
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;
}

B

• 题意：

  • 有一个地图，地图的点有好坏之分
  • 矩形边界不能有坏点
  • 两种操作：
    • 改变地图某点的状态
    • 求经过某点的最大矩形

• 题解（可能，我也没过，看不到数据的模拟题就是毒瘤）：

  • 修改：维护 $l[i][j],r[i][j],u[i][j]$，分别表示点 $(i,j)$ 左边，右边，上面第一个坏点的横/纵坐标。
    • 更改所在行列即可
  • 查询点 $(x,y)$：考虑点在最优矩形下边界的情况：
    • 倒序枚举顶边 $i\in [1,x-1]$
    • 这一行的某些列可能是坏点，导致这一列不能作为边框的边界，移动后对相关列打标记。
      • 直接寻找底的每一列第一个出现坏点的行，当 i 移动过这行的时候，就把这些列标记。
    • 寻找最大的左右边界 $nl,nr$
      • 问题转化：寻找区间内，第一个不为 1 的点
      • 路径压缩并查集维护
    • $s=\max (s,(r-l+1)\ast (x-j+1))$
  • 不在最优矩形下边界的情况，对称地考虑即可

列标记的过程可以用并查集维护，因为是一段连续的区间，维护这段连续的、不能选的列的左右端点即可。

这里给出一个测试样例，以供参考：

1
5 11 100
#.#######.#
##.#####.##
###.###.###
####.#.####
###########
2 4 6
2 5 6
1 2 3
1 2 9
2 5 6

E

• 题意：
  • 每个人的成绩有两种可能
  • 及格线为最高成绩的 m%
  • 求最多多少人及格
• 题解：
  • 双指针
    • 从小到大枚举区间右端点
    • 维护区间内的人数
  • treap
  • 树状数组

#include <algorithm>
#include <cstring>
#include <iostream>
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;
}

F

• 题意：
  • 无向图，选择一些点，
  • 每个点将使 “计数值” 减 1，每条边将使 “计数值” 加 1
  • 求最大 “计数值”
• 题解：
  • 贪心 连通块
    • 对于一个连通块，多选择一个点不会使解变差（因为至少多了一条边）
    • 所以总是选择完整的连通块
    • 累加正贡献的连通块的 “计数值”

#include <algorithm>
#include <cstring>
#include <iostream>
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;
}

/*
1
6 5
1 2
1 3
4 5
4 6
5 6

*/

G

• 题意：
  • x 是 good number，指 $\lfloor \sqrt[k]{x}\rfloor$ 整除 $x$
  • 求 [0, n] 之间 good number 的数量
• 题解：
  • 分块
    • 设 $i=\lfloor \sqrt[k]{x}\rfloor$
    • $\because \lfloor \sqrt[k]{x}\rfloor |x$
    • $\therefore x\in [i^k,(i+1{)}^k)$
    • 枚举 $i,i^k\in [0,n]$
      • 对 $\forall j\in [i^k,(i+1{)}^k),i|j$ 计数
        • 等差数列在区间中的通项数量
    • 注意特判 $k>31$，
      • 溢出了
      • 而且显然此时 $[1,2^k)$ 覆盖所有 $x$

#include <algorithm>
#include <cstring>
#include <iostream>
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;
}

I

• 题意：

  • 研究二维向量，有两种操作，
    • 获得一个向量
    • 查询某向量是否是已知向量的线性组合
  • 每次查询成立，我们都能获得一个权值 w
  • 问 q 次操作后，最终权值是多少

• 题解：

  • 辗转相除法 向量分解
    • 已有 0 个向量时，一定不成立
    • 已有 1 个向量时，判断是否共线
    • 已有 2 个向量时，
      • 设其分别为 $\vec{a},\vec{b}$，
      • 使用向量的辗转相除法，获得同基底的另一组向量 ${\vec{a}}_0,{\vec{b}}_0$，其中：
        • ${\vec{a}}_0$ 的第一个分量为 0，
        • ${\vec{b}}_0$ 的第二个分量小于 ${\vec{a}}_0$ 的第二个分量（辗转相除法后直接取模）。
        • 本质上是第一个分量的辗转相除法，只不过所有四则运算作用于所有分量，从而线性得到保证。
      • 于是，对于方程 $\vec{x}=k_1{\vec{a}}_0+k_2{\vec{b}}_0$ 中，$k_2$ 已知，判断 $k_1$ 是否存在即可（$\because$ 只有 ${\vec{b}}_0$ 对第一个分量有贡献）。
    • 已有多个向量时，
      • 对于新向量 $\vec{c}$ 与 ${\vec{b}}_0$，作辗转相除法，消去 $\vec{c}$ 的第一个分量
      • 显然，${\vec{a}}_0$ 和 $\vec{c}$ 的自由组合是 ${\vec{a}}_g$ 的倍数，${\vec{a}}_g$ 的第一个分量是前两者的最大公因数。
      • 更新 ${\vec{b}}_0$ 的第二个分量
      • 此时，问题回到向量数量为 2 的情况

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
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<Node> 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;
}

/*
1000 1 2 2 3


1
100
1 2 3
1 4 0
1 3 3
1 0 4

2
4
1 1 1
2 3 1 1
1 1 3
2 3 1 2
3
1 1 1
1 2 1
2 3 2 3


1
3
1 1 1
1 2 1
2 3 2 3


*/

K

• 题意：
  • 有根树的树根有无数个棋子
  • 你可以使一个棋子移动一步
  • 求走完所有顶点的最少步数
• 题解：
  • 树型dp
    • 状态转移
      • $f[i][1/0]$：从根开始，到遍历完子树 i 为止，是否回到 i 的路径长
      • $dis[u]$：从根到 u 的距离
      • $f[u][0]=\min \{\begin{array}{ll}f[u][1]+f[v][0]-dis[u],& 前面的子树回来，当前子树不回来\\ f[u][0]+f[v][1]-dis[u]+1,& 前面的子树不回来，当前子树回来\\ f[u][0]+f[v][0],& 新派一个棋子\end{array}$
      • $f[u][1]=dis[u]+\sum (f[v][1]-dis[u]+1)$
    • 边界：
      • $f[u][0]=dis[u]$
      • $f[u][1]=dis[u]$

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
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<int> 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;
}

/*
1
10
1 1 3 3 5 5 7 8 6

1 
4
1 1 2
*/

最后

以上就是魔幻火车为你收集整理的2020ccpc秦皇岛站部分题解2020ccpc秦皇岛站的全部内容，希望文章能够帮你解决2020ccpc秦皇岛站部分题解2020ccpc秦皇岛站所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。