头像

Xing_Ling


访客:4285

离线:3天前



Xing_Ling
14天前

【学习笔记】计算几何全家桶

继续骗访问量

本来是不想码的,但总是忘记一些基本操作,还是记下来比较好。

一:【准备工作】

#define LD double
#define Vector Point
#define Re register int
const LD eps=1e-8;//据说:出题的大学生们基本上都是用的这个值
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}//处理精度
inline LD Abs(LD a){return a*dcmp(a);}//取绝对值
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
    inline void out(){printf("%.2lf %.2lf\n",x,y);}
};

二:【向量】

1.【模长】

对于 $\vec{a}=(x,y),$ $|\vec{a}|=\sqrt{x^2+y^2}$ $=\sqrt{|\vec{a}|^{2}}$ $=\sqrt{\vec{a} \cdot \vec{a}}$ 。

inline LD Len(Vector a){return sqrt(Dot(a,a));}//【模长】

2.【向量加减】

对于 $\vec{a}=(x_{1},y_{1}),$ $\vec{b}=(x_{2},y_{2}),$ $\vec{a}+\vec{b}=(x_{1}+x_{2},y_{1}+y_{2})$ 。

对于 $\vec{a}=(x_{1},y_{1}),$ $\vec{b}=(x_{2},y_{2}),$ $\vec{a}-\vec{b}=(x_{1}-x_{2},y_{1}-y_{2})$ 。

inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}

3.【向量数乘(放缩)】

对于 $\vec{a}=(x,y),$ $\lambda \vec{a}=(\lambda x,\lambda y)$ 。

除法也可以理解为数乘:$\frac{\vec{a}}{\lambda}=\frac{1}{\lambda}\vec{a}=(\frac{1}{\lambda} x,\frac{1}{\lambda} y)$ 。

inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}

4.【点积(内积)(数量积)】

$\vec{a} \cdot \vec{b}=|\vec{a}||\vec{b}| \cos \theta$ $(\theta=\langle\vec{a}, \vec{b}\rangle)$ 。

对于 $\vec{a}=(x_{1}, y_{1}), \vec{b}=(x_{2}, y_{2}),$ $\vec{a} \cdot \vec{b}=x_{1} x_{2}+y_{1} y_{2}$ 。

夹角 $\theta$ 与点积大小的关系:

$(1).$ 若 $\theta=0^{\circ},$ $\vec{a} \cdot \vec{b}=|\vec{a}||\vec{b}|$ 。

$(2).$ 若 $\theta=180^{\circ},$ $\vec{a} \cdot \vec{b}=-|\vec{a}||\vec{b}|$ 。

$(3).$ 若 $\theta < 90^{\circ},$ $\vec{a} \cdot \vec{b}>0$ 。

$(4).$ 若 $\theta=90^{\circ},$ $\vec{a} \cdot \vec{b}=0$ 。

$(5).$ 若 $\theta > 90^{\circ},$ $\vec{a} \cdot \vec{b}<0$ 。

inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}//【点积】

5.【叉积(外积)(向量积)】

$\vec{a} \times \vec{b}=|\vec{a}||\vec{b}| \cos \theta$ $(\theta=\langle\vec{a}, \vec{b}\rangle)$ 。

对于 $\vec{a}=(x_{1}, y_{1}), \vec{b}=(x_{2}, y_{2}),$ $\vec{a} \times \vec{b}=x_{1} y_{2}-y_{1} x_{2}$ 。

向量位置与叉积大小的关系:

$(1).$ 若 $\vec{a} | \vec{b},$ $\vec{a} \times \vec{b}=0$ 。

$(2).$ 若 $\vec{a}$ 在 $\vec{b}$ 右侧,$\vec{a} \times \vec{b}>0$ 。

$(3).$ 若 $\vec{a}$ 在 $\vec{b}$ 左侧,$\vec{a} \times \vec{b}<0$ 。

inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}//【叉积】

三:【点、向量的位置变换】

1.【点、向量的旋转】

$(1).$ 对于点 $P=(x,y)$ 或向量 $\vec{a}=(x,y)$,将其顺时针旋转 $\theta$ 角度(点:关于原点,向量:关于起点): $\begin{vmatrix}x&y\end{vmatrix}$ $\times$ $\begin{vmatrix}cos \theta & -sin \theta\ sin \theta & cos \theta \end{vmatrix}$ $=$ $\begin{vmatrix}xcos \theta +ysin \theta &-xsin \theta + ycos \theta \end{vmatrix}$ 。

inline Point turn_P(Point a,LD theta){//【点A\向量A顺时针旋转theta(弧度)】
    LD x=a.x*cos(theta)+a.y*sin(theta);
    LD y=-a.x*sin(theta)+a.y*cos(theta);
    return Point(x,y);
}

$(2).$ 将点 $A(x,y)$ 绕点 $B(x_0,y_0)$ 顺时针旋转 $\theta$ 角度:$\begin{vmatrix}(x!-!x_0)cos \theta +(y!-!y_0)sin \theta + x_0 &-(x!-!x_0)sin \theta + (y!-!y_0)cos \theta + y_0 \end{vmatrix}$ 。

inline Point turn_PP(Point a,Point b,LD theta){//【将点A绕点B顺时针旋转theta(弧度)】
    LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
    LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
    return Point(x,y);
}

四:【图形与图形之间的关系】

1.【点与线段】

$(1).$ 判断点 $P$ 是否在线段 $AB$ 上:

inline int pan_PL(Point p,Point a,Point b){//【判断点P是否在线段AB上】
    return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0;//做法一 
//  return !dcmp(Cro(p-a,b-a))&&dcmp(min(a.x,b.x)-p.x)<=0&&dcmp(p.x-max(a.x,b.x))<=0&&dcmp(min(a.y,b.y)-p.y)<=0&&dcmp(p.y-max(a.y,b.y))<=0;//做法二 
    //PA,AB共线且P在AB之间(其实也可以用len(p-a)+len(p-b)==len(a-b)判断,但是精度损失较大)
}

$(2).$ 点 $P$ 到线段 $AB$ 的距离:

inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}//两点坐标重合则相等
inline LD dis_PL(Point p,Point a,Point b){//【点P到线段AB距离】
    if(a==b)return Len(p-a);//AB重合
    Vector x=p-a,y=p-b,z=b-a;
    if(dcmp(Dot(x,z))<0)return Len(x);//P距离A更近
    if(dcmp(Dot(y,z))>0)return Len(y);//P距离B更近
    return Abs(Cro(x,z)/Len(z));//面积除以底边长
}

2.【点与直线】

$(1).$ 判断点 $P$ 是否在直线 $AB$ 上:

inline int pan_PL_(Point p,Point a,Point b){//【判断点P是否在直线AB上】
    return !dcmp(Cro(p-a,b-a));//PA,AB共线
}

$(2).$ 点 $P$ 到直线 $AB$ 的垂足 $F$:

inline Point FootPoint(Point p,Point a,Point b){//【点P到直线AB的垂足】
    Vector x=p-a,y=p-b,z=b-a;
    LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);//分别计算AP,BP在AB,BA上的投影
    return a+z*(len1/(len1+len2));//点A加上向量AF
}

$(3).$ 点 $P$ 关于直线 $AB$ 的对称点:

inline Point Symmetry_PL(Point p,Point a,Point b){//【点P关于直线AB的对称点】
    return p+(FootPoint(p,a,b)-p)*2;//将PF延长一倍即可
}

3.【线与线】

$(1).$ 两直线 $AB,CD$ 的交点 $Q$:

inline Point cross_LL(Point a,Point b,Point c,Point d){//【两直线AB,CD的交点】
    Vector x=b-a,y=d-c,z=a-c;
    return a+x*(Cro(y,z)/Cro(x,y));//点A加上向量AF
}

$(2).$ 判断直线 $AB$ 与线段 $CD$ 是否相交:

inline int pan_cross_L_L(Point a,Point b,Point c,Point d){//【判断直线AB与线段CD是否相交】
    return pan_PL(cross_LL(a,b,c,d),c,d);//直线AB与直线CD的交点在线段CD上
}

$(3).$ 判断两线段 $AB,CD$ 是否相交:

inline int pan_cross_LL(Point a,Point b,Point c,Point d){//【判断两线段AB,CD是否相交】
    LD c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
    LD d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;//分别在两侧
}

4.【点与多边形】

$(1).$ 判断点 $A$ 是否在任意多边形 $Poly$ 以内(射线法):

inline int PIP(Point *P,Re n,Point a){//【射线法】判断点A是否在任意多边形Poly以内
    Re cnt=0;LD tmp;
    for(Re i=1;i<=n;++i){
        Re j=i<n?i+1:1;
        if(pan_PL(a,P[i],P[j]))return 2;//点在多边形上
        if(a.y>=min(P[i].y,P[j].y)&&a.y<max(P[i].y,P[j].y))//纵坐标在该线段两端点之间
            tmp=P[i].x+(a.y-P[i].y)/(P[j].y-P[i].y)*(P[j].x-P[i].x),cnt+=dcmp(tmp-a.x)>0;//交点在A右方
    }
    return cnt&1;//穿过奇数次则在多边形以内
}

$(2).$ 判断点 $A$ 是否在凸多边形 $Poly$ 以内(二分法):

inline int judge(Point a,Point L,Point R){//判断AL是否在AR右边
    return dcmp(Cro(L-a,R-a))>0;//必须严格以内
}
inline int PIP_(Point *P,Re n,Point a){//【二分法】判断点A是否在凸多边形Poly以内
    //点按逆时针给出
    if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0;//在P[1_2]或P[1_n]外
    if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))return 2;//在P[1_2]或P[1_n]上
    Re l=2,r=n-1;
    while(l<r){//二分找到一个位置pos使得P[1]_A在P[1_pos],P[1_(pos+1)]之间
        Re mid=l+r+1>>1;
        if(judge(P[1],P[mid],a))l=mid;
        else r=mid-1;
    }
    if(judge(P[l],a,P[l+1]))return 0;//在P[pos_(pos+1)]外
    if(pan_PL(a,P[l],P[l+1]))return 2;//在P[pos_(pos+1)]上
    return 1;
}

5.【线与多边形】

$(1).$ 判断线段 $AB$ 是否在任意多边形 $Poly$ 以内:不相交且两端点 $A,B$ 均在多边形以内。

$(2).$ 判断线段 $AB$ 是否在凸多边形 $Poly$ 以内:两端点 $A,B$ 均在多边形以内。

6.【多边形与多边形】

$(1).$ 判断任意两个多边形是否相离:属于不同多边形的任意两边都不相交 且 一个多边形上的任意点都不被另一个多边形所包含。

inline int judge_PP(Point *A,Re n,Point *B,Re m){//【判断多边形A与多边形B是否相离】 
    for(Re i1=1;i1<=n;++i1){
        Re j1=i1<n?i1+1:1;
        for(Re i2=1;i2<=m;++i2){
            Re j2=i2<m?i2+1:1;
            if(pan_cross_LL(A[i1],A[j1],B[i2],B[j2]))return 0;//两线段相交
            if(PIP(B,m,A[i1])||PIP(A,n,B[i2]))return 0;//点包含在内
        }
    }
    return 1;
}

五:【图形面积】

1.【任意多边形面积】

inline LD PolyArea(Point *P,Re n){//【任意多边形P的面积】 
    LD S=0;
    for(Re i=1;i<=n;++i)S+=Cro(P[i],P[i<n?i+1:1]);
    return S/2.0;
}

2.【圆的面积并】

自适应辛普森法乱搞

3.【三角形面积并】

自适应辛普森法乱搞

或者扫描线?wo太菜了不会写。


六:【凸包】

1.【求凸包】

$(1).$ $\text{Graham}$ 扫描法

inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};//按坐标排序
inline int ConvexHull(Point *P,Re n,Point *cp){//【Graham扫描法】求凸包
    sort(P+1,P+n+1,cmp1);
    Re t=0;
    for(Re i=1;i<=n;++i){//下凸包
        while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    Re St=t;
    for(Re i=n-1;i>=1;--i){//上凸包
        while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    return --t;//要减一
}

2.【旋转卡壳】

(这玩意儿有 $222*3=24$ 种读音)

Rd Ans=Len(cp[2]-cp[1]);
for(Re i=1,j=3;i<=cnt;++i){
    while(dcmp(Cro(cp[i+1]-cp[i],cp[j]-cp[i])-Cro(cp[i+1]-cp[i],cp[j+1]-cp[i]))<0)j=j<cnt?j+1:1;//注意是<0,如果写<=0的话可能会被两个点的数据卡掉
    Ans=max(Ans,max(Len(cp[j]-cp[i]),Len(cp[j]-cp[i+1])));//求最远距离
}

3.【半平面交】

struct Line{
    Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
    inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,a);}//如果角度相等则取左边的
}L[N],Q[N];
inline Point cross(Line L1,Line L2){return cross_LL(L1.a,L1.b,L2.a,L2.b);}//获取直线L1,L2的交点 
inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}//判断点a是否在直线L的右边
inline int halfcut(Line *L,Re n,Point *P){//【半平面交】 
    sort(L+1,L+n+1);Re m=n;n=0;
    for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];
    Re h=1,t=0;
    for(Re i=1;i<=n;++i){
        while(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;//当队尾两个直线交点不是在直线L[i]上或者左边时就出队
        while(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;//当队头两个直线交点不是在直线L[i]上或者左边时就出队
        Q[++t]=L[i];
    }
    while(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;
    while(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;
    n=0;
    for(Re i=h;i<=t;++i)P[++n]=cross(Q[i],Q[i<t?i+1:h]);
    return n;
}

4.【闵可夫斯基和】

Vector V1[N],V2[N];
inline int Mincowski(Point *P1,Re n,Point *P2,Re m,Vector *V){//【闵可夫斯基和】求两个凸包{P1},{P2}的向量集合{V}={P1+P2}构成的凸包
    for(Re i=1;i<=n;++i)V1[i]=P1[i<n?i+1:1]-P1[i];
    for(Re i=1;i<=m;++i)V2[i]=P2[i<m?i+1:1]-P2[i];
    Re t=0,i=1,j=1;V[++t]=P1[1]+P2[1];
    while(i<=n&&j<=m)++t,V[t]=V[t-1]+(dcmp(Cro(V1[i],V2[j]))>0?V1[i++]:V2[j++]);
    while(i<=n)++t,V[t]=V[t-1]+V1[i++];
    while(j<=m)++t,V[t]=V[t-1]+V2[j++];
    return t;
}

5.【动态凸包】

struct ConvexHull{
    int op;set<Point>s;
    inline int PIP(Point P){
        IT it=s.lower_bound(Point(P.x,-inf));//找到第一个横坐标大于P的点
        if(it==s.end())return 0;
        if(it->x==P.x)return (P.y-it->y)*op<=0;//比较纵坐标大小
        if(it==s.begin())return 0;
        IT j=it,k=it;--j;return Cro(P-*j,*k-*j)*op>=0;//看叉姬
    }
    inline int judge(IT it){
        IT j=it,k=it;
        if(j==s.begin())return 0;--j;
        if(++k==s.end())return 0;
        return Cro(*it-*j,*k-*j)*op>=0;//看叉姬
    }
    inline void insert(Point P){
        if(PIP(P))return;//如果点P已经在凸壳上或凸包里就不插入了
        IT tmp=s.lower_bound(Point(P.x,-inf));if(tmp!=s.end()&&tmp->x==P.x)s.erase(tmp);//特判横坐标相等的点要去掉
        s.insert(P);IT it=s.find(P),p=it;
        if(p!=s.begin()){--p;while(judge(p)){IT tmp=p--;s.erase(tmp);}}
        if((p=++it)!=s.end())while(judge(p)){IT tmp=p++;s.erase(tmp);}
    }
}up,down;
int x,y,T,op;
int main(){
//    freopen("123.txt","r",stdin);
    in(T),up.op=1,down.op=-1;
    while(T--){
        in(op),P.In();
        if(op<2)up.insert(P),down.insert(P);//插入点P
        else puts((up.PIP(P)&&down.PIP(P))?"YES":"NO");//判断点P是否在凸包内
    }
}

七:【圆】

1.【三点确定一圆】

$(1).$ 暴力解方程:

设 $x^2+y^2+Dx+Ey+F=0$,圆心为 $O$,半径为 $r$,带入三点 $A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)$,解得:

$\begin{cases} D=\frac{(x_2^2+y_2^2-x_3^2-y_3^2)(y_1-y_2)-(x_1^2+y_1^2-x_2^2-y_2^2)(y_2-y_3)}{(x_1-x_2)(y_2-y_3)-(x_2-x_3)(y_1-y_2)} \ E=\frac{x_1^2+y_1^2-x_2^2-y_2^2+D(x_1-x_2)}{y_2-y_1} \ F=-(x_1^2+y_1^2+Dx_1+Ey_1) \ O=(-\frac{D}{2},-\frac{E}{2}) \ r=\frac{D^2+E^2-4F}{4} \end{cases}$

#define S(a) ((a)*(a))
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getCircle(Point A,Point B,Point C){//【三点确定一圆】暴力解方程
    LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
    LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
    LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
    LD F=-(S(x1)+S(y1)+D*x1+E*y1);
    return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}

$(2).$ 向量求三角形垂心:

inline Circle getcircle(Point A,Point B,Point C){//【三点确定一圆】向量垂心法
    Point P1=(A+B)*0.5,P2=(A+C)*0.5;
    Point O=cross_LL(P1,P1+Normal(B-A),P2,P2+Normal(C-A));
    return Circle(O,Len(A-O));
}

2.【最小覆盖圆】

【定理】 如果点 $p$ 不在集合 ${S}$ 的最小覆盖圆内,则 $p$ 一定在 ${S}\cup{p}$ 的最小覆盖圆上。

inline int PIC(Circle C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}//判断点A是否在圆C内
inline void Random(Point *P,Re n){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}//随机一个排列
inline Circle Min_Circle(Point *P,Re n){//【求点集P的最小覆盖圆】
//  random_shuffle(P+1,P+n+1);
    Random(P,n);Circle C=Circle(P[1],0);
    for(Re i=2;i<=n;++i)if(!PIC(C,P[i])){
        C=Circle(P[i],0);
        for(Re j=1;j<i;++j)if(!PIC(C,P[j])){
            C.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);
            for(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);
        }
    }
    return C;
}

3.【三角剖分】

inline LD calc(Point A,Point B,Point O,LD R){//【三角剖分】
    if(A==O||B==O)return 0;
    Re op=dcmp(Cro(A-O,B-O))>0?1:-1;LD ans=0;
    Vector x=A-O,y=B-O;
    Re flag1=dcmp(Len(x)-R)>0,flag2=dcmp(Len(y)-R)>0;
    if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0;//两个点都在里面
    else if(flag1&&flag2){//两个点都在外面
        if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0;//完全包含了圆弧
        else{//分三段处理 △+圆弧+△
            if(dcmp(Cro(A-O,B-O))>0)swap(A,B);//把A换到左边
            Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
            Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z;
            ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0;
        }
    }
    else{//一个点在里面,一个点在外面
        if(flag1)swap(A,B);//使A为里面的点,B为外面的点
        Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
        Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=dcmp(Cro(A-O,B-O))>0?F-z:F+z;
        ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0;
    }
    return ans*op;
}

【计算几何全家桶 Code】

#include<algorithm>
#include<cstdio>
#include<cmath>


/*一:【准备工作】*/
#define LD double
#define LL long long
#define Re register int
#define Vector Point
using namespace std;
const int N=262144+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}//处理精度
inline LD Abs(LD a){return a*dcmp(a);}//取绝对值
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
    inline void out(){printf("%.2lf %.2lf\n",x,y);}
};


/*二:【向量】*/
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}//【点积】
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}//【叉积】
inline LD Len(Vector a){return sqrt(Dot(a,a));}//【模长】
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}//【两向量夹角】
inline Vector Normal(Vector a){return Vector(-a.y,a.x);}//【法向量】
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}//两点坐标重合则相等


/*三:【点、向量的位置变换】*/

/*1.【点、向量的旋转】*/
inline Point turn_P(Point a,LD theta){//【点A\向量A顺时针旋转theta(弧度)】
    LD x=a.x*cos(theta)+a.y*sin(theta);
    LD y=-a.x*sin(theta)+a.y*cos(theta);
    return Point(x,y);
}
inline Point turn_PP(Point a,Point b,LD theta){//【将点A绕点B顺时针旋转theta(弧度)】
    LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
    LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
    return Point(x,y);
}


/*四:【图形与图形之间的关系】*/

/*1.【点与线段】*/
inline int pan_PL(Point p,Point a,Point b){//【判断点P是否在线段AB上】
    return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0;//做法一
//  return !dcmp(Cro(p-a,b-a))&&dcmp(min(a.x,b.x)-p.x)<=0&&dcmp(p.x-max(a.x,b.x))<=0&&dcmp(min(a.y,b.y)-p.y)<=0&&dcmp(p.y-max(a.y,b.y))<=0;//做法二
    //PA,AB共线且P在AB之间(其实也可以用len(p-a)+len(p-b)==len(a-b)判断,但是精度损失较大)
}
inline LD dis_PL(Point p,Point a,Point b){//【点P到线段AB距离】
    if(a==b)return Len(p-a);//AB重合
    Vector x=p-a,y=p-b,z=b-a;
    if(dcmp(Dot(x,z))<0)return Len(x);//P距离A更近
    if(dcmp(Dot(y,z))>0)return Len(y);//P距离B更近
    return Abs(Cro(x,z)/Len(z));//面积除以底边长
}

/*2.【点与直线】*/
inline int pan_PL_(Point p,Point a,Point b){//【判断点P是否在直线AB上】
    return !dcmp(Cro(p-a,b-a));//PA,AB共线
}
inline Point FootPoint(Point p,Point a,Point b){//【点P到直线AB的垂足】
    Vector x=p-a,y=p-b,z=b-a;
    LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);//分别计算AP,BP在AB,BA上的投影
    return a+z*(len1/(len1+len2));//点A加上向量AF
}
inline Point Symmetry_PL(Point p,Point a,Point b){//【点P关于直线AB的对称点】
    return p+(FootPoint(p,a,b)-p)*2;//将PF延长一倍即可
}

/*3.【线与线】*/
inline Point cross_LL(Point a,Point b,Point c,Point d){//【两直线AB,CD的交点】
    Vector x=b-a,y=d-c,z=a-c;
    return a+x*(Cro(y,z)/Cro(x,y));//点A加上向量AF
}
inline int pan_cross_L_L(Point a,Point b,Point c,Point d){//【判断直线AB与线段CD是否相交】
    return pan_PL(cross_LL(a,b,c,d),c,d);//直线AB与直线CD的交点在线段CD上
}
inline int pan_cross_LL(Point a,Point b,Point c,Point d){//【判断两线段AB,CD是否相交】
    LD c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
    LD d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;//分别在两侧
}

/*4.【点与多边形】*/
inline int PIP(Point *P,Re n,Point a){//【射线法】判断点A是否在任意多边形Poly以内
    Re cnt=0;LD tmp;
    for(Re i=1;i<=n;++i){
        Re j=i<n?i+1:1;
        if(pan_PL(a,P[i],P[j]))return 2;//点在多边形上
        if(a.y>=min(P[i].y,P[j].y)&&a.y<max(P[i].y,P[j].y))//纵坐标在该线段两端点之间
            tmp=P[i].x+(a.y-P[i].y)/(P[j].y-P[i].y)*(P[j].x-P[i].x),cnt+=dcmp(tmp-a.x)>0;//交点在A右方
    }
    return cnt&1;//穿过奇数次则在多边形以内
}
inline int judge(Point a,Point L,Point R){//判断AL是否在AR右边
    return dcmp(Cro(L-a,R-a))>0;//必须严格以内
}
inline int PIP_(Point *P,Re n,Point a){//【二分法】判断点A是否在凸多边形Poly以内
    //点按逆时针给出
    if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0;//在P[1_2]或P[1_n]外
    if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))return 2;//在P[1_2]或P[1_n]上
    Re l=2,r=n-1;
    while(l<r){//二分找到一个位置pos使得P[1]_A在P[1_pos],P[1_(pos+1)]之间
        Re mid=l+r+1>>1;
        if(judge(P[1],P[mid],a))l=mid;
        else r=mid-1;
    }
    if(judge(P[l],a,P[l+1]))return 0;//在P[pos_(pos+1)]外
    if(pan_PL(a,P[l],P[l+1]))return 2;//在P[pos_(pos+1)]上
    return 1;
}

/*5.【线与多边形】*/

/*6.【多边形与多边形】*/
inline int judge_PP(Point *A,Re n,Point *B,Re m){//【判断多边形A与多边形B是否相离】
    for(Re i1=1;i1<=n;++i1){
        Re j1=i1<n?i1+1:1;
        for(Re i2=1;i2<=m;++i2){
            Re j2=i2<m?i2+1:1;
            if(pan_cross_LL(A[i1],A[j1],B[i2],B[j2]))return 0;//两线段相交
            if(PIP(B,m,A[i1])||PIP(A,n,B[i2]))return 0;//点包含在内
        }
    }
    return 1;
}


/*五:【图形面积】*/

/*1.【任意多边形面积】*/
inline LD PolyArea(Point *P,Re n){//【任意多边形P的面积】
    LD S=0;
    for(Re i=1;i<=n;++i)S+=Cro(P[i],P[i<n?i+1:1]);
    return S/2.0;
}

/*2.【圆的面积并】*/

/*3.【三角形面积并】*/


/*六:【凸包】*/

/*1.【求凸包】*/
inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};//按坐标排序
inline int ConvexHull(Point *P,Re n,Point *cp){//【Graham扫描法】求凸包
    sort(P+1,P+n+1,cmp1);
    Re t=0;
    for(Re i=1;i<=n;++i){//下凸包
        while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    Re St=t;
    for(Re i=n-1;i>=1;--i){//上凸包
        while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    return --t;//要减一
}
/*2.【旋转卡壳】*/

/*3.【半平面交】*/
struct Line{
    Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
    inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,a);}//如果角度相等则取左边的
}L[N],Q[N];
inline Point cross(Line L1,Line L2){return cross_LL(L1.a,L1.b,L2.a,L2.b);}//获取直线L1,L2的交点
inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}//判断点a是否在直线L的右边
inline int halfcut(Line *L,Re n,Point *P){//【半平面交】
    sort(L+1,L+n+1);Re m=n;n=0;
    for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];
    Re h=1,t=0;
    for(Re i=1;i<=n;++i){
        while(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;//当队尾两个直线交点不是在直线L[i]上或者左边时就出队
        while(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;//当队头两个直线交点不是在直线L[i]上或者左边时就出队
        Q[++t]=L[i];
    }
    while(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;
    while(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;
    n=0;
    for(Re i=h;i<=t;++i)P[++n]=cross(Q[i],Q[i<t?i+1:h]);
    return n;
}

/*4.【闵可夫斯基和】*/
Vector V1[N],V2[N];
inline int Mincowski(Point *P1,Re n,Point *P2,Re m,Vector *V){//【闵可夫斯基和】求两个凸包{P1},{P2}的向量集合{V}={P1+P2}构成的凸包
    for(Re i=1;i<=n;++i)V1[i]=P1[i<n?i+1:1]-P1[i];
    for(Re i=1;i<=m;++i)V2[i]=P2[i<m?i+1:1]-P2[i];
    Re t=0,i=1,j=1;V[++t]=P1[1]+P2[1];
    while(i<=n&&j<=m)++t,V[t]=V[t-1]+(dcmp(Cro(V1[i],V2[j]))>0?V1[i++]:V2[j++]);
    while(i<=n)++t,V[t]=V[t-1]+V1[i++];
    while(j<=m)++t,V[t]=V[t-1]+V2[j++];
    return t;
}

/*5.【动态凸包】*/

/*七:【圆】*/

/*1.【三点确定一圆】*/
#define S(a) ((a)*(a))
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getCircle(Point A,Point B,Point C){//【三点确定一圆】暴力解方程
    LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
    LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
    LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
    LD F=-(S(x1)+S(y1)+D*x1+E*y1);
    return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
inline Circle getcircle(Point A,Point B,Point C){//【三点确定一圆】向量垂心法
    Point P1=(A+B)*0.5,P2=(A+C)*0.5;
    Point O=cross_LL(P1,P1+Normal(B-A),P2,P2+Normal(C-A));
    return Circle(O,Len(A-O));
}

/*2.【最小覆盖圆】*/
inline int PIC(Circle C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}//判断点A是否在圆C内
inline void Random(Point *P,Re n){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}//随机一个排列
inline Circle Min_Circle(Point *P,Re n){//【求点集P的最小覆盖圆】
//  random_shuffle(P+1,P+n+1);
    Random(P,n);Circle C=Circle(P[1],0);
    for(Re i=2;i<=n;++i)if(!PIC(C,P[i])){
        C=Circle(P[i],0);
        for(Re j=1;j<i;++j)if(!PIC(C,P[j])){
            C.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);
            for(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);
        }
    }
    return C;
}

/*3.【三角剖分】*/
inline LD calc(Point A,Point B,Point O,LD R){//【三角剖分】
    if(A==O||B==O)return 0;
    Re op=dcmp(Cro(A-O,B-O))>0?1:-1;LD ans=0;
    Vector x=A-O,y=B-O;
    Re flag1=dcmp(Len(x)-R)>0,flag2=dcmp(Len(y)-R)>0;
    if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0;//两个点都在里面
    else if(flag1&&flag2){//两个点都在外面
        if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0;//完全包含了圆弧
        else{//分三段处理 △+圆弧+△
            if(dcmp(Cro(A-O,B-O))>0)swap(A,B);//把A换到左边
            Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
            Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z;
            ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0;
        }
    }
    else{//一个点在里面,一个点在外面
        if(flag1)swap(A,B);//使A为里面的点,B为外面的点
        Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
        Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=dcmp(Cro(A-O,B-O))>0?F-z:F+z;
        ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0;
    }
    return ans*op;
}

int main(){}



Xing_Ling
14天前

【学习笔记】数论、数学—常见定理、结论、性质汇总

我又臭不要脸地来骗博客访问量啦QAQ

〇:【不知道放哪儿好的内容】

1.【下降幂、上升幂】

【基本性质、定理】

  • $x^{\underline{n}}=(x-1)^{\underline{n-1}}x=\frac{(x)!}{(x-n)!}=\prod_{i=x-n+1}^{x} i$ $(x^{\underline{0}}=1)$

  • $x^{\overline{n}}=(x+1)^{\overline{n-1}}x=\frac{(x+n-1)!}{(x-1)!}=\prod_{i=x}^{x+n-1} i$ $(x^{\overline{0}}=1)$

【推导结论】

  • $x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}$

  • $x^{\overline{n}}=(-1)^n(-x)^{\underline{n}}$

  • $x^{\underline{n}}=A_{x}^{n}$

  • $x^{\overline{n}}=A_{x+n-1}^{n}$

2.【单位根】

【基本性质、定理】

  • $\omega_{n}^{k}=cos(\frac{2\pi k}{n})+sin(\frac{2\pi k}{n})i$

  • $\omega_{n}^{k}=g^{\frac{k(P-1)}{n}}\mod P$ $(P=k2^{t}+1,P\in {Prime})$

【推导结论】

  • $\omega_{n}^{k}=(\omega_{n}^{1})^{k}$

  • $\omega_{n}^{j}\omega_{n}^{k}=\omega_{n}^{j+k}$

  • $\omega_{2n}^{2k}=\omega_{n}^{k}$

  • $\omega_{n}^{(k+n/2)}=-\omega_{n}^{k}$ $(n$ 为偶数 $)$

  • $\sum_{i=1}^{n-1}\omega_{n}^{i}=0$


一:【基本数论、数学知识】

1.【斐波那契数列(Fibonacci)】

【基本性质、定理】

  • $F_{i}=F_{i-1}+F_{i-2}$

【推导结论】

  • $\sum_{i=1}^{n}{F_{i}}=F_{n+2}-1$

  • $\sum_{i=1}^{n}{F_{2i-1}}=F_{2n}$

  • $\sum_{i=1}^{n}{F_{2i}}=F_{2n+1}-1$

  • $\sum_{i=1}^{n}{(F_{n})^2}=F_{n}F_{n+1}$

  • $F_{n+m}=F_{n-1}F_{m-1}+F_{n}F_{m}$

  • $(F_{n})^2=(-1)^{(n-1)}+F_{n-1}F_{n+1}$

  • $F_{2n-1}=(F_{n})^2-(F_{n-2})^2$

  • $F_{n}=\frac{F_{n+2}+F_{n-2}}{3}$

  • $\frac{F_{i}}{F_{i-1}} \approx \frac{\sqrt{5}-1}{2} \approx 0.618$

  • $F_{n}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}$ 【证明】

2.【最大公约数(GCD)】

【推导结论】

  • $\gcd(a,b)=\gcd(b,a-b)$ $(a>b)$

  • $\gcd(a,b)=\gcd(b,a \mod b)$

  • $[k | \gcd(a,b)] \iff$ $[k|a][k|b]$

  • $[\gcd(k,ab)=1]=[\gcd(k,a)=1][\gcd(k,b)=1]$

  • 在 $Fibonacc$ 数列中求相邻两项的 $\gcd$ 时,辗转相减次数等于辗转相除次数。

  • $\gcd\left(F_{n},F_{m}\right)=F_{\gcd(n,m)}$ 【证明】

3.【最小公倍数(LCM)】

【推导结论】

  • $\gcd(a,b)\operatorname{lcm}(a,b)=ab$

二:【组合数学】

1.【排列组合】

【基本性质、定理】

  • $A_{n}^{m}=\frac{n!}{(n-m)!}$

  • $C_{n}^{m}=\frac{A_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}=C_{n}^{n-m}$

  • $C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$

【推导结论】

  • $mC_{n}^{m}=nC_{n-1}^{m-1}$

  • $C_{n+1}^{m+1}=\sum_{i=m}^{n}C_{i}^{m}$

  • $C_{n}^{m}=\frac{n}{m}C_{n-1}^{m-1}$

  • $\sum_{i=0}^{k}C_{n}^{i}C_{m}^{k-i}=C_{n+m}^{k}$【范德蒙德卷积】

  • $\sum_{i=0}^{n}C_{n-i}^{i}=F_{n+1}$($F$ 为斐波那契数列)

2.【卢卡斯定理】

【基本性质、定理】

  • $C_{n}^{m}=C_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}C_{n\mod p}^{m\mod p}$ $(p\in{Prime})$

3.【牛顿二项式定理】

【基本性质、定理】

  • $(x+y)^{n}=\sum_{i=0}^{n}C_{n}^{i}x^{n-i}y^i$

【推导结论】

  • $\sum_{i=0}^{n}C_n^{i}=2^n$

  • $\sum_{i=0}^{n}iC_n^{i}=n2^{n-1}$

  • $\sum_{i=0}^{n}i^2C_n^{i}=n(n+1)2^{n-1}$

4.【广义牛顿二项式定理】

【基本性质、定理】

  • $C_{r}^{n}= \begin{cases} 0, & n<0,r\in\mathbb{R}\ 1, & n=0,r\in\mathbb{R}\ \frac{r(r-1)\cdots (r-n+1)}{n!}, & n>0,r\in\mathbb{R} \end{cases}$

  • $(1+x)^{-n}=\sum_{i=0}^{\infty}C_{-n}^{i}x^{i}=\sum_{i=0}^{\infty}(-1)^iC_{n+i-1}^{i}x^i$

  • $(x+y)^{\alpha}=\sum_{i=0}^{\infty}C_{\alpha}^{i}x^{\alpha-i}y^i$ $(x,y,\alpha\in\mathbb{R}\ \text{且}\ |\frac{x}{y}|<1)$ 【证明】

5.【卡特兰数 (Catalan)】

6.【斯特林数 (Stirling)】

【基本性质、定理】

  • $s_{n}^{m}=s_{n-1}^{m-1}+(n-1)s_{n-1}^{m}$ $(s_{n}^{n}=1,s_{n}^{0}=0^{n})$

  • $S_{n}^{m}=S_{n-1}^{m-1}+mS_{n-1}^{m}$ $(S_{n}^{n}=1,S_{n}^{0}=0^{n})$

【推导结论】

  • $n!=\sum_{i=0}^{n}s_{n}^{i}$

  • $x^{\overline{n}}=\sum_{i=0}^{n}s_{n}^{i}x^i$

  • $x^{\underline{n}}=\sum_{i=0}^{n}s_{n}^{i}x^i(-1)^{n-i}$

  • $\sum_{i=1}^{n}S_{n}^{i}s_{i}^{m}=\sum_{i=0}^{n}s_{n}^{i}S_{i}^{m}$

  • $m^n=\sum_{i=0}^{m,n}S_{n}^{i}m^{\underline{i}}=\sum_{i=0}^{m,n}S_{n}^{i}C_{m}^{i}i!$

  • $m^{n}=\sum_{i=0}^{m,n}S_{n}^{i}m^{\overline{i}}(-1)^{n-i}$

  • $S_{n}^{m}=\frac{\sum_{i=0}^{m}(-1)^{m-i}C_{m}^{i}i^{n}}{m!}=\sum_{i=0}^{m} \frac{(-1)^{m-i}}{(m-i)!}\frac{i^{n}}{i !}$ 【例题】

  • $\sum_{i=0}^{n} i^{k}=\sum_{j=0}^{n}j!S_{k}^{j}C_{n+1}^{j+1}$

7.【贝尔数 (Bell)】

【基本性质、定理】

  • $B(n)=\sum_{i=1}^{n}S_{n}^{i}$

8.【Polya 定理】

【基本性质、定理】

9.【容斥原理】

【推导结论】

  • $f(i)=\sum\limits_{j=i}^{n}(-1)^{j-i}C_{j}^{i}g(j)$ $=g(i)-\sum\limits_{j=i+1}C_{j}^{i}f(j)$($f(i)$ 为恰好满足 $i$ 的计数,$g(i)$ 为至少满足 $i$ 的计数)【例题】 【例题】 【例题】

10.【生成函数】

【推导结论】

(1).【常用普通生成函数 (OGF) 收敛性式】
  • $\sum_{i=0}^{\infty}x^i=\frac{1}{1-x}$

  • $\sum_{i=0}^{\infty}(i+1)x^i=\frac{1}{(1-x)^2}$

  • $\sum_{i=0}^{\infty}C_{n}^{i}x^i=(1+x)^n$

  • $\sum_{i=0}^{\infty}C_{n+i-1}^{i}x^i=\frac{1}{(1-x)^n}$

  • $\sum_{i=0}^{\infty}x^i=\frac{1}{1-x}$

(2).【常用指数生成函数 (EGF) 收敛性式】
  • $\sum_{i=0}^{\infty}\frac{x^i}{i!}=e^x$

  • $\sum_{i=0}^{\infty}\frac{x^{2i}}{(2i)!}=\frac{e^x+e^{-x}}{2}$

  • $\sum_{i=0}^{\infty}\frac{x^{2i+1}}{(2i+1)!}=\frac{e^x-e^{-x}}{2}$


三:【各种反演】

1.【欧拉函数与欧拉反演】

【基本性质、定理】

  • $\varphi(x)=x\prod_{i=1}^{n}(1-\frac{1}{p_{i}})$

  • $\gcd(a,b)=1\Longrightarrow \varphi(ab)=\varphi(a)\varphi(b)$

  • $\gcd(a,m)=1\Longrightarrow a^{\varphi(m)}\equiv 1(\bmod m)$

  • $\gcd(a,m)=1\Longrightarrow a^{b} \equiv a^{b\mod \varphi(m)}(\bmod m)$

  • $b>\varphi(m)\Longrightarrow a^{b} \equiv a^{b\mod \varphi(m)+\varphi(m)}(\bmod m)$

  • $\sum_{d|n}\varphi(d)=n$ (即 $\varphi\ast 1=\operatorname{id}$) 【证明】

【推导结论】

  • $p>2 \Longrightarrow [\varphi(p)\mod 2=0]$

  • $p\in{Prime} \Longrightarrow \varphi(p^{k})=p^{k}-p^{k-1}$

  • $\sum_{i=1}^{n}i[gcd(i,n)=1]=\frac{n\varphi(n)+[n=1]}{2}$ 【例题】

  • $f(n)=\sum_{i=1}^{n}[\gcd(i,k)=1]=\frac{n}{k}\varphi(k)+f(n\mod k)$

  • $\exists x\in N^{*},a^x=1(\bmod m)$ $\iff$ $\gcd(a,m)=1$ 【证明】 【例题】

2.【狄利克雷卷积 (Dirichlet) 与莫比乌斯反演 (Mobius) 】

【基本性质、定理】

  • $(f \ast g)(n)=\sum_{d | n} f(d) g(\frac{n}{d})=$

  • $\sum_{d|n} \mu(d)=\epsilon(n)$ (即 $\mu\ast1=\epsilon$)

  • $f(n)=\sum_{d | n} g(d) \Longrightarrow$ $g(n)=\sum_{d | n} \mu(\frac{n}{d}) f(d)$ (即 $f=g\ast1 \Longrightarrow g=f\ast\mu$)

  • $f(n)=\sum_{n | d} g(d) \Longrightarrow$ $g(n)=\sum_{n | d} \mu(\frac{d}{n}) f(d)$

  • $f(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} g(dk) \Longrightarrow$ $g(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d) f(dk)$

【推导结论】

(2).【GCD】
  • $\gcd(i,j)=\sum_{d|i,d|j} \varphi(d)$

  • $[\gcd(i,j)=1]=\sum_{d|i,d|j} \mu(d)$

  • $\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i,j)=$ $\sum_{d=1}^{n}d\left(2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\varphi(i)}-1\right)$ 【例题($9$ 倍经验)】

  • $\sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i,j)=$ $\sum_{d=1}^{n} \varphi(d) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor$ 【例题】

  • $\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j)=k]=$ $\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)\lfloor\frac{n}{d k}\rfloor\lfloor\frac{m}{d k}\rfloor$ 【例题】

  • $\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j)\in {Prime}]=$ $\sum_{d=1}^{n}\left(\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{p | d\ \&\ p\in{Prime}} \mu(\frac{d}{p})\right)$ 【例题】

  • $\prod_{i=1}^{n} \prod_{j=1}^{n} \left(\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\right)=$ $\frac{(n!)^{2n}}{\left(\prod_{d=1}^{n} d^{\left(2 S_{\varphi}(\lfloor\frac{n}{a}\rfloor)-1\right)}\right)}$ 【例题】

(3).【LCM】
  • $\sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i,j)=$ $\sum_{d=1}^{n} d\left(\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor} x^{2} \mu(x) \sum_{i=1}^{\lfloor\frac{n}{dx}\rfloor} i\sum_{i=1}^{\lfloor\frac{m}{dx}\rfloor} j \right)$ 【例题】
(4).【除数函数】
  • $\sigma_{k}=\sum_{d|n}d^{k}$(即 $\sigma_{k}=\operatorname{id}_{k}\ast1$)

  • $d(xy)=\sum_{i|x} \sum_{j|y}[\operatorname{gcd}(i, j)=1]$(其中 $d(x)$ 表示 $x$ 的约数个数)

  • $\sum_{i=1}^{n}d(i)=$ $\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$ 【例题】

  • $\sum_{i=1}^{n} \sum_{j=1}^{m} d(ij)=$ $\sum_{k=1}^{n}\mu(k)\left(\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor{\frac{n}{ik}}\rfloor\right)\left(\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{m}{i k}\rfloor\right)$ 【例题】

  • $\sum_{i=1}^{n} \sum_{j=1}^{n} \sigma(ij)=$ $\sum_{d=1}^{n} \mu(d)d \left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sigma(i)\right)^{2}$ 【例题】

  • $\sum_{i=1}^{n} \sum_{j=1}^{m} \sigma(\gcd(i,j))=$ $\sum_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\left(\sum_{i | d} \mu(\frac{d}{i}) \sigma(i)\right)$ (其中 $\sigma(x)$ 表示 $x$ 的约数和) 【例题】

(5).【莫比乌斯函数】
  • $\sum_{k=1}^{n}\mu^{2}(k)=\sum_{d=1}^{\sqrt{n}}\mu(d)\lfloor \frac{n}{d^{2}}\rfloor$ 【例题】

  • $\sum_{i=1}^{n}\mu^2(i)\sqrt{\frac{n}{i}}=n$ 【证明】

3.【二项式反演】

【基本性质、定理】

  • $f(n)=\sum_{i=0}^{n}C_{n}^{i}g(i) \Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}f(i)$

  • $f(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}f(i)$

  • $f(n)=\sum_{i=n}^{?}C_{i}^{n}g(i) \Longleftrightarrow$ $g(n)=\sum_{i=n}^{?}(-1)^{i-n}C_{i}^{n}f(i)$

  • $f(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}f(i)$

4.【斯特林反演】

【基本性质、定理】

  • $f(n)=\sum_{i=0}^{n} S_{n}^{i} g(i) \Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{n-i} s_{n}^{i} g(i)$

  • $f(n)=\sum_{i=0}^{n}s_{n}^{i}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{n-i}S_{n}^{i}f(i)$

  • $f(n)=\sum_{i=n}^{?} S_{i}^{n} g(i) \Longleftrightarrow$ $g(n)=\sum_{i=n}^{?}(-1)^{i-n} s_{i}^{n} g(i)$

  • $f(n)=\sum_{i=n}^{?}s_{i}^{n}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=n}^{?}(-1)^{i-n}S_{i}^{n}f(i)$

5.【单位根反演】

【基本性质、定理】

  • $[n|k]=\frac{\sum_{i=0}^{n-1}w_{n}^{ik}}{n}$

  • $[a=b]=\frac{\sum_{i=0}^{n-1} w_{n}^{a i} w_{n}^{-i b}}{n}(a,b<n)$

【推导结论】

  • $\sum_{i=0}^{n}C_{n}^{i}m^{i}a_{(i\mod 4)}=\frac{1}{4}\sum_{j=0}^{3}a_{j} \sum_{k=0}^{3}w_{4}^{-kj}(mw_{4}^{k}+1)^{n}$ 【例题】

  • $\sum\limits_{i=0}^{n}C_{n}^{i}m^i\lfloor\frac{i}{k}\rfloor=$ $\frac{1}{k}{\left(nm!(m!+!1)^{n-1}-\frac{1}{k}{\sum\limits_{t=0}^{k}(m\omega_{k}^{t}+1)^{n}f(t)}\right)}$ $\begin{smallmatrix}\left(!f(t)!=!\begin{cases}!\frac{k(k-1)}{2},\omega_{k}^{-t}!=!1\ !\frac{k}{\omega_{k}^{-t}-1},\omega_{k}^{-t}!\neq! 1\end{cases}!\right)\end{smallmatrix}$ 【例题】


四:【数论筛法】

1.【杜教筛】

【基本性质、定理】

  • $g(1) S(n)=\sum_{i=1}^{n}(f \ast g)(i)-\sum_{d=2}^{n} g(d) S\left(\lfloor\frac{n}{d}\rfloor\right)$(其中 $S(n)=\sum_{i=1}^{n}f(i)$)

【推导结论】

  • $S_{\mu(x)}(n)=1-\sum_{d=2}^{n}S(\lfloor\frac{n}{d}\rfloor)$ 【例题】

  • $S_{\varphi(x)}(n)=\sum_{i=1}^{n} i-\sum_{d=2}^{n}S(\lfloor\frac{n}{d}\rfloor)$ 【例题】

  • $S_{(n^{2}\varphi(n))}=\sum_{i=1}^{n} i^{3}-\sum_{d=2}^{n} d^{2} S\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$ 【例题】


五:【导数与积分】

1.【导数】

【基本性质、定理】

  • $f’(x)=\lim\limits_{\Delta x \rightarrow 0} \frac{\Delta y}{\Delta x}=\lim\limits_{\Delta x \rightarrow 0} \frac{f(x+\Delta x)-f(x)}{\Delta x}$

  • $[f(x)\pm g(x)]’=f’(x)\pm g’(x)$

  • $[f(x)g(x)]’=f’(x)g(x)+f(x)g’(x)$

  • $[\frac{f(x)}{g(x)}]’=\frac{f’(x)g(x)-f(x)g’(x)}{[g(x)]^2}$

  • $\frac{d}{dx}f(g(x))=\frac{df}{dg}(g(x))\frac{dg}{dx}(x)$

【基本初等函数的导数公式】

  • 若 $f(x)=C$ $(C$ 为常数 $)$,则 $f’(x)=0$

  • 若 $f(x)=x^{a}$ $(\alpha \in \mathbb{Q}^{*})$,则 $f’(x)=ax^{a-1}$

  • 若 $f(x)=sin(x)$,则 $f’(x)=cos(x)$

  • 若 $f(x)=cos(x)$,则 $f’(x)=-sin(x)$

  • 若 $f(x)=a^x$,则 $f’(x)=a^x\ln a$

  • 若 $f(x)=e^x$,则 $f’(x)=e^x$

  • 若 $f(x)=\log_{a}x$,则 $f’(x)=\frac{1}{x\ln a}$

  • 若 $f(x)=\ln x$,则 $f’(x)=\frac{1}{x}$

2.【积分】

【基本性质、定理】

  • $\int_{a}^{b} f(x)\mathrm{d}x=\sum\limits_{i=1}^{n} f(\xi_{i})\Delta x_i=\lim\limits_{n \rightarrow \infty} \sum\limits_{i=1}^{n} f[a+\frac{i}{n}(b-a)] \frac{b-a}{n}$

  • $\int_{a}^{b}f(x)\mathrm{d}x=\left.F(x)\right|_{a} ^{b}=F(b)-F(a)$(其中 $F’(x)=f(x)$)

  • $\int_{a}^{b}kf(x)\mathrm{d}x=k\int_{a}^{b} f(x)\mathrm{d}x$

  • $\int_{a}^{b}[f(x)\pm g(x)]\mathrm{d}x=\int_{a}^{b}f(x)\mathrm{d}x\pm \int_{a}^{b}g(x)\mathrm{d}x$

  • $\int_{a}^{b}f(x)\mathrm{d}x=\int_{a}^{c}f(x)\mathrm{d}x+\int_{c}^{b}f(x)\mathrm{d}x$

  • $\int_{a}^{b}f(x)\mathrm{d}x=-\int_{b}^{a}f(x)\mathrm{d}x$

  • $\int_{a}^{a}f(x)\mathrm{d}x=0$

【基本积分公式】

  • $\int k\,\mathrm{d} x=kx+C$ $(C$ 为常数 $)$

  • $\int x^a\,\mathrm{d}x=\frac{x^{a+1}}{a+1}+C$ $(a\neq -1)$

  • $\int \frac{\mathrm{d}x}{x}=\ln|x|+C$

  • $\int e^x\,\mathrm{d}x=e^x+C$

  • $\int a^x\,\mathrm{d}x=\frac{a^x}{\ln a}+C$

  • $\int \frac{\mathrm{d}x}{1+x^2}=arctan(x)+C$

  • $\int \frac{\mathrm{d}x}{\sqrt{1-x^2}}=arcsin(x)+C$

  • $\int cos(x)\,\mathrm{d}x=sin(x)+C$

  • $\int sin(x)\,\mathrm{d}x=-cos(x)+C$

  • $\int \frac{\mathrm{d}x}{cos^2(x)}\,\mathrm{d}x=\int sec^2(x)\,\mathrm{d}x=tan(x)+C$

  • $\int \frac{\mathrm{d}x}{sin^2(x)}\,\mathrm{d}x=\int csc^2(x)\,\mathrm{d}x=-cot(x)+C$

  • $\int sec(x)tan(x)\,\mathrm{d}x=sec(x)+C$

  • $\int csc(x)cot(x)\,\mathrm{d}x=-csc(x)+C$

  • 高等数学积分表 $\text{147}$ 个积分公式推导【高等数学吧】


【参考文献】


$To$ $be$ $continued…$



活动打卡代码 AcWing 198. 反素数

Xing_Ling
8个月前

$QAQ$

#include<cstdio>
#define Re register int
int n,a[70]={0,1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360,2001000000};
int main(){
    scanf("%d",&n);
    for(Re i=69;i;--i)if(a[i]<n)return !printf("%d",a[i]);
}



Xing_Ling
9个月前

【学习笔记】动态规划—各种 DP 优化

其实我就是来宣传博客的 $\text{QAQ}$

【大前言】

个人认为贪心,$dp$ 是最难的,每次遇到题完全不知道该怎么办,看了题解后又瞬间恍然大悟(TAT)。这篇文章也是花了我差不多一个月时间才全部完成。


【进入正题】

用动态规划解决问题具有空间耗费大时间效率高的特点,但也会有时间效率不能满足要求的时候,如果算法有可以优化的余地,就可以考虑时间效率的优化。


【DP 时间复杂度的分析】

$DP$ 高时间效率的关键在于它减少了“冗余”,即不必要的计算或重复计算部分,算法的冗余程度是决定算法效率的关键。而动态规划就是在将问题规模不断缩小的同时,记录已经求解过的子问题的解,充分利用求解结果,避免了反复求解同一子问题的现象,从而减少“冗余”。
但是,一个动态规划问题很难做到完全消除“冗余”。

下面给出动态规划时间复杂度的决定因素:

时间复杂度 $=$ 状态总数 $×$ 每个状态转移的状态数 $×$ 每次状态转移的时间


【DP 优化思路】

一:减少状态总数

$(1).$ 改进状态表示

$(2).$选择适当的规划方向

二:减少每个状态转移的状态数

$(1).$ 四边形不等式和决策的单调性

$(2).$ 决策量的优化

$(3).$ 合理组织状态

$(4).$ 细化状态转移

三:减少状态转移的时间

$(1).$ 减少决策时间

$(2).$ 减少计算递推式的时间

(上述内容摘自 《动态规划算法的优化技巧》毛子青 ,想要深入了解其思想的可以去看看这篇写得超级好的论文。)


看到这里是不是已经感觉有点蒙了呢?
本蒟蒻总结了一个简化版本:


【DP 三要点】

在推导 $dp$ 方程时,我们时常会感到毫无头绪,而实际上 $dp$ 方程也是有迹可循的,总的来说,需要关注两个要点:状态决策转移。其中 “状态” 又最为关键,决策最为复杂。

【状态】

关于 “状态” 的优化可以从很多角度出发,思维难度及其高,有时候状态选择的好坏会直接导致出现暴零和满分的分化。

【决策】

“状态” 不同,“决策” 优化则有着大量模板化的东西,在各大书籍,文章上你都可以看到这样的话:只要是形如 $XXX$ 的状态转移方程,都可以用 $XXX$ 进行优化。

【转移】

“转移” 则指由最优决策点得到答案的转移过程,其复杂度一般较低,通常可以忽略,但有时也需要特别注意并作优化。

本文将会重点针对 “决策” 优化部分作一些总结,记录自己的感悟和理解。


$$
QAQ
$$


一:【矩阵优化 DP】

$updata$ 之后由于篇幅过大,已搬出。。。。。

【学习笔记】动态规划—矩阵递推加速

补充:其实质是优化 “决策”


$$
QAQ
$$


二:【数据结构优化 DP】

【前言】

在一些 $dp$ 方程的状态转移过程中,我们通常需要在某个范围内进行择优,选出最佳决策点,这往往可以作为 $dp$ 优化的突破口。

数据结构的使用较灵活,没有一个特定的模板,需要根据具体情况而定,选择合适的方案。由于状态转移总是伴随着区间查询最值,区间求和等操作,即动态区间操作,所以平衡树可以作为一个有用的工具,但考虑到代码复杂度,使用树状数组或者线段树将会是一个不错的选择。。

其实质是优化 “决策”


1.【维护合适的信息】

$The$ $Battle$ $of$ $Chibi$ $[UVA12983]$ 为例,大概题意就是计算在给定的序列中严格单调递增子序列的数量,并对 $1e9
+7$ 取模,给定序列长度小于等于 $1000$ 。

方程应该是比较好推的,用 $dp[i][j]$ 表示由序列中在 $j$ 之前的数构成并以 $a[j]$ 结尾的子序列中,长度为 $i$ 的子序列的数量。则:$dp[i][j]=\sum dp[i-1][k]$ ,其中 $k < j$ $且$ $a[k] < a[j]$ 。

对于决策点 $dp[i-1][k]$ 这里出现了 $3$ 个信息:
$(1).$ 在原序列中的位置 $k<j$ 。
$(2).$ $a[k]<a[j]$ 。
$(3).$ $dp[i-1][k]$ 的和。

对于 $(1)$,可以用枚举的顺序解决,剩下的两个信息即是数据结构需要维护的信息。

对于每一次 $dp[i]$ 的决策,可以将 $a[j]$ 作为数据结构维护的关键字, $dp[i-1][j]$ 作为权值,加入 $-inf$ 后离散化,得到一个大小为 $N+1$ 的数组并在上面建立树状数组,每次计算 $dp[i][j]$ 时查询前面已经加入的且关键字小于 $a[j]$ 的 $dp[i-1][k]$ 总和(即区间查询),然后把 $dp[i-1][j]$ 加入树状数组(单点查询)。

时间复杂度为 $O(logn)$。

当问题涉及到的操作更复杂时,树状数组无法维护所需要的信息,就只有用线段树了。这道题较简单,所以选择了代码复杂度更低的树状数组。


2.【Code】

#include<algorithm>
#include<cstring>
#include<cstdlib>//UVA抽风,加上这个就好了
#include<cstdio>
#define Re register int
using namespace std;//UVA抽风,还要加这个
const int N=1005,P=1e9+7;
int n,m,T,k,ans,cnt,a[N],b[N],C[N],dp[N][N];
inline void add(Re x,Re v){while(x<=n+1)(C[x]+=v)%=P,x+=x&-x;}
inline int ask(Re x){Re ans=0;while(x)(ans+=C[x])%=P,x-=x&-x;return ans%P;}
int main(){
    scanf("%d",&T);
    for(Re o=1;o<=T;++o){
        scanf("%d%d",&n,&m),ans=0,cnt=n;
        memset(dp,0,sizeof(dp));
        for(Re i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i],dp[1][i]=1;
        sort(b+1,b+n+1);//离散
        cnt=unique(b+1,b+n+1)-b-1;//去重
        for(Re i=2;i<=m;++i){
            memset(C,0,sizeof(C));//每次都要清空,重新开始维护
            for(Re j=1;j<=n;++j)
                dp[i][j]=ask((k=lower_bound(b+1,b+cnt+1,a[j])-b)-1),add(k,dp[i-1][j]);
        }   
        for(Re j=1;j<=n;++j)(ans+=dp[m][j])%=P;
        printf("Case #%d: %d\n",o,ans);
    }
}

3.【题目链接】

【简单题】

【高档题】


$$
QAQ
$$


三:【决策单调性】

【前言】

形如 $dp[i]=min(dp[j]+w(j,i))$ $(L_i \leqslant j \leqslant R_i)$ 的 $dp$ 方程被称作 $1D/1D$ 动态规划,其中 $L_i$ 和 $R_i$ 单调递增,$w(j,i)$ 决定着优化策略选择。

针对决策点具有的特性,可以大大降低寻找最优决策点的时间。

其实质是优化 “决策”


1.【定义】

【决策单调性】

设 $j_0[i]$ 表示 $dp[i]$ 转移的最优决策点,那么决策单调性可描述为 $\forall i \leqslant j,j_0[i] \leqslant j_0[j]$。也就是说随着 $i$ 的增大,所找到的最优决策点是递增态(非严格递增)。

【四边形不等式】

$w(x,y)$ 为定义在整数集合上的一个二元函数,若 $\forall a \leqslant b \leqslant c \leqslant d,w(a,c)+w(b,d) \leqslant w(a,d)+w(b,c)$,那么函数 $w$ 满足四边形不等式

为什么叫做四边形不等式呢?在 $w(x,y)$ 函数的二维矩阵中挖一块四边形,左上角右下角 小于等于 左下角右上角


2.【定理及其证明】

定理 (1):四边形不等式的另一种定义

$w(x,y)$ 为定义在整数集合上的一个二元函数,若 $\forall a < b,w(a,b)+w(a+1,b+1) \leqslant w(a+1,b)+w(a,b+1)$,那么函数 $w$ 满足四边形不等式

$证明:$

$\because \forall a < c,w(a,c)+w(a+1,c+1) \leqslant w(a+1,c)+w(a,c+1)$

$\therefore \forall a+1 < c,w(a+1,c)+w(a+2,c+1) \leqslant w(a+2,c)+w(a+1,c+1)$

$上下两式相加,有:$ $w(a,c)+w(a+2,c+1) \leqslant w(a,c+1)+w(a+2,c)$

$以此类推$ $\forall a \leqslant b\leqslant c,w(a,c)+w(b,c+1) \leqslant w(a,c+1)+w(b,c)$

$同理$ $\forall a \leqslant b \leqslant c \leqslant d,w(a,c)+w(b,d) \leqslant w(a,d)+w(b,c)$

定理 (2):决策单调性

$1D/1D$ 动态规划具有决策单调性当且仅当函数 $w$ 满足四边形不等式 时成立。

$证明:$

$\because$ $j_0[i]$ $在$ $dp[i]$ $的决策点中最优$
$\therefore$ $\forall i \in [1,N],\forall j \in [0,j_0[i]-1],dp[j_0[i]]+w(j_0[i],i) \leqslant dp[j]+w(j,i)$

$易知$ $\forall i’ \in [i+1,N]$,$均满足$ $j<j_0[i]<i<i’$。
$又$ $\because$ $函数$ $w$ $满足四边形不等式$
$\therefore$ $w(j,i)+w(j_0[i],i’) \leqslant w(j,i’)+w(j_0[i],i)$

$移项得:$ $w(j_0[i],i’)-w(j_0[i],i) \leqslant w(j,i’)-w(j,i)$

$与第一个式子相加,有:$ $dp[j_0[i]]+w(j_0[i],i’) \leqslant dp[j]+w(j,i’)$

最后的式子含义是:把 $j_0[i]$ 作为 $dp[i’]$ 的决策点,一定比小于 $j_0[i]$ 的任意一个 $j$ 都要更好。也就是说,$dp[i’]$ 的最优决策点不可能小于 $j_0[i]$ ,即 $j_0[i’] \geqslant j_0[i]$,所以方程 $dp$ 具有决策单调性


3.【证明决策单调性】

这里以 玩具装箱 $toy$ $[P3195]$ 为例(因为这个比较好证 QAQ),先来证一波决策单调性

设 $S[n]=\sum _{i=1}^n (C[i]+1)$,用 $dp[i]$ 表示装好前 $i$ 个的最小花费,则 $dp$ 方程为:$dp[i]=min(dp[j]+(S[i]-S[j]-1-L)^2)$。

很明显,这个方程是一个 $1D/1D$ 动态规划方程,其中 $w(i,j)=(S[i]-S[j]-1-L)^2$。

(注意在四边形不等式中的 $j$ 不是 $i$ 决策点,可以理解为 $i’$。而 $w(i,j)$ 的值可以理解为是由已完成的状态 $dp[i]$ 转移到 $dp[j]$ 所带有的附加价值)。

证明:设 $Q=S[i]-S[j]-1-L$

$\therefore w(i,j)=(S[i]-S[j]-1-L)^2=Q^2$

$$\begin{aligned}
\therefore w(i+1,j+1)=&(S[i+1]-S[j+1]-1-L)^2\
=&((S[i]+C[i+1]+1)-(S[j]+C[j+1]+1)-1-L)^2\
=&(Q+C[i+1]-C[j+1])^2
\end{aligned}
$$

$$
\begin{aligned}
w(i,j+1)=&(S[i]-S[j+1]-1-L)^2\
=&(S[i]-(S[j]+C[j+1]+1)-1-L)^2\
=&(Q-C[j+1]-1)^2
\end{aligned}
$$

$$
\begin{aligned}
w(i+1,j)=&(S[i+1]-S[j]-1-L)^2\
=&((S[i]+C[i+1]+1)-S[j]-1-L)^2\
=&(Q+C[i+1]+1)^2
\end{aligned}
$$

$\therefore w(i,j)+w(i+1,j+1)=2X^2+2C[i+1]X-2C[j+1]X+C[i+1]^2-2C[i+1]C[j+1]+C[j+1]^2$

$\therefore w(i+1,j)+w(i,j+1)=2X^2+2C[i+1]X-2C[j+1]X+C[i+1]^2+2C[i+1]+2C[j+1]+C[j+1]^2+2$

$\therefore w(i,j)+w(i+1,j+1)-w(i+1,j)+w(i,j+1)=-2(C[i+1]+1)(C[j+1]+1)$

又$\because C[i],C[j] \geqslant 1$

$\therefore -2(C[i+1]+1)(C[j+1]+1) \leqslant -8$

$\therefore w(i,j)+w(i+1,j+1) \leqslant w(i+1,j)+w(i,j+1)$

由定理 $(1)$ 可知,函数 $w$ 满足四边形不等式
又由定理 $(2)$可知, 方程 $dp$ 具有决策单调性

在实战中,通常使用打表的形式来验证 $w$ 函数的递变规律。


4.【实现方法】

关于决策单调性和斜率优化这两个东西的分类似乎有争议,有人说斜优是决策单调性的一种(好像就是二分栈来着?),也有人说斜优是针对斜率进行优化,是决策单调性是其一种方案(你谷某管理大大),我支持前一种说法。

($ps.$ 对于此处及以下语言不严谨处,大家可以认真思考并给予建议,待日后对其理解加深后再行修改。)

这里选择不同的例题将二者分开讲。

【二分栈】

二分栈,顾名思义就是二分加栈。

用栈维护单调的决策点,二分找到最优决策点。

$Lightning$ $Conductor$ $[P3515]$ 为例,题目大意就是在给定长度为 $n$ 的序列 $a$ 中,对于每一个 $i$,找到最小的自然数 $p_i$ 满足对于任意的 $j \in [1,n]$,均有 $a_j \leqslant a_i+p_i-\sqrt{\left|i-j\right|}$ 。

把这个式子变下形:$p_i \geqslant a_j-a_i+\sqrt{\left|i-j\right|}$ 。
即 $p_i=max { a_j+\sqrt{\left|i-j\right|} } -a_i$
即 $p_i = max { max{a_j+\sqrt{i-j}}(j \in [1,i]),max{a_j+\sqrt{j-i}}(j \in [i+1,n]) }-a_i$

可以发现里面两个 $max$ 可以视为同一个问题(只要把序列翻转一下就可以了),所以只需要考虑求出对于每一个 $i$ 的 $max{ a_j+\sqrt{i-j} }$,其中 $j \in [1,i]$。

设 $y_j=a_j+\sqrt{i-j}$

那么我们会得到 $n$ 个关于 $i$ 函数,$p_i=max{ y_j }$。

将样例画出来,如图:

可知当 $i=4$ 时,直线 $x=4$ 与 $y1=a_1+\sqrt{x-1}$ 的交点即为 $p_4$。

在上图中,对于任意 $j \in [1,n]$ ,$y1$ 总是在最上面,也就是说下面的其他函数可以踢掉不要,但由于 $sqrt$ 函数的增速递减,会出现如图中 $y2,y4$ 的情况,即存在一个交点使得在该点两边时两条直线的位置关系不同。此时如果没有上面的 $y1$,$y2,y4$ 都有可能成为答案,所以不能乱踢。

看下面这种情况:

设 $k_1$ 为 $y_1,y_2$ 的交点,$k_2$ 为 $y_2,y_3$ 的交点。
此时 $k_1 > k_2$,可以发现 $y_2$ 始终在其他直线的下面,可以放心的将其踢掉。

所以维护出来的决策集合大概就是酱紫的:

对于不同的 $i$ 来说,都有一个互不不同的直线在最上方,所以该决策集合里的直线都是有用的。可以从图中看出,最优决策点单调递增(决策单调性的数学证明较麻烦,本人能力不足,不作探讨)。

维护决策集合用单调队列,查找直线交点用二分,随便搞搞就行了。

时间复杂度为 $O(nlogn)$。

【分治】

为方便描述,用 $dp[a,b]$ 表示 $dp[a],dp[a+1],dp[a+2]…dp[b]$。

假设我们已知 $dp[l,r]$ 的最优决策点均位于 $[L,R]$,再设 $dp[mid]$ 的最优决策点为 $j_0$,其中 $mid=(l+r)/2$。根据决策单调性的定义可知:
$dp[l,mid-1]$ 的最优决策点位于 $[L,k]$,
$dp[mid+1,r]$ 的最优决策点位于 $[k,R]$。
原问题变成了两个规模更小的同类型问题,所以可以用分治来对 $dp$ 进行优化。

分治的话理解和代码都要简单一些,但在某些情况下可能要被卡,时间复杂度会严重退化,所以还是二分栈的实用性更高。

还是以 $Lightning$ $Conductor$ $[P3515]$ 为例,每次的分治中先暴力扫一遍找到 $p[mid=(l+r)/2]$ 的最优决策点 $j_0$,然后做一下左边,再做一下右边,然后 $…$ 然后 $…$ 就没了。

时间复杂度为 $O(nlogn)$。


5.【Code】

二分栈

#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
using namespace std;
const int N=5e5+3;
int i,j,n,h,t,a[N],Q[N],Poi[N];
double p[N],sqr[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline double Y(Re i,Re j){return a[j]+sqr[i-j];}
inline int find_Poi(int j1,int j2){//找到两个直线的交点i 
    Re l=j2,r=n,mid,ans=n+1;//为了处理两个直线没有交点的情况,用一个变量记录答案
    while(l<=r){
        mid=l+r>>1;
        if(Y(mid,j1)<=Y(mid,j2))ans=mid,r=mid-1;
//当前这个位置i使得直线j1的纵坐标小于直线j2的纵坐标,说明这个点i在交点的右方,所以右边界要缩小
        else l=mid+1;
    }
    return ans;
}
inline void sakura(){
    h=1,t=0;
    for(i=1;i<=n;++i){//由于i本身也是一个决策点,所以要先入队再取答案择优
        while(h<t&&Poi[t-1]>=find_Poi(Q[t],i))--t;//如果出现了上述可踢的情况,出队
        Poi[t]=find_Poi(Q[t],i),Q[++t]=i;
        while(h<t&&Poi[h]<=i)++h;
//找到第一个位置j使得直线Q[j]与直线Q[j+1]的交点大于i,
//那么直线Q[j]就是i前面在最上面的直线,即答案,自己画个图模拟一下就懂了
        p[i]=max(p[i],Y(i,Q[h]));
    }
}
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(a[i]),sqr[i]=sqrt(i);
    sakura();
    for(Re i=1;i<n-i+1;++i)swap(a[i],a[n-i+1]),swap(p[i],p[n-i+1]);
    sakura();
    for(Re i=n;i;--i)printf("%d\n",(int)ceil(p[i])-a[i]);
}

分治

#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
using namespace std;
const int N=5e5+3;
int i,j,n,h,t,a[N],Q[N],Poi[N];
double tmp,p[N],sqr[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void sakura(Re l,Re r,Re L,Re R){
    if(l>r)return;
    Re mid=l+r>>1,j0;double mx=0;
    for(Re j=L;j<=mid&&j<=R;++j)
    //暴力找p[i]的最优决策点j0,而其决策点j必须满足j<=i,即此处的j<=mid
        if((tmp=a[j]+sqr[mid-j])>mx)mx=tmp,j0=j;
    p[mid]=max(p[mid],mx);
    sakura(l,mid-1,L,j0),sakura(mid+1,r,j0,R);
}
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(a[i]),sqr[i]=sqrt(i);
    sakura(1,n,1,n);
    for(Re i=1;i<n-i+1;++i)swap(a[i],a[n-i+1]),swap(p[i],p[n-i+1]);
    sakura(1,n,1,n);
    for(Re i=n;i;--i)printf("%d\n",(int)ceil(p[i])-a[i]);
}

6.【题目链接】

【中档题】

【高档题】


$$
QAQ
$$


四:【单调队列优化 DP】


【前言】

形如 $dp[i]=max/min { dp[j]+funtion(i)+function(j) }$ 的 $dp$ 方程均可尝试使用单调队列优化。

单调栈单调队列给我们展现出了一种思想:在保证正确性的前提下,及时排除不可能的决策点,保持决策集合内部的有序性和查找决策的高效性。之前的二分栈,此处的单调队列优化,和后面的斜率优化都是以此为核心来运作的。

其实质是优化 “决策”


1.【单调队列的简单运用】

【T1】

琪露诺 $[P1725]$(盗版滑动窗口QAQ)。

【题目大意】

在给定序列中找出一条路径使其经过的点之和最大,且每次可走的距离在给定区间 $[l,r]$ 以内。

【分析】

方程非常简单:$dp[i]=max{ dp[j]+a[i] } (i-r \leqslant j \leqslant i-l)$ 。

在某一次决策中,由于决策点 $j$ 只可能在 $[i-l,i-r]$ 这一段区间内,可以只将这些点放入决策集合。
而 $l,r$ 是定值,当 $i$ 不断增大时,之前小于 $i-l$ 的 $j$ 现在还是小于 $i-l$,所以可以永远地踢掉。
若 $j < j’$ 且 $dp[j] \leqslant dp[j’]$,那么 $dp[j]$ 也可以永远地踢掉。为什么呢? $j$ 在 $j’$ 的前面,一定会先成为不合法决策点,而 $j$ 的价值又比 $j’$ 小,因此留下来只是浪费扫描的时间。

最终维护出了一个价值递减的单调队列。

【Code】
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using std::max;
const int N=2e5+3;
int n,l,r,h=1,t,a[N],Q[N];
long long ans=-2e9,dp[N]; 
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
    in(n),in(l),in(r);
    memset(dp,-127,sizeof(dp));
    Q[++t]=0;
    for(Re i=0;i<=n;++i)in(a[i]);
    dp[0]=a[0];
    for(Re i=l;i<=n;i++){//注意枚举起点是l不是1
        while(h<=t&&dp[Q[t]]<=dp[i-l])--t;//维护单调递减
        Q[++t]=i-l;//入队
        while(h<=t&&Q[h]<i-r)++h;//保证决策点合法
        dp[i]=dp[Q[h]]+a[i];//取出最优决策点
        if(i>=n-r)ans=max(ans,dp[i]);
    }
    printf("%lld",ans);
}

【T2】

$fence$ $[POJ1821]$

【题目大意】

$M$ 个工人要对 $N$ 块木板进行粉刷。工人 $i$ 要么不刷,要么就刷不超过 $L_i$ 块并且包含 $S_i$ 的连续一段木板,每粉刷一块木板有 $P_i$ 的报酬。要求使总报酬最大。

【分析】

$S_i$ 的散乱分布非常讨厌,所以先把工人按 $S_i$ 排个序。

主要信息有“工人序号”,“木板序号”,“报酬”这三个,而其中“报酬”为所求答案,可以用 $dp[i][j]$ 表示前 $i$ 个工人刷完前 $j$ 块木板所得总报酬。

考虑状态转移:
第 $i$ 个工人可以跳过不刷木板,也可以跳过第 $j$ 块木板不刷,因此先在 $dp[i-1][j]$ 和 $dp[i][j-1]$ 当中取个最大值。
工人 $i$ 想要粉刷的区间 $[k+1,j]$ 必须包括 $S_i$,并且区间长度要小于等于 $L_i$。
所以得出 $dp$ 转移方程:$dp[i][j]=max { dp[i-1][j],dp[i][j-1],dp[i-1][k]+P_i*(j-k) }$,其中 $S_i \leqslant j$ 且 $k \in [j-L_i,S_i-1]$。

$k$ 为决策点,$P_i*j$ 为定值可以单独提出来,所以实际上就是上面琪露诺 $[P1725]$一样的类型,只是加了一维而已。

最终维护出了一个 $dp[i-1][k]-P_i*k$ 递减的单调队列。

【Code】
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=16005;
struct QAQ{int L,P,S;}a[105];
int n,m,i,j,k,Q[N],W[N],dp[105][N];
inline bool cmp(QAQ a,QAQ b){return a.S<b.S;}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        for(i=1;i<=m;++i)scanf("%d%d%d",&a[i].L,&a[i].P,&a[i].S);
        std::sort(a+1,a+m+1,cmp);
        for(i=1;i<=m;++i){
            Re l=1,r=0,tmp,Si=a[i].S,Li=a[i].L,Pi=a[i].P;
            for(k=max(0,Si-Li);k<Si;++k){
            //k+1为工人i开始刷的位置,max(1,Si-Li+1)<=k+1<=Si
                tmp=dp[i-1][k]-Pi*k;
                while(l<=r&&Q[r]<=tmp)--r;
                Q[++r]=tmp,W[r]=k;
            }
            for(j=1;j<=n;++j){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                if(Si+Li>j&&j>=Si){//Si+Li-1>=j>=Si
                    while(l<=r&&W[l]+Li<j)++l;//W[r]+1+Li-1<j
                    if(l<=r)dp[i][j]=max(dp[i][j],Q[l]+Pi*j);
                }
            }
        }
        printf("%d\n",dp[m][n]);
    }
}

2.【单调队列优化多重背包】

先来回顾一下多重背包问题。

用 $v,w,c$ 分别表示物品重量,价值,数量,$n$ 为物品数量,$V$ 为背包容量。$dp$ 方程为:$dp[j]=max$ ${dp[j-k*v[i]]+k*w[i]}$ $(j\in[v[i],V],$ $k\in[1,min(c[i],j/v[i])])$

还可以用二进制拆分来进行优化,但就是有这样一道题,连 $log$ 都要卡:多重背包 $[CodeVS5429]$。所以还需要考虑更高效的算法。

但说来说去似乎都和单调队列扯不上关系。

为何?

观察 $dp[j]$ 和 $dp[j-1]$ 决策集合:
$dp[j]: {j \% v[i]…j-2*v[i],j-v[i] }$
$dp[j-1]: {(j-1) \% v[i]…(j-1)-2*v[i],(j-1)-v[i] }$

$dp[j]$ 的每一个决策点都与 $dp[j-1]$ 不同,很难根据 $dp[j-1]$ 的决策集合转移成 $dp[j]$ 的决策集合。

再看 $dp[j]$ 和 $dp[j-v[i]]$:

$dp[j]: { j-c[i]*v[i]…j-2v[i],j-v[i] }$

$dp[j-v[i]]: { j-(c[i]+1)*v[i]…j-3v[i],j-2v[i] }$

可以发现上面只是比下面的区别仅仅在于 $j-(c[i]+1)*v[i]$ 和 $j-v[i]$ ,恰好满足单调队列的一个特性:但有新的决策出现时,决策点集合中会去掉一部分不合法的,再加上一部分新来的。

所以我们可以按照 $j%v[i]$ 的余数来分一下:

$dp[j]$ $(j\%v[i]=0):{0,v[i],2v[i]…j-2v[i],j-v[i]}$
$dp[j]$ $(j\%v[i]=1):{1,v[i]+1,2v[i]+1…j-2v[i],j-v[i] }$
$…$
$dp[j]$ $(j\%v[i]=v[i]-1):{v[i]-1,2v[i]-1…j-2v[i],j-v[i]}$

设 $j=p*v[i]+r$,那么原方程可改为: $dp[{p*v[i]+r}]=max{ dp[{r+k*v[i]}]+(p-k)*{w[i]} }$ $(r \in [0,{v[i]-1}],$ $p\in [1,\lfloor(V-r)/{v[i]}\rfloor],$ $k \in [p-min( \lfloor {V/w[i]}\rfloor ,{c[i]}),p])$
只要在最外层将 $i,r,p$ 都枚举出来,这就是一个标准的单调队列可优化方程,用类似 $fence$ $[POJ1821]$ 的方法维护即可。

时间复杂度为 $O(N*V)$ 。

【Code】

#include<cstdio>
#define Re register int
const int N=7003,M=7003;
int n,h,t,V,mp,tmp,v[N],w[N],c[N],Q[N],K[N],dp[M];
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
inline int min(Re a,Re b){return a<b?a:b;}
int main(){
    in(n),in(V);
    for(Re i=1;i<=n;++i)in(v[i]),in(w[i]),in(c[i]);
    for(Re i=1;i<=n;++i)
        for(Re r=0;r<v[i];++r){
            h=1,t=0,mp=(V-r)/v[i];
            for(Re p=0;p<=mp;++p){
                tmp=dp[p*v[i]+r]-w[i]*p;
                while(h<=t&&Q[t]<=tmp)--t;
                Q[++t]=tmp,K[t]=p;
                while(h<=t&&p-K[h]>min(c[i],V/v[i]))++h;
                dp[p*v[i]+r]=max(dp[p*v[i]+r],Q[h]+p*w[i]);
            }
        }
    printf("%d",dp[V]);
}

3.【题目链接】

【简单题】

【中档题】


$$
QAQ
$$


五:【斜率优化 DP】

由于篇幅过大,已搬出。。。。。

【学习笔记】动态规划—斜率优化DP(超详细)

补充:其实质是优化 “决策”


$$
QAQ
$$


【参考文献】

(本文部分内容摘自以下文章)



活动打卡代码 AcWing 244. 谜一样的牛

Xing_Ling
9个月前

$QAQ$

#include<cstdio>
#define Re register int
const int N=1e5+3;
int i,n,l,r,mid,a[N],C[N],ans[N];
inline void in(int &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
inline void add(int x,int y){while(x<=n)C[x]+=y,x+=x&(-x);}
inline int ask(int x){int ans=0;while(x)ans+=C[x],x-=x&(-x);return ans;}
int main(){
    in(n);add(1,1);++a[1];
    for(i=2;i<=n;++i)in(a[i]),add(i,1),++a[i];
    for(i=n;i>=1;--i){
        l=a[i],r=n;
        while(l<r){
            mid=l+r>>1;
            if(ask(mid)<a[i])l=mid+1;
            else r=mid;
        }
        add(l,-1);ans[i]=l;
    }
    for(i=1;i<=n;++i)printf("%d\n",ans[i]);
}



Xing_Ling
9个月前

$QAQ$

#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,T,a,l,r,f;LL C1[1000003],C2[1000003];char op;
inline void in(int &x){
    x=f=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f)x=-x;
}
inline void add(int x,int y){Re i=x;while(i<=n)C1[i]+=y,C2[i]+=(LL)x*y,i+=i&(-i);}
inline LL ask_line(int x){
    LL ans=0;Re i=x;
    while(i)ans+=C1[i]*(x+1)-C2[i],i-=i&(-i);
    return ans;
}
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;i++)in(a),add(i,a-l),l=a;
    while(T--){
        scanf(" %c",&op),in(l),in(r);
        if(op=='C')in(a),add(l,a),add(r+1,-a);
        else printf("%lld\n",ask_line(r)-ask_line(l-1));
    }
}



Xing_Ling
9个月前

$QAQ$

#include<cstdio>
#define LL long long
const int N=1e5+3;
int n,T,a,b,c,f;LL C[N];char op;
inline void in(int &x){
    x=f=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f)x=-x;
}
inline void add_c(int x,int y){while(x<=n)C[x]+=y,x+=x&(-x);}
inline LL ask_x(int x){
    LL ans=0;
    while(x)ans+=C[x],x-=x&(-x);
    return ans;
}
int main(){
    in(n),in(T);
    for(int i=1;i<=n;i++)in(a),add_c(i,a-b),b=a;
    while(T--){
        scanf(" %c",&op),in(a);
        if(op=='C')in(b),in(c),add_c(a,c),add_c(b+1,-c);
        else printf("%lld\n",ask_x(a));
    }
}


活动打卡代码 AcWing 241. 楼兰图腾

Xing_Ling
9个月前

$QAQ$

#include<cstdio>
#define LL long long
#define Re register int
const int N=2e5+5;
int n,m,x,y,op,a[N],f1[N],f2[N];LL ans;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct FIT{
    int C[N];
    inline void add(Re x){while(x<=n)++C[x],x+=x&-x;}
    inline int ask(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}T1,T2;
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(a[i]);
    for(Re i=1;i<=n;++i)f1[i]=T1.ask(a[i]-1),T1.add(a[i]);
    for(Re i=n;i>=1;--i)f2[i]=T2.ask(a[i]-1),T2.add(a[i]);
    for(Re i=2;i<n;++i)ans+=(LL)(i-1-f1[i])*(n-i-f2[i]);
    printf("%lld ",ans),ans=0;
    for(Re i=2;i<n;++i)ans+=(LL)f1[i]*f2[i];
    printf("%lld",ans);
}


活动打卡代码 AcWing 240. 食物链

Xing_Ling
9个月前

$QAQ$

#include<algorithm>
#include<cstdio>
#define Re register int
int i,n,k,a,b,c,b1,b2,b3,c1,c2,c3,fu,ans,f[150005];
inline void in(Re &x){
    x=fu=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline int find(Re x){if(x!=f[x])f[x]=find(f[x]);return f[x];}
int main(){
    in(n),in(k);
    while(i<=3*n)f[i]=i++;
    while(k--){
        in(a),in(b),in(c);
        if(b>n||c>n){++ans;continue;}
        if(a>1){
            if((b==c)||(b2=find(b+n))==(c3=find(c+2*n))||(b3=find(b+2*n))==(c1=find(c))||b3==c3)++ans;
            else f[find(b)]=f[c3],f[find(c+n)]=f[b3],f[b2]=f[c1]; 
        }
        else{
            if((b1=find(b))==(c3=find(c+2*n))||(b2=find(b+n))==c3||(c1=find(c))==(b3=find(b+2*n))||(c2=find(c+n))==b3)++ans;
            else f[b3]=f[c3],f[b1]=f[c1],f[b2]=f[c2];
        }
    }
    printf("%d",ans);
}


活动打卡代码 AcWing 237. 程序自动分析

Xing_Ling
9个月前

$QAQ$

#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e6+3;
int n,m,T,b[N<<1],fa[N<<1];
struct QAQ{int x,y,e;inline bool operator<(QAQ O)const{return e>O.e;}}a[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline int judge(){
    for(Re i=1;i<=m;++i)
        if(a[i].e)fa[find(lower_bound(b+1,b+n+1,a[i].x)-b)]=find(lower_bound(b+1,b+n+1,a[i].y)-b);
        else if(find(lower_bound(b+1,b+n+1,a[i].x)-b)==find(lower_bound(b+1,b+n+1,a[i].y)-b))return 0;
    return 1;
}
int main(){
    in(T);
    while(T--){
        in(m),n=0;
        for(Re i=1;i<=m;++i)in(a[i].x),in(a[i].y),in(a[i].e),b[++n]=a[i].x,b[++n]=a[i].y;
        sort(b+1,b+n+1),sort(a+1,a+m+1);
        n=unique(b+1,b+n+1)-b-1;
        for(Re i=1;i<=n;++i)fa[i]=i;
        puts(judge()?"YES":"NO");
    }
}