Skip to content

第六届 CCPC 秦皇岛

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J K L
5/12 O - O - O O O - - - - -
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

Problem A. A Greeting from Qinhuangdao

Solved By Dup4. 9(+)

题意

给出 r 和红球，b 个蓝球，问取两个球，都是红球的概率是多少？

思路

\displaystyle \frac{r}{r + b} \cdot \frac{r - 1}{r + b - 1}

Code 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int _T;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        printf("Case #%d: ", i);
        int r, b;
        scanf("%d%d", &r, &b);
        if (r < 2)
            puts("0/1");
        else {
            int A = r * (r - 1);
            int B = (r + b) * (r + b - 1);
            int _g = __gcd(A, B);
            A /= _g;
            B /= _g;
            printf("%d/%d\n", A, B);
        }
    }
    return 0;
}

Problem B. Bounding Wall

Upsolved By -.

题意

思路

Problem C. Cameraman

Solved By Dup4 & groggy_. -

题意

  • 给出一个矩形，左下角是 (0, 0), 右上角是 (w, h), 并且给出一个点 (x, y)(1 \leq x \leq w - 1, 1 \leq y \leq h - 1)。
  • 在矩形内部有 n 个点，现在要找个点射出去两条线，使得射线以及矩形围成的闭合区域只有 (x, y) 这个点。
  • 现在要求两条射线与矩形围成的闭合区域中，矩形那部分的变长和最长。

思路

  • 大力猜测要找的那个点就可以是 (x, y)。
  • 然后从 (x, y) 向其它点连射线，交矩形一个点。
  • 对求出的点做直角排序。
    • 我们直接直角排序发现过不了。
    • 后来考虑每个点肯定在矩形的四条边上，那么我们对这四条边的上的点分别排序，最后找个方向合并起来。
  • 然后计算相邻两点之间围成的变长和。
    • 这里其实情况有很多种，但是如果加入矩形的四个角作为虚点。
    • 那么相邻亮点肯定在矩形的一条边上，这个时候求距离很简单。
    • 那么就转化成了两个实点之间相邻两点的边长和。
Code 
#include <bits/stdc++.h>
using namespace std;
using db = long double;
#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)
void err() {
    cout << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}

const db eps = 1e-6;
int sgn(db x) {
    if (fabs(x) < eps)
        return 0;
    return x < 0 ? -1 : 1;
}
const int N = 1e5 + 10;
int w, h, n;

struct Point {
    db x, y;
    int vis, tp;
    Point(db x = 0, db y = 0, int vis = 1) : x(x), y(y), vis(vis) {}
    void scan() {
        scanf("%Lf%Lf", &x, &y);
    }
    Point operator-(const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
    bool operator<(const Point &b) const {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
    }
    db operator^(const Point &b) const {
        return x * b.y - y * b.x;
    }
    db dis(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    db dis2(Point b) {
        return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
    }
} p;

struct Line {
    Point s, e;
    Line() {}
    Line(Point s, Point e) : s(s), e(e) {}
};

struct Polygon {
    vector<Point> p;
    Polygon() {
        p.clear();
    }
    Polygon(int n) {
        p.clear();
        p.resize(n);
    }
    void add(Point x) {
        p.push_back(x);
    }
    int sze() {
        return p.size();
    }
    Point &operator[](int x) {
        return p[(x + sze()) % sze()];
    }
    struct cmpNorm {
        Point p;
        cmpNorm(Point p) : p(p) {}
        bool operator()(Point a, Point b) {
            int d = sgn((a - p) ^ (b - p));
            if (d == 0) {
                return sgn(a.dis2(p) - b.dis2(p)) < 0;
            } else {
                return d > 0;
            }
        }
    };
    void norm() {
        Point mi = *p.begin();
        for (int i = 1; i < sze(); ++i) mi = min(mi, p[i]);
        sort(p.begin(), p.end(), cmpNorm(mi));
    }
    void norm(Point mi) {
        sort(p.begin(), p.end(), cmpNorm(mi));
    }
    //	int pointInConvex(Point q) {
    //		int l = 1, r = sze() - 2;
    //		while (r - l >= 0) {
    //			int mid = (l + r) >> 1;
    //			int a1 = sgn((p[mid] - p[0]))
    //		}
    //	}
} po, _po;

db dis(Point a) {
    return (p.x - a.x) * (p.x - a.x) + (p.y - a.y) * (p.y - a.y);
}

Point getPoint(Point a) {
    db dis_x = fabs(a.x - p.x);
    db dis_y = fabs(a.y - p.y);
    //	cout<<dis_x<<' '<<dis_y<<endl;
    if (a.x == p.x && a.y > p.y)
        return Point(p.x, h);
    else if (a.y == p.y && a.x > p.x)
        return Point(w, p.y);
    else if (a.x == p.x && a.y < p.y)
        return Point(p.x, 0);
    else if (a.y == p.y && a.x < p.x)
        return Point(0, p.y);
    else if (a.x > p.x && a.y > p.y) {
        Point new1_a;
        new1_a.x = w;
        new1_a.y = p.y + (w - p.x) * dis_y / dis_x;
        Point new2_a;
        new2_a.x = p.x + (h - p.y) * dis_x / dis_y;
        new2_a.y = h;
        //		cout<<dis(new1_a)<<' '<<dis(new2_a)<<endl;
        //		cout<<new1_a.x<<' '<<new1_a.y<<endl;
        //		cout<<new2_a.x<<' '<<new2_a.y<<endl;
        if (sgn(dis(new1_a) - dis(new2_a)) <= 0)
            return new1_a;
        else
            return new2_a;
    } else if (a.x > p.x && a.y < p.y) {
        Point new1_a;
        new1_a.x = w;
        new1_a.y = p.y - (w - p.x) * dis_y / dis_x;
        Point new2_a;
        new2_a.x = p.x + p.y * dis_x / dis_y;
        new2_a.y = 0;
        if (sgn(dis(new1_a) - dis(new2_a)) <= 0)
            return new1_a;
        else
            return new2_a;
    } else if (a.x < p.x && a.y > p.y) {
        Point new1_a;
        new1_a.x = 0;
        new1_a.y = p.y + p.x * dis_y / dis_x;
        Point new2_a;
        new2_a.x = p.x - (h - p.y) * dis_x / dis_y;
        new2_a.y = h;
        if (sgn(dis(new1_a) - dis(new2_a)) <= 0)
            return new1_a;
        else
            return new2_a;
    } else if (a.x < p.x && a.y < p.y) {
        Point new1_a;
        new1_a.x = 0;
        new1_a.y = p.y - p.x * dis_y / dis_x;
        Point new2_a;
        new2_a.x = p.x - p.y * dis_x / dis_y;
        new2_a.y = 0;
        if (sgn(dis(new1_a) - dis(new2_a)) <= 0)
            return new1_a;
        else
            return new2_a;
    }
    return Point(0, 0);
}

db calc(Point a, Point b) {
    if (sgn(a.x - b.x) == 0 || sgn(a.y - b.y) == 0) {
        return max(fabs(a.x - b.x), fabs(a.y - b.y));
    } else {
        assert(0);
    }
    return 0;
}

int main() {
    int _T;
    scanf("%d", &_T);
    for (int CAS = 1; CAS <= _T; ++CAS) {
        printf("Case #%d: ", CAS);
        scanf("%d%d", &w, &h);
        p.scan();
        scanf("%d", &n);
        po = Polygon(n);
        for (int i = 0; i < n; ++i) {
            po[i - 1].scan();
        }
        po.norm(p);
        _po = Polygon(n + 4);
        //		dbg(n);
        for (int i = 0; i < n; ++i) {
            _po[i] = getPoint(po[i]);
            //			dbg(_po[i].x, _po[i].y);
            _po[i].vis = 1;
        }
        _po[n] = Point(0, 0, 0);
        _po[n + 1] = Point(w, 0, 0);
        _po[n + 2] = Point(w, h, 0);
        _po[n + 3] = Point(0, h, 0);
        for (int i = 0; i < n + 4; ++i) {
            if (sgn(_po[i].y) == 0)
                _po[i].tp = 1;
            else if (sgn(_po[i].x - w) == 0)
                _po[i].tp = 2;
            else if (sgn(_po[i].y - h) == 0)
                _po[i].tp = 3;
            else if (sgn(_po[i].x) == 0)
                _po[i].tp = 4;
        }
        sort(_po.p.begin(), _po.p.end(), [&](Point a, Point b) {
            if (a.tp != b.tp)
                return a.tp < b.tp;
            if (a.tp == 1)
                return sgn(a.x - b.x) <= 0;
            else if (a.tp == 2)
                return sgn(a.y - b.y) <= 0;
            else if (a.tp == 3)
                return sgn(a.x - b.x) >= 0;
            else if (a.tp == 4)
                return sgn(a.y - b.y) >= 0;
        });
        //		for (int i = 1; i <= n + 4; ++i) {
        //			dbg(i, _po[i].x, _po[i].y);
        //		}
        db res = 0;
        for (int i = 1; i <= n + 100; ++i) {
            int _j = i - 1;
            for (int j = i - 1;; --j) {
                if (_po[j].vis == 1) {
                    _j = j;
                    break;
                }
            }
            db now = 0;
            for (int j = i - 1; j >= _j; --j) {
                now += calc(_po[j], _po[j + 1]);
            }
            res = max(res, now);
        }
        printf("%.10Lf\n", res);
    }
    return 0;
}

Problem D. Defend City

Upsolved By -.

题意

思路

Problem E. Exam Results

Solved By Dup4 & ltslts. 76(+1)

题意

  • 给出 n 个人和一个概率参数 p。
  • 对于每个人，在一场考试中，如果他发挥的好，他会得到 a_i 的分数，否则得到 b_i 的分数。
  • 在一场考试中，假定最高分数为 x，那么只要一个人得到的分数大于等于 x \cdot p\%，那么他就能通过这场考试。
  • 问所有 2^n 的情况中，最多能有多少人通过考试。

思路

  • 将所有分数排序。
  • 然后从大到小枚举 x，然后维护两个指针。
    • 一个是要所有大于 x 的分数都不能要。
    • 一个是所有小于 x \cdot p\% 的分数都不能加入。
      • 但是考虑 x 是递减的，所以下界是逐渐减小，所以是慢慢加入很多可以的点。
    • 所以每个分数只会被加入一次，剔除一次。
  • 要注意的是，如果一个人两个分数都因为大于 x 而被剔除掉，是不合法的情况。
Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pII = pair<int, int>;
#define fi first
#define se second
#define SZ(x) (int(x.size()))
const int N = 2e5 + 10;
int n, p;
int a[N], b[N];
int f[N];

void gao() {
    for (int i = 1; i <= n; ++i) f[i] = 0;
    vector<pII> vec;
    for (int i = 1; i <= n; ++i) {
        vec.push_back(pII(a[i], i));
        vec.push_back(pII(b[i], i));
    }
    sort(vec.begin(), vec.end());
    int res = 0, now = 0;
    int r = SZ(vec) - 1, l = SZ(vec) - 1;
    int m = SZ(vec) - 1;
    int MaxScore = 0;
    for (int i = 1; i <= n; ++i) {
        MaxScore = max(MaxScore, min({a[i], b[i]}));
    }
    for (int i = m; i >= 0; --i) {
        int Max = vec[i].fi;
        if (Max < MaxScore)
            break;
        ll pMax = 1ll * p * Max;
        while (l >= 0 && 1ll * vec[l].fi * 100 >= pMax) {
            int id = vec[l].se;
            ++f[id];
            if (f[id] == 1)
                ++now;
            --l;
        }
        while (r >= 0 && vec[r].fi > Max) {
            int id = vec[r].se;
            --f[id];
            if (f[id] == 0)
                --now;
            --r;
        }
        res = max(res, now);
    }
    printf("%d\n", res);
}

int main() {
    int _T;
    scanf("%d", &_T);
    for (int CAS = 1; CAS <= _T; ++CAS) {
        printf("Case #%d: ", CAS);
        scanf("%d%d", &n, &p);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", a + i, b + i);
        }
        gao();
    }
    return 0;
}

Problem F. Friendly Group

Solved By Dup4 & ltslts. 44(+)

题意

给出 n 个点和 m 条边。

现在要给出一个子图，定义价值为：

V = \mbox{连接这个子图中两点的边的数量} - \mbox{点数} - \mbox{其中一个点在子图中，另一个点在子图外的边的数量} 连接这个子图中两点的边的数量点数其中一个点在子图中，另一个点在子图外的边的数量

问如何选子图，使得价值最大？

思路

  • 贪心，选择正收益的每一个连通块。
Code 
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int(x.size()))

const int N = 3e5 + 10;
int n, m;
vector<vector<int>> G, T;

struct UFS {
    int fa[N], sze[N];
    void init(int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = 0;
            sze[i] = 1;
        }
    }
    int find(int u) {
        return fa[u] ? fa[u] = find(fa[u]) : u;
    }
    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            if (sze[fu] > sze[fv]) {
                swap(fu, fv);
            }
            fa[fv] = fu;
            sze[fu] += sze[fv];
        }
    }
} ufs;

int main() {
    int _T;
    scanf("%d", &_T);
    for (int CAS = 1; CAS <= _T; ++CAS) {
        printf("Case #%d: ", CAS);
        scanf("%d%d", &n, &m);
        G.clear();
        G.resize(n + 1);
        ufs.init(n);
        for (int i = 1, u, v; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            ufs.merge(u, v);
        }
        T.clear();
        T.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            T[ufs.find(i)].push_back(i);
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            if (!T[i].empty()) {
                int E = 0, V = SZ(T[i]);
                for (auto &it : T[i]) {
                    E += SZ(G[it]);
                }
                E /= 2;
                if (E - V > 0)
                    res += E - V;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

Problem G. Good Number

Solved By Dup4. 34(+)

题意

  • 给出 n 和 k。
  • 统计 [1, n] 中有多少个 x 满足 \displaystyle \lfloor \sqrt[k]{x} \rfloor \;\;|\;\; x。

思路

  • k = 1 的时候特判。
  • 考虑 \lfloor \sqrt[k]{x} \rfloor 的种类只有 \lfloor \sqrt[k]{n} \rfloor 种。
  • 那么对于 i，它掌管的范围是 [i^k, (i + 1)^k), 直接统计这个范围内有多少个 i 的倍数即可。
Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;

ll calc(int x) {
    ll res = 1;
    for (int i = 1; i <= k; ++i) {
        res *= x;
        if (res > n)
            return n + 1;
    }
    return res;
}

ll gao(ll x, ll y) {
    return y / x;
}

int main() {
    int _T;
    scanf("%d", &_T);
    for (int CAS = 1; CAS <= _T; ++CAS) {
        printf("Case #%d: ", CAS);
        scanf("%d%d", &n, &k);
        if (k == 1) {
            printf("%d\n", n);
        } else {
            int limit = ceil(pow(n, 1.0 / k)) + 10;
            limit = min(limit, n);
            ll res = 0;
            for (int i = 1; i <= limit; ++i) {
                ll l = calc(i);
                ll r = calc(i + 1);
                if (l < r) {
                    res += gao(i, r - 1) - gao(i, l - 1);
                }
            }
            printf("%lld\n", res);
        }
    }
    return 0;
}

Problem H. Holy Sequence

Upsolved By -.

题意

思路

Problem I. Interstellar Hunter

Upsolved By -.

题意

思路

Problem J. Jewel Splitting

Upsolved By -.

题意

思路

Problem K. Kingdom’s Power

Upsolved By -.

题意

  • 给出 n 个点的有根树，根为 1。
  • 在根结点，有无限个士兵。
  • 每次可以调配一个士兵，向它相邻的点走一步。
  • 问所有点都至少被一个士兵访问过的最小次数。

思路

Problem L. Lost Temple

Upsolved By -.

题意

思路

Last update: March 24, 2022
Created: March 23, 2022
Back to top