首页 > 代码库 > 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训练记录
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。