题解-GXOI/GZOI2019 特技飞行

时间:2022-04-02 09:12:44

Problem

loj3085 bzoj不放题面差评

题意概要:给出两条竖直直线,再给出 \(n\) 架飞机的初始航线:一条接通这两条直线的线段,保证航线交点不在两条直线上。现要求安排所有飞机在航线相交处做特技:

  • 擦身而过:两架飞机按原方向线路继续前进,一次得分 \(b\)
  • 对向交换:两架飞机交换线路继续前进,一次得分 \(a\)

另外,给定 \(k\) 个边界与坐标轴成 \(45°\)角 的正方形,若一次特技被至少一个正方形囊括,则总得分加 \(c\)

现要求决策每次相遇做的特技,求最大/最小收益

同时要求决策方案中所有飞机 在两条竖直直线处 按纵坐标的排序 相同

\(n, Q\leq 10^5\)

交点个数 \(\leq 5\times 10^5\)

这题意概要好像和原题面差不多了qwq

Solution

\(\mathrm{GXOI/GZOI2019}\) 的题好毒瘤啊,两道联赛、两道原题、一道麻将题……完全不想打,就这题还有点意思……还偏偏要整个二合一……

交点个数 \(\leq 5\times 10^5\),应该是暗示要暴力求出来:交点一定是右部直线排序的逆序对(左部已经有序),用个 \(set\) 暴力扫就是 \(O(n\log n)\)。就得到了所有交点

\(c\) 的贡献很明显是单独求的,将坐标系旋转 \(45°\) 后就可以扫描线了。所以其实难度在于如何求 \(a,b\) 的贡献

设交点总数为 \(t\),其中有 \(x\) 个点交换航线,\(t-x\) 个点不交换。这部分贡献是 \(ax+b(t-x)=(a-b)x+bt\),所以总得分的最大最小值一定是 \(x\) 取最值时取得,即只需要求最少/多有多少个点交换航线

首先因为要求飞机在起终点的顺序不变,而交换航线不会改变顺序,所有点都交换航线肯定是可行的,即 \(x_{\max}=t\)

再考虑最小值。假如所有点都不换航线(\(x = 0\)),在大部分情况下都不合法,考虑使用最少的交换航线使得最终状态与初始状态一致:可以发现,若按照原航线行进时,飞机状态的变化产生了 \(s_1\rightarrow s_2\rightarrow ...\rightarrow s_m\rightarrow s_1\) 的循环,则可以使用 \(m-1\) 次交换使得方案合法(一次交换可以使得一架且最多一架飞机到达指定位置,使 \(m-1\) 架飞机合法后剩下的那一架飞机也即合法)

那么需要交换的次数为 "\(n-\)循环的个数"

复杂度为 \(O(n\log n+k\log k)\),瓶颈在暴力找交点和扫描线

Code

代码中 get_cross 为暴力找交点,Circle 为找循环,Extra 为扫描线

#include <bits/stdc++.h>
using namespace std; inline void read(int&x){
char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
} const double eps = 1e-6;
const int N = 101000, M = 501000; int l0[N], r0[N];
int n,L,R; struct pnt {
double x, y;
friend inline bool operator < (const pnt&A,const pnt&B) {return A.x < B.x;}
}p[M]; int p0; pnt crs(int i,int j) {
double th = (double)abs(l0[i] - l0[j]) / (abs(l0[i] - l0[j]) + abs(r0[i] - r0[j]));
return (pnt) {L + (R-L) * th, l0[i] + (r0[i] - l0[i]) * th};
} set <int> c;
set <int> :: iterator itr;
map <int,int> mp; int get_cross() {
for(int i=1;i<=n;++i) {
c.insert(r0[i]);
mp[r0[i]] = i;
itr = c.find(r0[i]);
for(++itr; itr != c.end(); ++itr) {
int j = mp[*itr];
p[++p0] = crs(i, j);
}
}
return p0;
} namespace Circle {
int b[N], dad[N];
int find(int x) {return dad[x] ? dad[x] = find(dad[x]) : x;}
int main() {
for(int i=1;i<=n;++i) b[i] = r0[i];
sort(b+1,b+n+1);
int res = 0;
for(int i=1,j,p1,p2;i<=n;++i) {
j = lower_bound(b+1,b+n+1,r0[i])-b;
if((p1 = find(i)) == (p2 = find(j))) ++res;
else dad[p1] = p2;
}
return p0 - (n - res);
}
} namespace Extra {
double b[M+N+N];
int Q, tot; struct LNE {
double x, y1, y2; int w;
friend inline bool operator < (const LNE&A,const LNE&B) {return A.x < B.x;}
}l[N+N]; namespace BIT {
#define lb(x) (x&(-x))
int d[M+N+N];
inline int qry(int x) {
int res = 0;
for(int i=x;i;i-=lb(i)) res += d[i];
return res;
}
inline void upd(int l, int r, int w) {
for(;l<=tot;l+=lb(l)) d[l] += w;
for(++r;r<=tot;r+=lb(r)) d[r] -= w;
}
#undef lb
} void input() {
double x, y;
for(int i=1;i<=p0;++i) {
x = p[i].x, y = p[i].y;
p[i].x = x + y, p[i].y = x - y;
b[++tot] = p[i].y;
}
sort(p+1,p+p0+1);
int r; read(Q);
for(int i=1;i<=Q;++i) {
scanf("%lf%lf",&x,&y), read(r);
l[i+i-1].x = x + y - r - eps;
l[i+i-1].y1 = x - r - y - eps;
l[i+i-1].y2 = x - y + r + eps;
l[i+i-1].w = 1;
l[i+i].x = x + y + r + eps;
l[i+i].y1 = x - y - r - eps;
l[i+i].y2 = x + r - y + eps;
l[i+i].w = -1; b[++tot] = x - y + r + eps;
b[++tot] = x - y - r - eps;
}
Q <<= 1;
sort(l+1,l+Q+1); sort(b+1,b+tot+1);
int tt0 = 0; b[0] = -1e10;
for(int i=1;i<=tot;++i)
if(fabs(b[i] - b[i-1]) > eps)
b[++tt0] = b[i];
tot = tt0; for(int i=1;i<=p0;++i) p[i].y = lower_bound(b+1,b+tot+1,p[i].y) - b;
for(int i=1;i<=Q;++i) {
l[i].y1 = lower_bound(b+1,b+tot+1,l[i].y1) - b;
l[i].y2 = lower_bound(b+1,b+tot+1,l[i].y2) - b;
}
} int main() {
input(); int res = 0;
for(int i=1,j=1;i<=p0;++i) {
while(j <= Q and l[j].x <= p[i].x)
BIT::upd(l[j].y1, l[j].y2, l[j].w), ++j;
if(BIT::qry(p[i].y)) ++res;
}
return res;
}
} int main() {
int A, B, C;
read(n), read(A), read(B), read(C);
read(L), read(R);
for(int i=1;i<=n;++i) read(l0[i]);
for(int i=1;i<=n;++i) read(r0[i]); int ans1 = A * get_cross(), ans2 = ans1, exa;
ans2 += (B - A) * Circle::main();
exa = C * Extra::main();
if(ans1 > ans2) swap(ans1, ans2);
printf("%d %d\n",ans1 + exa, ans2 + exa);
return 0;
}

题解-GXOI/GZOI2019 特技飞行的更多相关文章

  1. P5302 &lbrack;GXOI&sol;GZOI2019&rsqb;特技飞行

    题目地址:P5302 [GXOI/GZOI2019]特技飞行 这里是官方题解(by lydrainbowcat) 题意 给 \(10^5\) 条直线,给 \(x = st\) 和 \(x = ed\) ...

  2. luogu P5302 &lbrack;GXOI&sol;GZOI2019&rsqb;特技飞行

    传送门 强行二合一可还行 首先\(c\)的贡献是不会变的,先考虑求出多少交点被矩形覆盖,交点的话可以按左端点纵坐标从下到上顺序枚举一条线段,然后维护右端点纵坐标的set,把之前处理过线段的右端点放进s ...

  3. &lbrack;GXOI&sol;GZOI2019&rsqb;特技飞行

    题目链接 [https://www.luogu.org/problem/P5302] 思路:这道题可以说是两道题的合并.注意到\(c\)的分数与 \(a\)和\(b\)的分数 无关,也就是说可以分成两 ...

  4. 题解&colon;&lbrack;GXOI&sol;GZOI2019&rsqb;与或和

    开始完全没思路 在洛谷看到样例一,突发奇想,决定先做一下元素只有0/1的情况 发现子任务1是全1子矩阵 子任务2是总子矩阵个数减去全0子矩阵 发现全0/1矩阵可以构造单调栈解决.具体做法:前缀和求出每 ...

  5. &lbrack;GX&sol;GZOI2019&rsqb;特技飞行(扫描线&plus;置换)

    感觉是6题中最难的一题,其实这题是一个二合一: 第一问:给定平面上若干点和k个关键点,关键点覆盖一个45°倾斜的正方形范围r,求有多少点被至少一个关键点覆盖.这个可以曼哈顿转切比雪夫距离,然后再扫描线 ...

  6. GXOI&sol;GZOI2019题解

    GXOI/GZOI2019题解 P5300 [GXOI/GZOI2019]与或和 一眼题.. 显然枚举每个二进制位,答案就变成了全1子矩阵数量. 这个xjb推推,单调栈一下就行了. #include& ...

  7. Loj &num;3085&period; 「GXOI &sol; GZOI2019」特技飞行

    Loj #3085. 「GXOI / GZOI2019」特技飞行 题目描述 公元 \(9012\) 年,Z 市的航空基地计划举行一场特技飞行表演.表演的场地可以看作一个二维平面直角坐标系,其中横坐标代 ...

  8. 【LOJ】&num;3085&period; 「GXOI &sol; GZOI2019」特技飞行

    LOJ#3085. 「GXOI / GZOI2019」特技飞行 这显然是两道题,求\(C\)是一个曼哈顿转切比雪夫后的线段树扫描线 求\(AB\),对向交换最大化和擦身而过最大化一定分别为最大值和最小 ...

  9. 「GXOI &sol; GZOI2019」简要题解

    「GXOI / GZOI2019」简要题解 LOJ#3083. 「GXOI / GZOI2019」与或和 https://loj.ac/problem/3083 题意:求一个矩阵的所有子矩阵的与和 和 ...

随机推荐

  1. RegExp 对象 &lpar;JavaScript&rpar;

    $1...$9 属性 (RegExp) (JavaScript) 返回在模式匹配期间找到的,所存储的最近的九个部分.只读. 语法         RegExp.$n 参数     RegExp 始终为 ...

  2. IOS 字典快速转换为Model 模型

    一般情况下IOS得局部页面加载的过程是,创建一个Model然后,将Nib文件与Model进行关联,然后能够快速的获取到Nib文件上的控件实例.操作生成页面. 但是原生的内容是没有直接通过Json获取M ...

  3. 用thinkphp将网络上的图片下载到本地服务器

    我用的thinkphp版本是3.2.3,这个版本的跟更早些版本的调用方法不太一样,正确的调用方法是: Demo3Controller.class <?php namespace Home\Con ...

  4. &lbrack;译&rsqb;LINT TO SQL 介绍&lpar;数据库查询&rpar; - Part&period;3

    出处:Linq To Sql (Part.3 – Querying our database) 术语表 Built-in:内置的 Clause:子句 Debugger:调试器 Object Relat ...

  5. 苹果IOS与谷歌 android系统的UI设计原则

    一.苹果为IOS的界面设计提出了六大原则: 1.整体美学 整体美学指的是一个应用的表现和行为与它的功能完美集成,传达连贯的信息. 人们关心一个应用是否提供它承诺的功能,但他们也被应用的外观和行为强烈影 ...

  6. 华为oj之字符个数统计

    题目:字符个数统计 热度指数:4720 时间限制:1秒 空间限制:32768K 本题知识点: 字符串 题目描述 编写一个函数,计算字符串中含有的不同字符的个数.字符在ACSII码范围内(0~127). ...

  7. spring filter lister servlet

    https://blog.csdn.net/nacey5201/article/details/8547772 https://blog.csdn.net/xwl617756974/article/d ...

  8. HDUOJ ---1423 Greatest Common Increasing Subsequence(LCS)

    Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536 ...

  9. 谈API网关的背景、架构以及落地方案

    Chris Richardson曾经在他的博客上详细介绍过API网关,包括API网关的背景.解决方案以及案例.对于大多数基于微服务的应用程序而言,API网关都应该是系统的入口,它会负责服务请求路由.组 ...

  10. &num;&sol;bin&sol;sh参数-e的含义

    注:本博客欢迎转载和引用,但请保留原作者信息! 一.背景 今天遇到一个诡异的问题,一旦脚本中判断$?为非零,那么脚本就会自动退出的情况,仔细调试脚本的逻辑,并没有发现错误,因此作此文 二.解决 既然要 ...