@Scarlet 2017-01-12T12:07:00.000000Z 字数 3034 阅读 1295

# POI 2004

POI 2004 OI 解题报告

## Game (Stage I) (0/100)

1. 若$a[n]=m-1$，则只能移动最后一枚棋子，$Ans=1$
2. 若谁移动后所有棋子都在$[m-n-1..m-2]$，则胜。故可转化模型：两个空格之间作为楼梯，$m-2$$m-1$间作为地面，连续棋子数B作为石子数，则成为经典问题（见论文）。

Too difficult.

#include<bits/stdc++.h>#define N 1001000#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,m,i,now,tot,top,ans,sum,a[N],b[N];int main(){    m=read(),n=read();a[n+1]=m-1;    for(int i=1;i<=n;i++)a[i]=read();    if(a[n]>=m-1)    {        for(int i=n;i&&a[i]-a[i-1]==1;i--)sum++;        return printf("%d",sum+1),0;    }    for(int i=n;i;i--,now++)        if(a[i+1]-a[i]!=1)        {            b[top++]=now;now=0;            if(a[i+1]-a[i]>2)top+=2-((a[i+1]-a[i])&1);        }    b[top]=now;    for(int i=1;i<=top;i++)        if(i&1)ans^=b[i];    for(int i=1;i<=top;i++)        if( (i&1)&&(b[i]^ans)<b[i] || !(i&1)&&(b[i-1]^ans)>b[i-1]&&((b[i-1]^ans)<=b[i]+b[i-1]))            sum++;    printf("%d",sum);}

## The Bridge (Stage II - day 0) (0/100)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100010using 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,a[maxn],f[maxn];int main(){    n=read();    for(int i=1;i<=n;i++)a[i]=read();    if(n<=2)return printf("%d",a[n]),0;    for(int i=n-1;i>=2;i--)    {        f[i]=f[i+1]+a[1]+a[i+1];        if(i<=n-2)f[i]=min(f[i],f[i+2]+a[i+2]+a[1]+a[2]*2);    }    printf("%d",f[2]+a[2]);}

## Passage (Stage II - day 2) (0/100)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 20#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;}using namespace std;int t[maxn],w[maxn],f[1<<16],T[1<<16],s[1<<16];int bin[maxn],W,n;int main(){    memset(f,63,sizeof(f));    bin[0]=1;for(int i=1;i<maxn;i++)bin[i]=bin[i-1]<<1;    W=read(),n=read();    for(int i=0;i<n;i++)        t[i]=read(),w[i]=read();    for(int i=0;i<bin[n];i++)        for(int j=0;j<n;j++)            if(i&bin[j])                T[i]=max(T[i],t[j]),s[i]+=w[j];    f[0]=0;    for(int i=1;i<bin[n];i++)        for(int j=i;j;j=i&(j-1))            if(s[j]<=W)f[i]=min(f[i],T[j]+f[i^j]);    printf("%d",f[bin[n]-1]);}

• 私有
• 公开
• 删除