首页 > 代码库 > 20160929训练记录

20160929训练记录

选数

排序原数列,二分答案,对于差值<mid的相邻对进行删除

#include<map>#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<complex>#include<iostream>#include<assert.h>#include<algorithm>using namespace std;#define inf 1001001001#define infll 1001001001001001001LL#define ll long long#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl#define gmax(a,b) (a)=max((a),(b))#define gmin(a,b) (a)=min((a),(b))#define Ri register int#define gc getchar()#define il inlineil int read(){    bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch==-)f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-0;ch=gc;}return f?x:-x;}#define gi read()#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);int n,k,a[100002],p[100002],g[100002];bool chk(int x){    int cnt=0,_p=a[1],mn;    for(int i=2;i<=n;i++){        if(a[i]-_p<x)++cnt;        else _p=a[i];     }    return n-cnt>=k;}int main(){    FO(choose);    n=gi;k=gi;    for(int i=1;i<=n;i++)a[i]=gi;    sort(a+1,a+n+1);     for(int i=2;i<=n;i++)g[i]=a[i]-a[i-1];    int l=1,r=1000000001,ans;    while(l<=r){        int mid=(l+r)/2;        if(chk(mid)){            ans=mid;            l=mid+1;        }        else r=mid-1;    }    cout<<ans;}

划区灌溉

易得f[i]=min{f[j]}+1 (技术分享)

然后用个单调队列

#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<complex>#include<iostream>#include<assert.h>#include<algorithm>using namespace std;#define inf 1001001001#define infll 1001001001001001001LL#define ll long long#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl#define gmax(a,b) (a)=max((a),(b))#define gmin(a,b) (a)=min((a),(b))#define Ri register int#define gc getchar()#define il inlineil int read(){    bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch==-)f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-0;ch=gc;}return f?x:-x;}#define gi read()#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);const int maxn=1000033;int dq[1234567],f[1234567],map[1234567];int n,m,L,A,B;int main(){    FO(divide);    n=gi;L=gi;A=gi;B=gi;    memset(f,127/2,sizeof(f));    int a,b;    for(int i=1;i<=n;i++)        a=gi,b=gi,map[min(a+1,b)]++,map[b]--;    a=(A-B)<<1,b=0;int H=1,T=0;    f[0]=0;    int now=0;    for(int i=1;i<A*2;i++)    now+=map[i];    for(int i=A<<1;i<=L;i+=2,a+=2,b+=2){        while(H<=T&&f[dq[T]]>=f[b])    T--;        dq[++T]=b;        if(f[dq[T]]>=inf)    T--;        now+=map[i]+map[i-1];        if(now){            f[i]=inf;            continue;        }        while(H<=T&&dq[H]<a)    H++;        if(H<=T&&f[dq[H]]<inf)f[i]=f[dq[H]]+1;        else f[i]=inf;     }    printf("%d\n",f[L]<inf?f[L]:-1);    return 0;}

树林

从树林连一条线到边界。然后根据在边界两侧的情况bfs

#include<map>#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<complex>#include<iostream>#include<assert.h>#include<algorithm>using namespace std;#define inf 1001001001#define infll 1001001001001001001LL#define ll long long#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl#define gmax(a,b) (a)=max((a),(b))#define gmin(a,b) (a)=min((a),(b))#define Ri register int#define gc getchar()#define il inlineil int read(){    bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch==-)f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-0;ch=gc;}return f?x:-x;}#define gi read()#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);int n,m,sx,sy,x,y;struct data{    int x,y,f;};int dx[]={0,0,1,1,1,-1,-1,-1};int dy[]={1,-1,-1,0,1,1,-1,0};int a[55][55],b[55][55],flag[2][55][55];int main(){    FO(grove);    n=gi;m=gi;    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++){            char ch=gc;            while(ch!=.&&ch!=X&&ch!=*)ch=gc;            if(ch==X)a[i][j]=1,x=i,y=j;            if(ch==*)sx=i,sy=j;     }    queue<data>q;    q.push((data){sx,sy,0});    for(int i=1;i<=n-x;i++)b[i+x][y]=1;    while(!q.empty()){        data c=q.front();q.pop();        for(int i=0;i<8;i++){            int X=c.x+dx[i],Y=c.y+dy[i];            if(X<=n&&X>0&&Y<=m&&Y>0&&!a[X][Y]){                if((b[c.x][c.y]||b[X][Y])&&Y<=c.y)continue;                if(b[X][Y]&&!flag[1][X][Y]){                    flag[1][X][Y]=flag[c.f][c.x][c.y]+1;                    q.push((data){X,Y,1});                }else{                    if(!flag[c.f][X][Y]){                        flag[c.f][X][Y]=flag[c.f][c.x][c.y]+1;                        q.push((data){X,Y,c.f});                    }                }            }        }     }    cout<<flag[1][sx][sy];}

迷宫花坛

仙人掌最短路。

把环缩了。然后根据两点的位置分类讨论

#include<map>#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<complex>#include<iostream>#include<assert.h>#include<algorithm>using namespace std;#define inf 1001001001#define infll 1001001001001001001LL#define ll long long#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl#define gmax(a,b) (a)=max((a),(b))#define gmin(a,b) (a)=min((a),(b))#define Ri register int#define gc getchar()#define il inlineil int read(){    bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch==-)f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-0;ch=gc;}return f?x:-x;}#define gi read()#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);const int N=100010,M=300010;  using namespace std;  int n,m,Q,dis[N],sta[N],top;int rdis[N],rcnt,fa[N][22],dfn[N],pre[N],bel[N],rlen[N],dep[N];  struct edge{    int to,next,val;}e[M*2];int last[N],cnt=1,tim;bool inq[N],del[M],vis[N];  void add(int a,int b,int c){    e[++cnt]=(edge){b,last[a],c};last[a]=cnt; }void ins(int a,int b,int c){add(a,b,c),add(b,a,c);}  void spfa(){      queue<int>q;    for(int i=1;i<=N;i++)dis[i]=inf;    dis[1]=0;q.push(1);inq[1]=1;    while(!q.empty()){          int x=q.front();q.pop();          for(int y=last[x];y;y=e[y].next){              if (dis[e[y].to]>dis[x]+e[y].val){                  dis[e[y].to]=dis[x]+e[y].val;                  if (!inq[e[y].to]){                             q.push(e[y].to);                        inq[e[y].to]=1;                  }              }          }          inq[x]=0;    }  }  void getring(int st,int ed,int id){      del[id]=del[id^1]=1;    rlen[++rcnt]+=e[id].val;      for(int x=ed;x!=st;x=e[pre[x]^1].to){          bel[x]=rcnt;        del[pre[x]]=del[pre[x]^1]=1;          ins(st,x,0);        rlen[rcnt]+=e[pre[x]].val;      }  }    void dfs(int x){      dfn[x]=++tim;      for (int y=last[x];y;y=e[y].next)         if(y!=(pre[x]^1)&&(y<=(m*2+1))){              if(!dfn[e[y].to])                 pre[e[y].to]=y,rdis[e[y].to]=rdis[x]+e[y].val,dfs(e[y].to);              else if(dfn[e[y].to]<dfn[x])                         getring(e[y].to,x,y);          }  }    void dfs2(int x){      vis[x]=1;      for(int i=1;i<=17;i++) fa[x][i]=fa[fa[x][i-1]][i-1];      for(int y=last[x];y;y=e[y].next)        if(!del[y]&&e[y].to!=fa[x][0])              dep[e[y].to]=dep[x]+1,fa[e[y].to][0]=x,dfs2(e[y].to);  }    int query(int x,int y){      if(dep[x]<dep[y]) swap(x,y);      int a=x,b=y;      for(int h=dep[x]-dep[y],i=17;h&&i>=0;i--) if(h&(1<<i))h-=(1<<i),x=fa[x][i];      if(x==y) return dis[a]-dis[b];    for(int i=17;i>=0;i--)          if(fa[x][i]!=fa[y][i])              x=fa[x][i],y=fa[y][i];      int lca=fa[x][0];      if(bel[x]&&bel[x]==bel[y]){          int d=abs(rdis[x]-rdis[y]);d=min(d,rlen[bel[x]]-d);          return dis[a]+dis[b]-dis[x]-dis[y]+d;      }      return dis[a]+dis[b]-2*dis[lca];  }    int main(){      FO(garden);    n=gi;m=gi;    for(int i=1,x,y,z;i<=m;i++) x=gi,y=gi,z=gi,ins(x,y,z);      spfa();    pre[1]=-1;    dfs(1);dfs2(1);    Q=gi;     for(int i=1;i<=Q;i++) printf("%d\n",query(gi,gi));      return 0;  }

20160929训练记录