FJOI2018二试游记-白红宇

FJOI2018二试游记

阅读量：5275 次

发布时间：2019-06-14

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

二试画风清奇

T1普及组水题 BZOJ4500

T2原题 BZOJ4919

前两天加起来1h-

T3毒瘤题肛了3h+得到0分的好成绩

省选rank44->rank24

#include
      
       #include
       
        #define rep(i,s,t) for(register int i=s;i<=t;++i)using namespace std;#define gc getchar()const int N=2e6+11,inf=(1<<30);inline int read(){    char c;while(c=gc,c==' '||c=='\n');int data=0,f=1;    if(c=='-')f=-1;else data=c-48;    while(c=gc,c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data*f;}int T,n,m,k,tot,x,y,z;int nxt[N],las[4011],to[N],w[N],ans[4011];inline void add(int x,int y,int z){    nxt[++tot]=las[x],    las[x]=tot,    to[tot]=y,    w[tot]=z;}inline void init(){    rep(i,1,n+m)las[i]=0,ans[i]=-inf;    tot=0;}inline bool bfs(int x){    for(register int e=las[x];e;e=nxt[e]){        if(ans[to[e]]==-inf){            ans[to[e]]=w[e]-ans[x];            if(!bfs(to[e]))                return 0;        }        else            if(ans[to[e]]+ans[x]!=w[e])                return 0;    }    return 1;}int main(){    freopen("solo.in","r",stdin);    freopen("solo.out","w",stdout);    T=read();    while(T--){        n=read(),m=read(),k=read();        init();        rep(i,1,k){            x=read(),y=read()+n,z=read(),            add(x,y,z),add(y,x,z);        }        rep(i,1,n+m)            if(ans[i]==-inf){                ans[i]=0;                if(!bfs(i)){                    puts("No");                    goto end;                }            }        puts("Yes");        end:;    }    return 0;}

T1 code

#include
      
       #include
       
        #include
        
         #define rep(i,s,t) for(register int i=s;i<=t;++i)using namespace std;const int N=4e5+11,M=2e5+11;int nxt[N],las[N],to[N];int val[N];multiset
         
          s[M];multiset
          
           ::iterator it;int n,fa,tot;inline void add(int x,int y){    nxt[++tot]=las[x];    las[x]=tot;    to[tot]=y;}inline void merge(int x,int y){    if(s[x].size()
           
            ='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data*f;}int main(){ freopen("boss.in","r",stdin); freopen("boss.out","w",stdout); n=read(); rep(i,1,n){ val[i]=read(), val[i]=-val[i]; } rep(i,2,n){ fa=read(), add(fa,i); } dfs(); printf("%d\n",(int)s[1].size()); return 0;}

T2 code

T3 毒瘤题弃疗

#include
      
       #include
       
        #include
        
         #include
         
          #define rep(i,s,t) for(register int i=s;i<=t;++i)using namespace std;typedef double db;const int N=1e5+11;db S,T,X,Y;inline db sqr(db x){    return x*x;}struct point{    db x,y;    inline bool operator<(point A)const{        return sqr(x-S)+sqr(y-T)>sqr(A.x-S)+sqr(A.y-T);    }}p[2][N],now;priority_queue
          
           heap;int n,m;int a,b,c,d;int mark[2][N];db ans,h,minn;inline void init(){    rep(i,1,n){        if(!mark[0][i])heap.push(p[0][i]);        if(mark[0][i]==1)S=0,T=p[0][i].y;        if(mark[0][i]==2)X=0,Y=p[0][i].y;    }    rep(i,1,m){        if(!mark[1][i])heap.push(p[1][i]);        if(mark[1][i]==1)S=h,T=p[1][i].y;        if(mark[1][i]==2)X=h,Y=p[1][i].y;    }}int main(){    freopen("post.in","r",stdin);    freopen("post.out","w",stdout);    scanf("%d%d%d%d%d%d%lf",&n,&m,&a,&b,&c,&d,&h);    mark[a][b]=1,mark[c][d]=2;    rep(i,1,n)        scanf("%lf",&p[0][i].y);    rep(i,1,m){        scanf("%lf",&p[1][i].y);        p[1][i].x=h;    }    init();    while(!heap.empty()){        now=heap.top();heap.pop();        ans+=1.*sqrt(1.*sqr(now.x-S)+1.*sqr(now.y-T));        S=now.x,T=now.y;    }    ans+=1ll*sqrt(sqr(X-S)+sqr(Y-T));    minn=ans;ans=0.;    init();    swap(X,S),swap(Y,T);    while(!heap.empty()){        now=heap.top();heap.pop();        ans+=1.*sqrt(1.*sqr(now.x-S)+1.*sqr(now.y-T));        S=now.x,T=now.y;    }    ans+=1ll*sqrt(sqr(X-S)+sqr(Y-T));    minn=min(minn,ans);    printf("%.2lf\n",minn);    return 0;}