@Scarlet 2017-01-23T04:44:53.000000Z 字数 10941 阅读 1267

# POI 2005

POI 2005 OI 解题报告

## Toy Cars (Stage I)

From hzwer

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 500010using namespace std;typedef long long LL;#define G c=getchar()#define pa pair<int,int>#define mp make_pairinline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int n,K,p,ans,a[maxn],nxt[maxn],last[maxn];bool m[maxn];priority_queue<pa,vector<pa> >q;int main(){    n=read();K=read(),p=read();    for(int i=1;i<=n;i++)last[i]=p+1;    for(int i=1;i<=p;i++)a[i]=read();    for(int i=p;i;i--)nxt[i]=last[a[i]],last[a[i]]=i;    for(int i=1;i<=p;i++)    {        if(m[a[i]]){q.push(mp(nxt[i],a[i]));continue;}        if(K)        {            ans++;q.push(mp(nxt[i],a[i]));            m[a[i]]=1;            K--;        }        else        {            while(m[q.top().second]==0)q.pop();            m[q.top().second]=0;            q.pop();            ans++;q.push(mp(nxt[i],a[i]));            m[a[i]]=1;        }    }    printf("%d",ans);    return 0;}

## Piggy Banks (Stage I)

/*    Author:Scarlet*/#include<cstdio>#define N 1000005using namespace std;inline int read(){    int x=0;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x;}int n,ans,fa[N],x,p,q;int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int main(){    n=read();       for(int i=1;i<=n;i++)fa[i]=i;    for(int i=1;i<=n;i++)    {        x=read(),p=find(i),q=find(x);        if(p!=q)fa[q]=i;    }    for(int i=1;i<=n;i++)if(fa[i]==i)ans++;    printf("%d",ans);    return 0;}

## A Journey to Mars (Stage II - day 0)

#include<bits/stdc++.h>#define maxn 2000100using namespace std;typedef long long LL;#define G c=getchar()inline LL read(){    LL x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}struct rec{int x,y;}a[maxn];int b[maxn],sta[maxn],r[maxn],res,n;bool can[2][maxn];void work(int k){    b[0]=0;    for(int i=1;i<=n;i++)b[i]=b[i-1]+a[i].x-a[i].y;    for(int i=1;i<=n;i++)b[n+i]=b[n+i-1]+a[i].x-a[i].y;    int top=0;b[2*n+1]=-1000000000;    for(int i=0;i<=(n<<1)+1;i++)    {        while(top&&b[i]<b[sta[top]])r[sta[top--]]=i-1;        sta[++top]=i;    }    for(int i=0;i<=n-1;i++)if(r[i]-i+1>=n)can[k][i+1]=1;}int main(){    n=read();    for(int i=1;i<=n;i++)        a[i].x=read(),a[i].y=read(),res+=a[i].x-a[i].y;    if(res<0)    {        for(int i=1;i<=n;i++)printf("NIE\n");        return 0;    }    work(0);    for(int i=1;i<=n>>1;i++)        swap(a[i],a[n+1-i]);    int t=a[1].y;    for(int i=1;i<=n-1;i++)        a[i].y=a[i+1].y;    a[n].y=t;    work(1);    for(int i=1;i<=n;i++)        if(can[0][i]||can[1][n+1-i])printf("TAK\n");        else printf("NIE\n");    return 0;}

## Bank Notes (Stage II - day 1)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define M 20200using namespace std;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int n,k,b[220],c[220],f[M];int main(){    n=read();    for(int i=1;i<=n;i++)b[i]=read();    for(int i=1;i<=n;i++)c[i]=read();    k=read();    memset(f,0x3f,sizeof f);    f[0]=0;    for(int i=1,j;i<=n;i++)    {        for(j=1;j<=c[i];j<<=1)        {            for(int k=::k;k>=b[i]*j;k--)                f[k]=min(f[k],f[k-b[i]*j]+j);            c[i]-=j;        }        if(!c[i]) continue;        j=c[i];        for(int k=::k;k>=b[i]*j;k--)                f[k]=min(f[k],f[k-b[i]*j]+j);    }    printf("%d",f[k]);    return 0;}

## Fibonacci Sums (Stage II - day 1)

1.对于f[i]>=2的情况：

2.对于f[i]=1&&f[i+1]=1的情况：

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 1000100using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int a[maxn],b[maxn],c[maxn];void Up(int k){    while(c[k])    {        c[k]=c[k-1]=0;        c[k+1]++;        k+=2;    }}void trans(int i){    if(c[i]<2)return;    int k=i-2;    if(i==2)k++;    if(i>1)c[k]++;    c[i+1]++;    c[i]-=2;}int main(){    int n=read();for(int i=1;i<=n;i++)a[i]=read();    int m=read();for(int j=1;j<=m;j++)b[j]=read();    int len=max(m,n);    for(int i=len;i>=1;i--)    {        c[i]+=a[i]+b[i];        if(c[i]>=2)        {            trans(i);            trans(i+1);            if(i==1)trans(1);        }        if(c[i])Up(i+1);        if(c[i+1])Up(i+2);        if(c[i+2])Up(i+3);    }    while(c[len+1])len++;    if(c[len+2])len+=2;    while(c[len+1])len++;    printf("%d ",len);    for(int i=1;i<=len;i++)        printf("%d ",c[i]);    return 0;}

## Dicing (Stage II - day 2)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 20010#define maxm 100010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}#define AE(u,v,w) E[Si]=(Ed){v,w},nxt[Si]=idx[u],idx[u]=Si++#define Add(u,v,w) AE(u,v,w),AE(v,u,0)#define INF 1000000000struct Ed{int v,w;}E[maxm];int idx[maxn],nxt[maxm],Si,S,T,h[maxn],q[maxn],n,m,ans;bool bfs(){    memset(h,-1,sizeof(h));q[0]=h[0]=0;    for(int l=0,r=1;l<r;)        for(int u=q[l++],i=idx[u];i+1;i=nxt[i])            if(E[i].w&&h[E[i].v]==-1)h[E[i].v]=h[u]+1,q[r++]=E[i].v;    return h[T]+1;}int dfs(int x,int f){    if(x==T)return f;    int ret=0,w;    for(int i=idx[x];i+1;i=nxt[i])        if(E[i].w&&h[E[i].v]==h[x]+1)        {            w=dfs(E[i].v,min(f-ret,E[i].w));            E[i].w-=w;E[i^1].w+=w;            if((ret+=w)==f)return f;        }    if(!ret)h[x]=-1;    return ret;}int dinic(){for(ans=0;bfs();)ans+=dfs(S,INF);return ans;}int e[maxn][2];void build(int x){    memset(idx,-1,sizeof(idx)),Si=0;    for(int i=1;i<=n;i++)        Add(S,i,x);    for(int i=1;i<=m;i++)        Add(n+i,T,1),Add(e[i][0],n+i,1),Add(e[i][1],n+i,1);}int main(){    n=read(),m=read();//这行前面写了int调了1h你敢信。    S=0,T=n+m+1;    for(int i=1;i<=m;i++)        e[i][0]=read(),e[i][1]=read();    int l=1,r=m,ans,mid;    for(;l<=r;)        mid=l+r>>1,build(mid),dinic()==m?r=mid-1,ans=mid:l=mid+1;    printf("%d",ans);    return 0;}

## Template (Stage II - day 2)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 1000010using namespace std;int n,k,p,F[maxn];char s[maxn],ch;void KMP(int n,char *a){    int j=0,k=1;    for(;1+j<n&&a[j]==a[1+j];j++);    F[1]=j;    for(int i=2,Len,L;i<n;i++)    {        Len=k+F[k],L=F[i-k];        if(L<Len-i)F[i]=L;        else        {            for(j=max(0,Len-i);i+j<n&&a[j]==a[i+j];j++);            F[k=i]=j;        }    }}int NXT[maxn],PRE[maxn];#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn],nxt[maxn],to[maxn],Si=1;int main(){    scanf("%s",s);    n=strlen(s);    KMP(n,s);    for(int i=0;i<=n;i++)        NXT[i]=i+1,PRE[i]=i-1;    F[0]=n;    F[n]=n+1;    for(int i=0;i<=n;i++)        AE(F[i],i);    int K=1,mx=1;    for(;K<=n;K++)    {        for(int i=idx[K-1],L,R;i;i=nxt[i])            L=PRE[to[i]],R=NXT[to[i]],NXT[L]=R,PRE[R]=L,mx=max(mx,R-L);        if(mx<=K)break;    }    printf("%d\n",K);}

## Special Forces Manoeuvres (Stage III - day 1)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 2010#define S(J) ((J)*(J))using namespace std;typedef long long LL;typedef double DB;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}DB x[maxn],y[maxn],r[maxn];bool InC(DB X,DB Y,int w){return S(X-x[w])+S(Y-y[w])<=S(r[w])+0.00001;}void mx(DB&X,DB&Y,DB x,DB y){if(x>X)X=x,Y=y;}void mn(DB&X,DB&Y,DB x,DB y){if(x<X)X=x,Y=y;}void c2point(DB x1,DB y1,DB r1,DB x2,DB y2,DB r2,DB &rx1,DB &ry1,DB &rx2,DB &ry2){    DB a,b,r;    a=x2-x1;    b=y2-y1;    r=(a*a+b*b+r1*r1-r2*r2)/2;    if(a==0&&b!=0)    {        ry1=ry2=r/b;        rx1=sqrt(r1*r1-ry1*ry1);        rx2=-rx1;    }    else if(a!=0&&b==0)    {        rx1=rx2=r/a;        ry1=sqrt(r1*r1-rx1*rx2);        ry2=-ry1;    }    else if(a!=0&&b!=0)    {        DB delta;        delta=b*b*r*r-(a*a+b*b)*(r*r-r1*r1*a*a);        ry1=(b*r+sqrt(delta))/(a*a+b*b);        ry2=(b*r-sqrt(delta))/(a*a+b*b);        rx1=(r-b*ry1)/a;        rx2=(r-b*ry2)/a;    }    rx1+=x1;    ry1+=y1;    rx2+=x1;    ry2+=y1;}int main(){    int n=read(),ans;    for(int i=1;i<=n;i++)        x[i]=read(),y[i]=read(),r[i]=read();    DB MX=x[1]+r[1],MY=y[1];    int f=0;    for(int i=2;i<=n;i++)    {        if(InC(MX,MY,i))continue;        for(int j=1;j<i;j++)        {            DB NX=-100000000,NY=-10000000,sx,sy,tx,ty;sx=sy=tx=ty=0;            if(S(x[i]-x[j])+S(y[i]-y[j])>S(r[i]+r[j])){MX=NX,MY=NY;break;}//相离            if(InC(x[j]+r[j],y[j],i))mx(NX,NY,x[j]+r[j],y[j]);            if(InC(x[i]+r[i],y[i],j))mx(NX,NY,x[i]+r[i],y[i]);            if(S(x[i]-x[j])+S(y[i]-y[j])>S(r[i]-r[j]))//相交            {                c2point(x[i],y[i],r[i],x[j],y[j],r[j],sx,sy,tx,ty);                mx(NX,NY,sx,sy);                mx(NX,NY,tx,ty);            }            if(MX>NX)MX=NX,MY=NY;        }        for(int j=1;j<=i;j++)            if(!InC(MX,MY,j)){f=1;break;}        if(f){ans=i;break;}    }    if(!f)puts("NIE");    else printf("%d",ans);    return 0;}

## Double-row (Stage III - day 1)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 50010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int vis[maxn<<1],st,num,cnt,sum,n,ans,t;int a[2][maxn],to[2][maxn],gg[maxn<<1];void dfs(int x){    if(vis[x])return;    sum++;vis[x]=1;    if(a[st][x]==num)cnt++,num=a[!st][x],dfs(to[!st][x]);    else num=a[st][x],dfs(to[st][x]);}int main(){    n=read();    memset(vis,-1,sizeof(vis));    int tot=0;    for(int i=0;i<2;i++)for(int j=1;j<=n;j++)a[i][j]=read(),gg[tot++]=a[i][j];    sort(gg,gg+tot);    tot=unique(gg,gg+tot)-gg;    for(int i=0;i<2;i++)        for(int j=1;j<=n;j++)        {            a[i][j]=lower_bound(gg,gg+tot,a[i][j])-gg+1;            if(vis[a[i][j]]==-1)vis[a[i][j]]=n*i+j-1;            else to[i][j]=vis[a[i][j]]%n+1,to[vis[a[i][j]]/n][vis[a[i][j]]%n+1]=j;        }    memset(vis,0,sizeof(vis));    vis[0]=1;    for(int i=1;i<=n;i++)        if(!vis[i])        {            cnt=sum=0;            num=a[st=0][i];dfs(to[st][i]);            num=a[st=1][i];dfs(to[st][i]);            if(!vis[i])vis[i]=1,sum++;ans+=min(cnt,sum-cnt);        }    printf("%d",ans);    return 0;}

## The Bus (Stage III - day 2)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}struct poi{int x,y,s;}q[maxn];inline bool cmp(const poi &a,const poi &b){return a.x==b.x?a.y<b.y:a.x<b.x;}int c[maxn],xg[maxn],yg[maxn],xc,yc;void add(int x,int v){    for(;x<maxn;x+=x&-x)c[x]=max(c[x],v);}int ask(int x){    int ret=0;    for(;x;x-=x&-x)ret=max(ret,c[x]);    return ret;}int main(){    freopen("w.in","r",stdin);    int n=read(),m=read(),k=read();    for(int i=0;i<k;i++)        xg[i]=read(),yg[i]=read(),q[i]=(poi){xg[i],yg[i],read()};    sort(xg,xg+k);xc=unique(xg,xg+k)-xg;    sort(yg,yg+k);yc=unique(yg,yg+k)-yg;    for(int i=0;i<k;i++)        q[i].x=lower_bound(xg,xg+xc,q[i].x)-xg+1,        q[i].y=lower_bound(yg,yg+yc,q[i].y)-yg+1;    sort(q,q+k,cmp);    for(int i=0;i<k;i++)    {        int w=ask(q[i].y)+q[i].s;        add(q[i].y,w);    }    printf("%d\n",ask(maxn-1));    return 0;}

Next：POI 2006

• 私有
• 公开
• 删除