2020ccpc秦皇岛站部分题解

2020ccpc秦皇岛站

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

---

A

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

#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 + 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/%d\n", 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 ] 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))
  • 不在最优矩形下边界的情况，对称地考虑即可

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

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

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

E

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

#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 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: %lld\n", 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 
#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 + 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: %d\n", 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，指 ⌊ 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 计数
        • 等差数列在区间中的通项数量
    • 注意特判 k > 31 k > 31 k>31，
      • 溢出了
      • 而且显然此时 [ 1 , 2 k ) [1, 2^k) [1,2k) 覆盖所有 x x x

#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 + 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: %d\n", 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 个向量时，
      • 设其分别为 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 =k1​a 0​+k2​b 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 
#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 + 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 %d\n", 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: %lld\n", 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 ] 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]

#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<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: %d\n", 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
*/