首页 > 代码库 > 2017-2-19四校联考
2017-2-19四校联考
T1.
#include<cstdio> #include<cstring> #define MN 300 int a[MN+5][MN+5],f[2][1<<17]; int main() { freopen("design.in","r",stdin); freopen("design.out","w",stdout); int n,m,p,i,j,k,x,p1,p2; scanf("%d%d%d",&n,&m,&p); for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&(m>n?a[j][i]:a[i][j])); if(m>n)i=n,n=m,m=i;f[0][0]=1; for(i=p1=1,p2=0;i<=n+1;++i)for(j=1;j<=m;++j,p1^=1,p2^=1) { memset(f[p1],0,sizeof(f[p1])); for(k=0;k<1<<m;++k) { if(!a[i-1][j]&&(k&(1<<j-1)))continue; x=k^(a[i-1][j]<<j-1); if(!a[i][j]&&(x&(1<<j-1)))continue; f[p1][x]=(f[p1][x]+f[p2][k])%p; if(a[i][j]&&a[i][j-1]&&!(x&(1<<j-1))&&!(x&(1<<j-2))) x|=1<<j-1,x|=1<<j-2,f[p1][x]=(f[p1][x]+f[p2][k])%p; } } printf("%d",1ll*f[p2][0]*f[p2][0]%p); fclose(stdin);fclose(stdout);return 0; }
T2.
#include<cstdio> #include<algorithm> using namespace std; inline int read() { int x=0;char c; while((c=getchar())<‘0‘||c>‘9‘); for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=x*10+c-‘0‘; return x; } #define MN 200000 int n,L,a[MN+5],t[MN+5],q[MN+5]; struct P{int l,r;}p[MN+5]; bool cmp(P a,P b){return a.l==b.l?a.r>b.r:a.l<b.l;} int c[MN+5][2],fa[MN+5],s[MN+5],tf[MN+5]; inline void update(int x){s[x]=s[c[x][0]]+s[c[x][1]]+1;} void rotate(int x) { int f=fa[x],ff=fa[f],l,r; l=c[f][1]==x;r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][c[ff][1]==f]=x;c[f][l]=c[x][r];c[x][r]=f; update(f);if(tf[f])tf[x]=tf[f],tf[f]=0; } void splay(int x) { for(int f;fa[x];rotate(x)) if(fa[f=fa[x]])rotate(c[fa[f]][0]==f^c[f][0]==x?x:f); update(x); } void access(int x) { int f; for(splay(x);(f=tf[x])>0;splay(x)) { splay(f); fa[c[f][1]]=0;tf[c[f][1]]=f; fa[c[f][1]=x]=f;tf[x]=0; } } int get(int x,int k) { int l=1,r=n,mid,res=0; while(l<=r) { if(p[mid=l+r>>1].l>a[x])r=mid-1; else l=mid+1,res=mid; } if(!res||p[res].r<a[x])return -1; if(p[res].r-L>=a[1]) { for(l=1,r=x;l<=r;) if(a[mid=l+r>>1]>p[res].r-L)q[x]=mid,r=mid-1; else l=mid+1; return t[x]=k+1,0; } else q[x]=0; for(l=x,r=k;l<=r;) if(a[mid=l+r>>1]>p[res].r)r=mid-1; else l=t[x]=mid+1; return 0; } int main() { freopen("launch.in","r",stdin); freopen("launch.out","w",stdout); int m,i,j,k,ans; n=read();m=read();L=read(); for(i=1;i<=n;++i) { p[i].l=read();p[i].r=read(); if(p[i].r<p[i].l)p[i+1].l=0,p[i+1].r=p[i].r,p[i].r+=L,++i,++n; } sort(p+1,p+n+1,cmp); for(i=1,p[j=0].r=-1;i<=n;++i)if(p[i].r>p[j].r)p[++j]=p[i];n=j; while(m--) { for(k=read(),i=1;i<=k;++i)a[i]=read(); sort(a+1,a+k+1); for(i=1,a[j=0]=-1;i<=k;++i)if(a[i]!=a[i-1])a[++j]=a[i]; for(i=1;i<=j;++i)if(get(i,j))break; if(i<=j){puts("-1");continue;} for(i=0;i++<=j;)c[i][0]=c[i][1]=fa[i]=0,s[i]=1; for(i=1;i<=j;++i)tf[i]=t[i];tf[i]=-1; access(1);ans=s[c[1][0]]; for(i=0;i++<=j;)c[i][0]=c[i][1]=fa[i]=0,s[i]=1; for(i=1;i<=j;++i)tf[i]=-1; for(i=1;i<=j;++i) { if(q[i])ans=min(ans,(access(q[i]),s[c[q[i]][0]]+1)); splay(i);tf[i]=t[i]; } printf("%d\n",ans); } fclose(stdin);fclose(stdout);return 0; }
T3.
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; inline int read() { int x=0;char c; while((c=getchar())<‘0‘||c>‘9‘); for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=x*10+c-‘0‘; return x; } #define MN 100000 #define N 131072 #define INF (1LL<<60) int c[MN+5],cn,l[MN+5],r[MN+5],t[MN+5],w[MN+5]; ll ans=INF,t1[N*2],t2[N*2]; void renew(ll*t,int k,ll x) { if(x>=t[k+=N])return; for(t[k]=x;k>>=1;)t[k]=min(t[k<<1],t[(k<<1)+1]); } ll query(ll*t,int l,int r) { ll res=INF; for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) { if(~l&1)res=min(res,t[l+1]); if( r&1)res=min(res,t[r-1]); } return res; } int findl(int x) { int l=1,r=cn,mid,res; while(l<=r) if(c[mid=l+r>>1]<x)l=mid+1; else r=mid-1,res=mid; return res; } int findr(int x) { int l=1,r=cn,mid,res; while(l<=r) if(c[mid=l+r>>1]>x)r=mid-1; else l=mid+1,res=mid; return res; } int main() { freopen("network.in","r",stdin); freopen("network.out","w",stdout); int n,m,i,j,x,y,z;ll a,b; n=read();c[++cn]=1;c[++cn]=m=read(); for(i=1;i<=n;++i)l[i]=read(),r[i]=read(),c[++cn]=t[i]=read(),w[i]=read(); sort(c+1,c+cn+1); for(i=1,j=0;i<=cn;++i)if(c[i]!=c[i-1])c[++j]=c[i];cn=j; memset(t1,42,sizeof(t1));memset(t2,42,sizeof(t2)); renew(t1,1,0);renew(t2,cn,0); for(i=1;i<=n;++i) { x=findl(l[i]);y=findr(r[i]);z=findl(t[i]); a=query(t1,x,y);b=query(t2,x,y); if(a+b+w[i]<ans)ans=a+b+w[i]; renew(t1,z,a+w[i]);renew(t2,z,b+w[i]); } printf("%lld",ans<INF?ans:-1); fclose(stdin);fclose(stdout);return 0; }
2017-2-19四校联考
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。