ZPCPC 2020 题解

比赛题目在 Gym 的地址:The 17th Zhejiang Provincial Collegiate Programming Contest

和两个高一小神仙组队(听说他们是第一次打 ACM?),没想到合作默契融洽,最后打了个 rank 18,可以说是非常快乐啦!

最下面那支队就是我们了 qaq

第一次打这么正式的 ACM,前后两个摄像机位有点不习惯,再加上比赛开始后的一个小时都没有拿到纸质题面,最初一段时间的过题速度很慢。

喜提 $8$ 题队中最高罚时

A. AD 2020

每个日期都用 YYYYMMDD表示,该字符串中含有 202 的日期是「好的」。$T$ 次询问,每次求出两个日期 $Y_{1},M_{1},D_{1}$ 和 $Y_{2},M_{2},D_{2}$ 之间有多少个日子是「好的」。

数据范围:$1 \le T \le 10 ^ {5}$。

Solution

预处理前缀和即可。

时间复杂度:$\mathcal O(10 ^ {4} \cdot 12 \cdot 31 +T)$。

Code


B. Bin Packing Problem

C. Crossword Validation

D. Dividing the Points

E. Easy DP Problem

对于一个长度为 $m$ 的数列 $b_{i}$,有 $(m + 1) \times (m + 1)$ 个状态 $dp[i][j]$,其转移如下:

$$ dp[i][j] = \begin{cases} 0 & i = 0 \\ i ^ {2} + dp[i - 1][j] & i > 0, j = 0 \\ i ^ {2} + \max(dp[i - 1][j], dp[i - 1][j - 1] + b_{i}) & i > 0, j > 0 \end{cases} $$

现在有一个长度为 $n$ 的数列 $a_{i}$,有 $q$ 次询问,每次询问给定 $l, r, k$ 表示令 $m = r - l + 1$ 且 $b_{1 \ldots m} = a_{l \ldots r}$,求出此时 $dp[m][k]$ 的值。

数据范围:$1 \le n, q \le 10 ^ {5}$,$1 \le a_{i} \le 10 ^ {6}$,$1 \le k \le r - l + 1$。

Solution

题目等价于:从 $(0, 0)$ 开始移动,往下走一格答案加上 $i ^ 2$;往右下走一格加上 $i ^ 2 + b_{i}$。我们要最大化最终 $(m, k)$ 处的答案。

所以最终的答案就是 $\sum_{i = 1} ^ {m} i ^ 2 + (b_{i}\ \text{中前 }k\text{ 大的数之和})$。

直接离散化后用主席树维护即可。

时间复杂度:$\mathcal O((n + q) \log n)$。


F. Finding a Sample


G. Gliding


H. Huge Clouds

在平面直角坐标系中,$x$ 轴上方有 $n$ 颗星星 $(x_{i}, y_{i})$ 和 $m$ 朵云 $(u_{i1}, v_{i1}) - (u_{i2}, v_{i2})$。$x$ 轴上的某一点 $(x, 0)$ 是阴影当且仅当这个点看不到任何一颗星星。在点 $P$ 能看到星星 $i$ 当且仅当点 $P$ 和 $(x_{i}, y_{i})$ 的连线不经过任何一朵云(包括端点)。特殊地,如果一颗星星被一朵云穿过,那么它永远无法被看到。

求出 $x$ 轴上的阴影长度。如果答案大于 $10 ^ {9}$,输出 -1。答案的绝对或相对误差不超过 $10 ^ {-4}$。

数据范围:$1 \le n, m \le 500$,$-10 ^ {4} \le x_{i}, y_{i}, u_{i1}, v_{i1}, u_{i2}, v_{i2} \le 10 ^ {4}$。

Solution

计算几何大力分类讨论。

对于每颗星星,求出其形成的阴影区间集合(和每朵云形成阴影的交),最后求出被覆盖 $n$ 次的区间长度。

时间复杂度:$\mathcal O(nm \log nm)$。

Code

#include <bits/stdc++.h>
typedef long long int64;

const int N = 5e2;
const double EPS = 1e-6, INF = 1e20;
int n, m;
std::vector<std::pair<double, int>> opt;
struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    inline Point operator-(const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
    inline int operator^(const Point &rhs) const {
        return x * rhs.y - rhs.x * y;
    }
} s[N + 5];
struct Line {
    Point a, b;
} c[N + 5];


inline bool isIn(const Point &p, const Point &a, const Point &b) {
    return ((a - p) ^ (b - p)) == 0;
}
inline bool isInSeg(const Point &p, const Point &a, const Point &b) {
    return isIn(p, a, b) && p.x >= std::min(a.x, b.x) && p.x <= std::max(a.x, b.x) && p.y >= std::min(a.y, b.y) && p.y <= std::max(a.y, b.y);
}
inline bool invalid(const Point &p, const Point &a, const Point &b) {
    return p.y <= std::min(a.y, b.y);
}
inline double calc(const Point &p, const Point &a) {
    return p.x + 1.0 * (a.x - p.x) / (p.y - a.y) * p.y;
}
inline void solve(const Point &p) {
    std::vector<std::pair<double, double>> vec;
    for (int i = 1; i <= m; i++) {
        Point a = c[i].a, b = c[i].b;
        if (isInSeg(p, a, b)) {
            vec.clear();
            vec.emplace_back(-INF, INF);
            break;
        } else if (isIn(p, a, b) || p.y <= std::min(a.y, b.y)) {
            continue;
        } else if (p.y >= std::max(a.y, b.y)) {
            double s = calc(p, a), t = calc(p, b);
            if (s > t) {
                std::swap(s, t);
            }
            vec.emplace_back(s, t);
        } else {
            if (a.y > b.y) {
                std::swap(a, b);
            }
            ((a - p) ^ (b - p)) < 0 ? vec.emplace_back(-INF, calc(p, a)) : vec.emplace_back(calc(p, a), INF);
        }
    }
    std::sort(vec.begin(), vec.end());
    int tot = vec.size();
    for (int i = 0; i < tot; ) {
        int j = i;
        double r = vec[i].second;
        for (; j + 1 < tot && vec[j + 1].first <= r; ) {
            r = std::max(r, vec[j + 1].second);
            j++;
        }
        opt.emplace_back(vec[i].first, 1);
        opt.emplace_back(r, -1);
        i = j + 1;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &s[i].x, &s[i].y);
        }
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d%d", &c[i].a.x, &c[i].a.y, &c[i].b.x, &c[i].b.y);
            if (c[i].a.x > c[i].b.x) {
                std::swap(c[i].a, c[i].b);
            }
        }
        opt.clear();
        for (int i = 1; i <= n; i++) {
            solve(s[i]);
        }
        std::sort(opt.begin(), opt.end());
        double ans = 0;
        for (int cnt = 0, i = 0; i < (int)opt.size(); i++) {
            if ((cnt += opt[i].second) == n) {
                ans += opt[i + 1].first - opt[i].first;
            }
        }
        if (ans > 1e9) {
            printf("-1\n");
        } else {
            printf("%.12lf\n", ans);
        }
    }
    return 0;
}

I. Invoking the Magic


J. Just an Old Problem


K. Killing the Brute-force


L. List of Products

发表评论