【GZOI 2019】特技飞行

清疚 2023-08-17 15:48 87阅读 0赞

# Problem #

## Description ##

公元 \\(9012\\) 年，Z 市的航空基地计划举行一场特技飞行表演。表演的场地可以看作一个二维平面直角坐标系，其中横坐标代表着水平位置，纵坐标代表着飞行高度。

在最初的计划中，这 \\(n\\) 架飞机首先会飞行到起点 \\(x = x\_\{st\}\\) 处，其中第 \\(i\\) 架飞机在起点处的高度为 \\(y\_\{i,0\}\\)。它们的目标是终点 \\(x = x\_\{ed\}\\) 处，其中第 \\(i\\) 架飞机在终点处的高度应为 \\(y\_\{i,1\}\\)。因此，每架飞机可以看作坐标系中的一个点，它的航线是从 \\((x\_\{st\},y\_\{i,0\})\\) 出发、到 \\((x\_\{ed\},y\_\{i,1\})\\) 结束的一条线段，如下图所示。

![5cb2a2d6a8dc9.png][]

这 \\(n\\) 架飞机同时出发且始终保持一定的对地速度。因此，对于任意两条交叉的航线（线段），对应的两架飞机必然会同时到达交点处——这就是它们进行特技表演的时刻。它们将会偏转机翼，展现以极近的距离「擦身而过」特技，然后**继续保持各自的航线**。

航空基地最近还研究了一种新的特技「对向交换」。当两架飞机到达交点处时，之前正在下降的那架立即转为执行抬升动作，之前正在上升的那架则执行一次空翻，两架飞机一上一下、机腹对机腹，同样以极近的距离经过交点，然后**互相交换接下来的航线**。

我们不必关心特技动作在物理上究竟是如何实现的，飞机仍然看作一个点，在两种特技动作下，航线的变化如下图所示（\\(y\_\{i,1\}'\\) 表示交换航线后第 \\(i\\) 架飞机在终点的新高度）。容易发现，「对向交换」会使它们的航线变为折线，并**保持它们在纵坐标上的相对顺序**；而「擦身而过」会**改变它们在纵坐标上的相对顺序**。

![5cb2a389b6bb8.png][]

现在，观看表演的嘉宾团提出了一个苛刻的要求——在终点 \\(x = x\_\{ed\}\\) 处，按照高度排序，\\(n\\) 架飞机的相对顺序必须与 \\(x = x\_\{st\}\\) 处的相对顺序一致。嘉宾团还给「对向交换」特技和「擦身而过」特技分别评定了难度系数 \\(a\\) 和 \\(b\\)，每次「对向交换」特技可以获得 \\(a\\) 的分数，每次「擦身而过」特技可以获得 \\(b\\) 的分数。

除此以外，嘉宾团共有 \\(k\\) 名成员，第 \\(i\\) 名成员会乘热气球停留在位置 \\((p\_i,q\_i)\\) 处，具有 \\(r\_i\\) 的观测距离，可以观测到区域 \\(|x - p\_i| + |y - q\_i| \\le r\_i\\) 里的所有特技。  
若某个交点处的特技被**一名或多名**嘉宾观测到，则可以获得 \\(c\\) 的额外加分。

注意：**特技无论是否被观测到，均可以获得 \\(a\\) 或者 \\(b\\) 的得分**。

下图是对本题第一幅图 \\(4\\) 条航线 \\(4\\) 个交点的一种满足要求的安排，包括 \\(2\\) 次「对向交换」、\\(2\\) 次「擦身而过」，\\(3\\) 项特技被观测到，得分 \\(2a + 2b + 3c\\)。为了方便观察，图中展现「对向交换」特技的交点稍稍有些分离。

![5cb2a5b2c7b4c.png][]

在这次的剧情里，你成为了 Z 市航空基地的规划员，你可以决定在每个交点处是执行「对向交换」还是「擦身而过」。你被要求在保证嘉宾团要求的前提下，计算整个特技表演的可能得到的最低和最高分数。

## Input Format ##

第一行包含六个非负整数 \\(n,a,b,c,x\_\{st\},x\_\{ed\}\\)，分别表示航线（线段）总数、「对向交换」特技的得分、「擦身而过」特技的得分、观测对表演的额外分、飞行起点的横坐标、飞行终点的横坐标。

第二行包含 \\(n\\) 个非负整数 \\(y\_\{i,0\}\\)，其中第 \\(i\\) 个数表示第 \\(i\\) 条航线起点的纵坐标，保证按照从低到高的顺序给出，即 \\(y\_\{i,0\} < y\_\{i + 1,0\}\\)。

第三行包含 \\(n\\) 个非负整数 \\(y\_\{i,1\}\\)，其中第 \\(i\\) 个数表示第 \\(i\\) 条航线终点的纵坐标。

第四行包含一个非负整数 \\(k\\)，表示嘉宾的数量。

接下来 \\(k\\) 行每行三个非负整数 \\(p\_i,q\_i,r\_i\\)，分别表示第 \\(i\\) 名嘉宾所在位置的横、纵坐标与观测距离。

输入数据对于所有航线（线段）在直线 \\(x = x\_\{st\}\\) 和 \\(x = x\_\{ed\}\\) 之间的交点总数也有一些限制，详见「数据范围与提示」。

## Output Format ##

输出只有一行，包含两个整数，表示整个特技飞行表演的可能得到的最低和最高分数，中间用一个空格隔开。

## Sample ##

### Input 1 ###

4 1 2 3 1 6 1 2 3 4 4 1 3 2 2 3 3 1 5 2 2

### Output 1 ###

13 15

### Input 2 ###

10 73 28 13 0 100 2 9 16 25 29 34 43 46 52 58 8 25 35 52 41 5 16 3 19 48 5 46 40 1 37 27 5 67 34 1 65 28 4 29 38 1

### Output 2 ###

989 1619

## Explainatioin for Input 1 ##

该样例的航线就是题目描述的图中所画的情况，只是嘉宾所在的位置稍有不同。

最低得分的表演方案是在所有交点处均采用「对向交换」特技，得分 \\(4a + 3c = 13\\)。

最高得分的表演方案与题目描述的图中所画的情况一致，得分 \\(2a + 2b + 3c = 15\\)。

## Range ##

不存在三条或三条以上的线段交于同一点。

所有坐标和 \\(r\_i\\) 均为 \\(5 \\times 10^7\\) 以内的非负整数。

\\(y\_\{i,0\} < y\_\{i + 1,0\}\\)，\\(y\_\{i,1\}\\) 各不相同。

\\(x\_\{st\} < p\_i < x\_\{ed\},1 ≤ a,b,c ≤ 10^3\\)。

<table> 
 <thead> 
 <tr> 
 <th style="text-align:center;">测试点编号</th> 
 <th style="text-align:center;">\(n,k\) 的规模</th> 
 <th style="text-align:center;">交点数的规模</th> 
 <th style="text-align:center;">约定</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">\(1\)</td> 
 <td style="text-align:center;">\(n,k \le 15\)</td> 
 <td style="text-align:center;">\(\le 40\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(2\)</td> 
 <td style="text-align:center;">\(n,k \le 15\)</td> 
 <td style="text-align:center;">\(\le 40\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(3\)</td> 
 <td style="text-align:center;">\(n,k \le 15\)</td> 
 <td style="text-align:center;">\(\le 40\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(4\)</td> 
 <td style="text-align:center;">\(n,k \le 15\)</td> 
 <td style="text-align:center;">\(\le 40\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(5\)</td> 
 <td style="text-align:center;">\(n \le 30.000,k \le 100\)</td> 
 <td style="text-align:center;">\(\le 200,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(6\)</td> 
 <td style="text-align:center;">\(n \le 30.000,k \le 100\)</td> 
 <td style="text-align:center;">\(\le 200,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(7\)</td> 
 <td style="text-align:center;">\(n \le 30.000,k \le 100\)</td> 
 <td style="text-align:center;">\(\le 200,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(8\)</td> 
 <td style="text-align:center;">\(n \le 30.000,k \le 100\)</td> 
 <td style="text-align:center;">\(\le 200,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(9\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">\(a = b\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(10\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">\(a = b\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(11\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">\(a = b\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(12\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">\(a = b\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(13\)</td> 
 <td style="text-align:center;">\(n,k \le 50,000\)</td> 
 <td style="text-align:center;">\(\le 250,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(14\)</td> 
 <td style="text-align:center;">\(n,k \le 50,000\)</td> 
 <td style="text-align:center;">\(\le 250,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(15\)</td> 
 <td style="text-align:center;">\(n,k \le 50,000\)</td> 
 <td style="text-align:center;">\(\le 250,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(16\)</td> 
 <td style="text-align:center;">\(n,k \le 50,000\)</td> 
 <td style="text-align:center;">\(\le 250,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(17\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(18\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(19\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(20\)</td> 
 <td style="text-align:center;">\(n,k \le 100,000\)</td> 
 <td style="text-align:center;">\(\le 500,000\)</td> 
 <td style="text-align:center;">无</td> 
 </tr> 
 </tbody> 
</table>

# Algorithm #

向量，扫描线

# Mentality #

考场上打的全是麻烦的算法 .jpg 。

\\(step1:\\)

首先发现，由于交点数不多，显然先求交点。对于两条线段，它们相交当且仅当左端点纵坐标的大小关系和右端点相反。

由于题目按照左端点纵坐标单调递增给出，直接用一个 \\(set\\) 维护已给出的右端点纵坐标集合，对于新线段暴力扫一遍 \\(set\\) 中的线段，看是否相交。

求交点其实很简单，利用斜率就好了。

奈何我选择了叉积 \\((???)\\)，我也觉得自己挺迷的。

\\(step2:\\)

对于每个嘉宾，直接将嘉宾和交点坐标转换成切比雪夫意义下的坐标，二维数点即可。

这里使用扫描线二维数点。

\\(step3:\\)

接下来剩下的是翻折操作。

不难发现，由于 \\(a,b\\) 有明确的大小关系，所以两个极端答案肯定是尽量多选 \\(a\\) 和尽量少选 \\(a\\) 。

对于尽量多选 \\(a\\) ，也就是翻折操作，我们发现其实可以所有操作全部翻折，最后到右边之后，一定会是有序的。

这个有两种理解方式：

一、交点数等价于逆序对数，一次翻折就相当于扭回去了一对逆序对，当我们将所有逆序对都扭回去之后，序列不存在逆序对，即结果有序。

二、题面中有提到：一次翻折操作会使两架飞机仍保持相对位置不变。那么我们每次都进行翻折，始终不会有任意两架飞机交换位置，所以最后结果有序。

对于尽量少选 \\(a\\) ，我们将每个飞机 \\(i\\) 和它的目的地 \\(p\_i\\) 相连，就会得到一张只存在简单环的图。

不难发现，对于一个环，设其中元素分别为 \\(a\_1\\sim a\_n\\) 它的形式如下：

\\(\\forall\_\{i=1\}^\{n-1\}p\_\{a\_i\}=a\_\{i+1\}\\)

\\(p\_\{a\_n\}=a\_1\\)

由于交换元素仅针对逆序对，所以要将环整体位移一位最少也就需要环长减一的次数。

所以 \\(a\\) 的最少选择次数为所有环的环长减一之和。

没了。

# Code #

考场的时候脑子比较乱，代码也就打得长了。我也不知道我为什么码出了 \\(5k\\)

#include <algorithm> #include <cmath> #include <cstdio> #include <iostream> #include <set> using namespace std; #define LL long long #define go(x, i, v) for (int i = hd[x], v = to[i]; i; v = to[i = nx[i]]) #define inline __inline__ __attribute__((always_inline)) inline LL read() { LL x = 0, w = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); } while (isdigit(ch)) { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } return x * w; } const int Max_n = 1e5 + 5; int n, a, b, c, K, ans; int cnt, cc; LL Ans1, Ans2; double xs, xe, ys[Max_n], ye[Max_n]; struct dots { double x, y; } k[Max_n * 5]; struct xl { double x, y; double operator*(const xl &b) { return x * b.y - b.x * y; } }; set<pair<double, double> > s; set<pair<double, double> >::iterator it; inline bool cmp(dots a, dots b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } inline void part1() { n = read(), a = read(), b = read(), c = read(), xs = read(), xe = read(); for (int i = 1; i <= n; i++) ys[i] = read(); double D = xe - xs; for (int i = 1; i <= n; i++) { ye[i] = read(); it = s.end(); if (s.size()) it--; while ((*it).first > ye[i] && it != s.begin()) { cnt++; xl d1 = (xl){-D, ys[i] - (*it).first}, d2 = (xl){0, ye[i] - (*it).first}; double S1 = abs(d1 * d2); d1 = (xl){D, ye[i] - (*it).second}, d2 = (xl){0, ys[i] - (*it).second}; double S2 = abs(d1 * d2); double K = S2 / (S1 + S2), D1 = (*it).first - (*it).second; k[cnt].x = xs + D * K, k[cnt].y = (*it).second + K * D1; it--; } if (it == s.begin()) if ((*it).first > ye[i]) { cnt++; xl d1 = (xl){-D, ys[i] - (*it).first}, d2 = (xl){0, ye[i] - (*it).first}; double S1 = abs(d1 * d2); d1 = (xl){D, ye[i] - (*it).second}, d2 = (xl){0, ys[i] - (*it).second}; double S2 = abs(d1 * d2); double K = S2 / (S1 + S2), D1 = (*it).first - (*it).second; k[cnt].x = xs + D * K, k[cnt].y = (*it).second + K * D1; } s.insert(make_pair(ye[i], ys[i])); } for (int i = 1; i <= cnt; i++) { double X = k[i].x, Y = k[i].y; k[i].x = X + Y, k[i].y = X - Y; } sort(k + 1, k + cnt + 1, cmp); } double z[Max_n << 4]; int C[Max_n << 3]; int cntr, hd[Max_n], nx[Max_n << 1], to[Max_n << 1]; struct que { double pos; double l, r, L, R; int id, t; } q[Max_n << 3]; struct person { double x, y, r; } p[Max_n]; inline bool cmp2(que a, que b) { return a.pos == b.pos ? a.t < b.t : a.pos < b.pos; } inline void add(int k, int x) { for (int i = k; i <= cc; i += i & -i) C[i] += x; } inline int query(int k) { int ans = 0; for (int i = k; i; i -= i & -i) ans += C[i]; return ans; } inline void part2() { K = read(); for (int i = 1; i <= K; i++) { p[i].x = read(), p[i].y = read(), p[i].r = read(); double X = p[i].x, Y = p[i].y; p[i].x = X + Y, p[i].y = X - Y; } int Cnt = 0; for (int i = 1; i <= K; i++) { Cnt++; q[Cnt].l = p[i].x - p[i].r, q[Cnt].r = p[i].x + p[i].r; q[Cnt].L = p[i].y - p[i].r, q[Cnt].R = p[i].y + p[i].r; q[Cnt].t = 1, q[Cnt + 1] = q[Cnt], q[Cnt + 1].t = 3; q[Cnt].pos = q[Cnt].l, q[++Cnt].pos = q[Cnt].r; z[++cc] = q[Cnt].L, z[++cc] = q[Cnt].R; q[Cnt].id = q[Cnt - 1].id = i; } for (int i = 1; i <= cnt; i++) { Cnt++, q[Cnt].pos = k[i].x, q[Cnt].l = k[i].y, q[Cnt].t = 2; z[++cc] = q[Cnt].l; } sort(q + 1, q + Cnt + 1, cmp2); sort(z + 1, z + cc + 1); for (int i = 1; i <= Cnt; i++) { if (q[i].t == 1) { int x = lower_bound(z + 1, z + cc + 1, q[i].R) - z; int y = lower_bound(z + 1, z + cc + 1, q[i].L) - z; add(y, 1), add(x + 1, -1); } if (q[i].t == 3) { int x = lower_bound(z + 1, z + cc + 1, q[i].R) - z; int y = lower_bound(z + 1, z + cc + 1, q[i].L) - z; add(y, -1), add(x + 1, 1); } if (q[i].t == 2) { int x = lower_bound(z + 1, z + cc + 1, q[i].l) - z; if (query(x)) ans++; } } Ans1 += 1ll * ans * c, Ans2 += 1ll * ans * c; Ans1 += 1ll * a * cnt; } int num[Max_n], P[Max_n]; int top, tim, dfn[Max_n], low[Max_n], vis[Max_n], stk[Max_n]; int size[Max_n], bel[Max_n], cir; bool cmp3(int a, int b) { return ye[a] < ye[b]; } void addr(int u, int v) { cntr++; nx[cntr] = hd[u], to[cntr] = v; hd[u] = cntr; } void dfs(int x) { stk[++top] = x, dfn[x] = low[x] = ++tim, vis[x] = 1; go(x, i, v) if (!vis[v]) dfs(v), low[x] = min(low[x], low[v]); else if (vis[v] == 1) low[x] = min(low[x], dfn[v]); if (dfn[x] == low[x]) { cir++; while (stk[top] != x) bel[stk[top]] = cir, size[cir]++, vis[stk[top--]] = -1; top--, bel[x] = cir, size[cir]++; } } void part3() { for (int i = 1; i <= n; i++) num[i] = i; sort(num + 1, num + n + 1, cmp3); for (int i = 1; i <= n; i++) addr(num[i], i), addr(i, num[i]); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i); int tot = 0; for (int i = 1; i <= cir; i++) tot += size[i] - 1; Ans2 += 1ll * tot * a + 1ll * (cnt - tot) * b; } int main() { #ifndef ONLINE_JUDGE freopen("trick.in", "r", stdin); freopen("trick.out", "w", stdout); #endif part1(); part2(); part3(); if (Ans1 > Ans2) swap(Ans1, Ans2); cout << Ans1 << " " << Ans2; }

转载于:https://www.cnblogs.com/luoshuitianyi/p/11594733.html

[5cb2a2d6a8dc9.png]: /images/20230810/94ecb6cfb3954d119d2e0eed0fb65406.png
[5cb2a389b6bb8.png]: /images/20230810/2a1b6e546dfd450a805bf9a981a0cff4.png
[5cb2a5b2c7b4c.png]: /images/20230810/2006ee05e798401699f6fd1c8b194fa3.png