2.25-3.2

1. 计算几何

1.1 二维几何基础

struct Point{    double x,y;    Point(double x = 0, double y = 0):x(x),y(y){}}typedef Point Vector;Vector operator + (Vector A ,Vector B){ return Vector(A.x+B.x,A.y+B.y); }Vector operator - (Vector A ,Vector B){ return Vector(A.x-B.x,A.y-B.y); }Vector operator / (Vector A ,Vector B){ return Vector(A.x/B.x,A.y/B.y); }Vector operator * (Vector A ,Vector B){ return Vector(A.x*B.x,A.y*B.y); }bool operator < (const Point &a,const Point &b){    return a.x
    

1.1.1 基本运算

double Dot(Vector A,Vector B){ return A.x*B.x+A.y*B.y; }double Length(Vector A){return sqrt(Dot(A,A)); }double Angle(Vector A,Vector B){ return acos(Dot(A,B)/Length(A)/Length(B)); }double Cross(Vector A,Vector B){ return A.x*B.y - A.y*B.x;}double Area2(Point A,Point B,Point C){ return Cross(B-A,C-A); }Vector Rotate(Vector A,double rad){    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}Vector Normal(Vector A){    double L = Length(A);    return Vector(-A.y/L,A.x/L);}

1.1.2 点与直线

//直线用P = P0+tv表示//调用前确保两条直线P+tv,Q+tw有唯一交点，当且仅当Cross(v,w)非0Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){    Vector u = P-Q;    double t = Cross(w,u)/Cross(v,w);    return p+v*t;}double DistanceToLine(Point P,Point A,Point B){    Vector v1 = B-A,v2 = P-A;    return fabs(Cross(v1,v2))/Length(v1);//不取绝对值得到有向距离}double DistanceToSegment(Point P,Point A,Point B){    if(A==B)return Length(P-A);    Vector v1 = B-A,v2 = P-A,v3 = P-B;    if(dcmp(Dot(v1,v2)) < 0)return Length(v2);    else if(dcmp(Dot(v1,v3)) > 0)return Length(v3);    else return fabs(Cross(v1,v2))/Length(v1);}//点在直线上的投影Point GetLineProjection(Point p,Point A,Point B){    Vector v = B-A;    return A+v*(Dot(v,P-A)/Dot(v,v));}//线段相交 严格相交bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){    double c1 = Cross(a2-a1,b1-a1),c2 = Cross(a2-a1,b2-a1);    double c3 = Cross(b2-b1,a1-b1),c4 = Cross(b2-b1,a2-b1);    return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;}//不严格相交，还没有补充bool Onsegment(Point p,Point a1,Point a2){    return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p)) < 0;}

1.1.3 多边形

//多边形double ConvexPolygonArea(Point *p,int n){    double area = 0;    for(int i=1;i

1.2 与圆有关的计算问题

2. CF-1130

D题和E题

• 火车只能顺时针走
• 一次只能从一个地方拿走一个，所以对于当前 j ，如果有cnt[j]个糖果，那么必须经过它cnt[j]次，而且把需要传递距离最近的那个留到最后。这样该点需要走的最远距离就是(cnt[j]-1)*n + last ，last为最后一个要走的距离。
• \(O(n^2)\) 遍历所有。输出答案

#include 
    
     using namespace std;const int inf = 0x3f3f3f3f;const int N = 5010;int n,m,cnt[N],last[N];int main(){    cin>>n>>m;    memset(last,0x3f,sizeof last);    for(int i=0,a,b;i
    

3. CF-1038

• 这题很简单，贪心就可以了，奈何我脑痴把数组下标写的小了，浪费了二十分钟

• 每个数给答案的贡献无非只有两种，一种正的，一种负的，让我们想想极端的情况。假如这个序列整个都是正的，那我们需要一个数来充当被减数，然后之后整个序列就可以进行运算了。当我们运算出当前结果时，可以想到的是，该结果可以进行内部取反，来迎合下一次操作。（妙啊）

#include 
    
     using namespace std;const int N = 500010;typedef long long ll;ll a[N];int n;int main(){    cin>>n;    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);    if(n==1)cout<
     
      <
      
       0)cnt_pos++;            else if(a[i]<0)cnt_neg++;        }        if(cnt_pos&&cnt_neg)            cout<
       
        <
       
      
     
    

4. CF-1025

• 这个题差点就想出来了，然而我太着急。
• 每组两个数字，从中取出一个，然后整个序列很n个组，使得取出来的这n个数字的gcd不为1
• 因为每组两个数字都可以取，所以可以提供的质因子就变成了两份，为了产生对答案的贡献，我们不妨把该组可以产生的贡献都计算进去。然后筛选出来的答案再进行压缩，使得他符合所有组中的选择。
• 每组的数乘起来，然后求整个序列的gcd，可以想到这个gcd包含了所有组中共有的质因数（质因数的指数是多少不用管）。然后每次筛的时候，选一个质因数不为一的数字选就可以了。

#include 
    
     using namespace std;#define g std::__gcdlong long A[555555],B[555555],n,a=0;int main(){    scanf("%lld", &n);    for(int i=1;i<=n;i++)    {        scanf("%lld%lld",&A[i],&B[i]);        a=g(a,A[i]*B[i]);    }    if(a==1){        return puts("-1"),0;    }    for(int i=1;i<=n;i++){        if(g(a,A[i])>1)            a=g(a,A[i]);        else            a=g(a,B[i]);    }    return printf("%lld\n", a), 0;}
    

• 取一个切点然后反转，两次反转我们可以发现完全就是将前缀串接到了后缀串的后面，而一次反转效果也是同样的，把切割点分开，两端连上，中间的情况我们不需要考虑。
• 所以这个题就转换为了把这个串结成一个圈，然后在圈上取一段长度最长不超过n的连续不同序列。注意极端情况(如果不是cf给的数据，恐怕要卡很久)

#include 
    
     using namespace std;char s[200100];int main(){    cin>>s;    int res = 0, cnt = 1;    int len = strlen(s);    for(int i=len;i
     
      len)        cout<
      
       <
      
     
    

• 区间dp，思路挺顺，但是有一点马虎了之后就会造成很大的麻烦
• dp[l][r][0]表示以 l-1 为根的区间可否组成二叉搜索树。然后搜就可以了
• 代码可以优化一下

#include 
    
     using namespace std;const int N = 770;int n;int d[N][N][2],g[N][N],a[N];int gcd(int a,int b){    return b==0?a:gcd(b,a%b);}int dp(int l,int r,int m){    int p = m==0?l-1:r+1;    int &res = d[l][r][m];    if(res)return res;    if(l==r){        if(g[l][p]>1)res = 1;        else res = -1;    }    else{        int flag = 0;        for(int i=l;i<=r;i++){            if(g[i][p]>1){                if(i==l){                    if(dp(i+1,r,0)==1){                        flag = 1;break;                    }                }                if(i==r){                    if(dp(l,i-1,1)==1){                        flag = 1;break;                    }                }                else{                    if(dp(l,i-1,1)==1&&dp(i+1,r,0)==1){                        flag = 1;break;                    }                }            }        }        if(flag)res = 1;        else res = -1;    }    return res == 1;}int main(){    cin>>n;    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        g[i][i] = a[i];    }    for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++){            g[i][j] = g[j][i] = gcd(a[i],a[j]);        }    if(n == 2){        if(g[1][2]>1)        puts("Yes");        else puts("No");        return 0;    }    int flag = 0;    for(int i=1;i<=n;i++){        if(i==1){            if(dp(2,n,0)==1){                flag = 1;                break;            }        }        else if(i==n){            if(dp(1,n-1,1)==1){                flag = 1;break;            }        }        else if(dp(1,i-1,1)==1&&dp(i+1,n,0)==1){            flag = 1;break;        }    }    /*    for(int i=1;i<=n;i++){        for(int j=i+1;j<=n;j++)            printf("%d %d %d %d\n",i,j,d[i][j][0],d[i][j][1]);    }    */    if(flag)puts("Yes");    else    puts("No");    return 0;}
    

压缩后：

#include 
    
     using namespace std;const int N = 770;int n;int d[N][N][2],g[N][N],a[N];int gcd(int a,int b){    return b==0?a:gcd(b,a%b);}int dp(int l,int r,int m){    int p = m==0?l:r;    int &res = d[l][r][m];    if(res)return res;    if(l==r) res = 1;    else{        l = m==0?l+1:l;        r = m==1?r-1:r;        int flag = 0;        for(int i=l;i<=r;i++){            if(g[i][p]>1){                if(dp(l,i,1)==1&&dp(i,r,0)==1){                    flag = 1;break;                }            }        }        if(flag)res = 1;        else res = -1;    }    return res == 1;}int main(){    cin>>n;    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        g[i][i] = a[i];    }    for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++){            g[i][j] = g[j][i] = gcd(a[i],a[j]);        }    int flag = 0;    for(int i=1;i<=n;i++){        if(dp(1,i,1)==1&&dp(i,n,0)==1){            flag = 1;            break;        }    }    if(flag)puts("Yes");    else puts("No");    return 0;}
    

5. CF-1027

• 思路还是比较清晰的，不过在处理各种情况时，不要一味想着统一所有情况，其实分一下奇偶也是可以的，更容易写对

#include 
    
     using namespace std;typedef long long ll;ll n,q,x,y;int main(){    cin>>n>>q;    ll res;    for(int i=1;i<=q;i++){        cin>>x>>y;        if((x+y)%2==0){            if(x&1) res = ((x-1)/2)*n+(y/2+1);            else res = ((x-2)/2)*n + ((n+1)/2)+y/2;        }        else {            if(x&1) res = ((x-1)/2)*n + y/2 + (n*n+1)/2;            else res = ((x-2)/2)*n + n/2 + y/2+1 + (n*n+1)/2;        }        cout<
     
      <
     
    

• 虽然是个难度1600的贪心，但是贪心策略很好想，难点在于处理上，如果用hash存储的话，即使是1e4的数组，每组test memset一下时间也会爆炸，貌似有人卡过的，不过这不是正解。
• 正解是先排个序，然后两个相同的变成一个，单着的就抛弃了就可以了。然后扫一次
• T了半小时之后看正解，因为数组下标，还有循环，又坑了半小时。感觉状态不太好的时候就不要硬干了，肯定是小问题。

#include 
    
     using namespace std;typedef long long ll;const int N = 1000*1000+13;int T,n,m,a[N],b[N];int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=0;i
     
       S*TP){                A = b[i];B = b[i+1];                P = TP;                S = TS;            }        }        printf("%d %d %d %d\n",A,A,B,B);    }    return 0;}
     
    

• 这题一眼就是并查集，NONONO，忽略了两点的有向关系。也是巧了，刚做了这题第二天就在牛客碰到了。
• 具体处理就是先拓扑扫一遍，剩下的就是环，在环内找个最小值放哨兵就可以了。

#include 
    
     using namespace std;typedef long long ll;const int N = 200010;int n;int c[N],p[N],deg[N],v[N];int dfs(int x){    v[x] = 1;    if(v[p[x]])return c[x];    else return min(c[x],dfs(p[x]));}int main(){    cin>>n;    for(int i=1;i<=n;i++)scanf("%d",&c[i]);    for(int i=1;i<=n;i++){        scanf("%d",&p[i]);        deg[p[i]]++;    }    queue
     
       q;    for(int i=1;i<=n;i++)if(deg[i]==0)q.push(i);    while(!q.empty()){        int x = q.front();q.pop();        deg[p[x]]--;        if(deg[p[x]]==0)q.push(p[x]);    }    int res = 0;    for(int i=1;i<=n;i++){        if(deg[i]&&!v[i]){            //printf("%d\n",i);            res+=dfs(i);        }    }    cout<
      
       <
      
     
    

6.CF-1023

• 被A题卡特判了。难过

#include 
    
     using namespace std;const int N = 200010;char s[N],t[N];int n,m;bool check(int x){    if(x==n&&n!=m)return false;    for(int i=0;i
     
      x;i--){        int j = m-1-(n-1-i);        if(j
      
       >n>>m;    cin>>s>>t;    if(n>m+1){        puts("NO");return 0;    }    int index = n;    for(int i=0;i
      
     
    

大佬的代码：

#include 
    
     using namespace std;int main(){    string s1,s2;int n,m,i=0;cin>>n>>m>>s1>>s2;    while(s1[i]==s2[i]&&i
    

• 直接放代码了，这题没什么好说的，还卡了那么久。

#include 
    
     using namespace std;const int N = 200010;int n,k;char s[N],t[N];int main(){    while(cin>>n>>k){        cin>>s;        int l = 0,r = 0,p = 0;        for(int i=0;i