luogu P5302 [GXOI/GZOI2019]特技飞行-白红宇

luogu P5302 [GXOI/GZOI2019]特技飞行

阅读量：4514 次

发布时间：2019-06-08

本文共 1474 字，大约阅读时间需要 4 分钟。

强行二合一可还行

首先\(c\)的贡献是不会变的,先考虑求出多少交点被矩形覆盖,交点的话可以按左端点纵坐标从下到上顺序枚举一条线段,然后维护右端点纵坐标的set,把之前处理过线段的右端点放进set里,然后所有右端点在当前线段右端点上方的线段都是和当前线段有交点的,直接算出来,并且这样算不会算重

本题中的矩形是斜着的,但是如果我们把所有点绕原点顺时针转\(45^\circ\),那么矩形的四边都会和坐标轴平行,我们可以直接考虑每个点是否被矩形覆盖,把坐标离散化,然后套扫描线扫横坐标,用树状数组维护每个纵坐标是否被覆盖,扫到某个点就直接查对应\(y\)坐标是否有值就行了

然后考虑\(a,b\),最大值最小值一定是一个尽量多用「对向交换」,一个尽量多用「擦身而过」,而「对向交换」不会改变飞机在纵坐标的相对顺序,所以可以全部用「对向交换」;然后尽量多用「擦身而过」等价于尽量少用「对向交换」.考虑把左端点纵坐标按大小编号,右端点纵坐标也按大小编号,然后左端点编号\(i\)向对应的右端点编号\(j\)连边,我们可以得到若干个环,因为要使得最后的相对顺序和开始的相对顺序一样,也就是要用最少的操作数把那些环转化成\(n\)个自环,而每次「对向交换」可以对应到交换两点连出去的点,可以发现一个大小为\(sz\)的环只要操作\(sz-1\)次,所以最少次数就是\(\sum_{circle} sz-1\),等价于\(n-\)环的个数

// luogu-judger-enable-o2#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define LL long long#define db doubleusing namespace std;const int N=1e5+10;const db sb=1.0/sqrt(2),eps=1e-8;int rd(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*w;}struct nn{ db x; nn(){} nn(db nx){x=nx;} bool operator < (const nn &bb) const {return x
               
                 s1;set
                
                 ::iterator i1;struct matrix{ point a,b; bool operator < (const matrix &bb) const {return bb.a
                 
                  
                    hp;bool cmp(matrix aa,matrix bb){return aa.a
                   
                    a2) swap(a1,a2); printf("%lld %lld\n",a1,a2); return 0;}

转载于:https://www.cnblogs.com/smyjr/p/10763209.html

你可能感兴趣的文章