比赛题目在 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;
}