四连测Day2-白红宇

四连测Day2

阅读量：4325 次

发布时间：2019-06-06

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

题目：链接: https://pan.baidu.com/s/1ef_9hGBhczW0B4dz5IUKmw 密码: qgjy

T1:

hash后直接二分查询即可

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline long long read(){    long long f=1,ans=0;char c;    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}    return ans*f;}char str[100001];long long sum[100001];long long b[100001];long long bb=27; long long maxn=0;long long l,r,mid;long long u,v;bool check(long long x){    long long x1=sum[u+x-1]-sum[u-1]*b[x];//    cout<
           
            <<" "<
            
             <<" "<
             
              <<" "<
              
               <

View Code

T2:

因为作者能力有限，数学技巧过于高深，所以先给std，学完以后再重新补写

#include
      
       #include
       
        #include
        
         using namespace std;inline int read(){    int x=0,t=1,c;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    while(isdigit(c))x=x*10+c-'0',c=getchar();    return x*t;}int sig(long long x){    if(x<0)return -1;    else if(!x)return 0;    return 1;}long long gcd(long long a,long long b){
    return b?gcd(b,a%b):a;}class Vector{public:    long long x,y;    Vector(long long _x=0,long long _y=0)    {        x=_x;        y=_y;    }    Vector operator + (const Vector &b) const    {        return Vector(x+b.x,y+b.y);    }    Vector operator - (const Vector &b) const    {        return Vector(x-b.x,y-b.y);    }    long long operator * (const Vector &b) const    {        return x*b.x+y*b.y;    }};class Line{public:    long long a,b,c;    Line(Vector v0,Vector v1)    {        a=v0.x-v1.x;        b=v0.y-v1.y;        swap(a,b);        a=-a;        c=gcd(a,b);        a/=c;        b/=c;        c=a*v0.x+b*v0.y;    }    Line(long long _a=0,long long _b=1,long long _c=0)    {        a=_a;        b=_b;        c=_c;    }    int side(Vector v)    {        return sig(v*Vector(a,b)-c);    }}l1,l2;void Solve(){    int n=read();    Vector v0,v1,u0,u1;    v0.x=read();v0.y=read();v1.x=read();v1.y=read();    l1=Line(v0,v1);    bool res=0;    while(n--)    {        u0.x=read();u0.y=read();u1.x=read();u1.y=read();        l2=Line(u0,u1);        if(l1.a*l2.b==l1.b*l2.a)        {            if(l1.c*l2.b==l2.c*l1.b)            {                long long l0=0,r0=(v1-v0)*(v1-v0),l1=(u0-v0)*(v1-v0),r1=(u1-v0)*(v1-v0);                if(l0<=r1&&l1<=r0)res=1;            }        }        else        {            if(l1.side(u0)!=l1.side(u1)&&l2.side(v0)!=l2.side(v1))res=1;        }    }    if(res)puts("YES");    else puts("NO");}int main(){    freopen("intersect.in","r",stdin);    freopen("intersect.out","w",stdout);    int T=read();    while(T--)Solve();}

std

T3:

dijkstra倒推，加优先队列优化，设dis[n]=0,dis[i]=min{dis[i],max（最大限制，dis[x(i为起点的终点)]+所对应需要的能量）}

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;inline long long read(){ long long f=1,ans=0;char c; while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return ans*f;}priority_queue
            
             
               > que;long long n,m,cnt=1;struct node{ long long a,b,c,m,nex;}x[2000110];long long head[1000010];long long vis[1000010];long long dis[1000010];void add(long long u,long long v,long long c,long long m){ x[cnt].a=u,x[cnt].b=v,x[cnt].c=c,x[cnt].m=m; x[cnt].nex=head[u],head[u]=cnt++;}long long inf;int main(){ memset(head,-1,sizeof(head)); memset(dis,127/3,sizeof(dis)); inf=dis[1]; n=read(),m=read(); for(long long i=1;i<=m;i++) { long long u=read(),v=read(),c=read(),m=read(); add(u,v,c,m); add(v,u,c,m); } dis[n]=0; que.push(make_pair(0,n)); while(!que.empty()) { long long xx=que.top().second;que.pop(); if(vis[xx]==1) continue; vis[xx]=1; for(long long i=head[xx];i!=-1;i=x[i].nex) { if(dis[x[i].b]>max(x[i].m,dis[xx]+x[i].c)) { dis[x[i].b]=max(x[i].m,dis[xx]+x[i].c); que.push(make_pair(-dis[x[i].b],x[i].b)); } } } if(dis[1]!=inf) cout<