BJOI2015 Day2

轮到罗剑桥出题了

这是什么风格，中文名称与英文名称分明对不上吗233

T1:

似乎只会做这道题23333

A....BE

........

C....DF

据题意数学变形得A-C<=B-D，B-D<=E-F，即左右的差是递增的。

A....B

.......

C....D

E....F

据题意数学变形得A-B<=C-D，C-D<=E-F，即上下的差是递增的。

那么令f1[i][j]=A[i][j]-A[i+1][j],f2[i][j]=A[i][j]-A[i][j+1]。

只有当f1[i][j-1]<=f1[i][j]且f2[i-1][j]<=f2[i][j]时 (i,j)才能进入矩形中。

那么问题就转化成最大子矩形，其内部没有坏点。

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

int A[maxn][maxn],B[maxn][maxn],C[maxn][maxn],n,m,ans;

int is[maxn][maxn];

int right[maxn],left[maxn],up[maxn][maxn];

int main() {

    freopen("neo.in","r",stdin);

    freopen("neo.out","w",stdout);

    n=read();m=read();

    rep(i,,n) rep(j,,m) A[i][j]=read();

    rep(i,,n) rep(j,,m) B[i][j]=A[i][j]-A[i+][j],C[i][j]=A[i][j]-A[i][j+];

    n--;m--;

    rep(i,,n) rep(j,,m) if(B[i][j]<=B[i][j+]&&C[i][j]<=C[i+][j]) is[i][j]=;

    rep(i,,n) {

        rep(j,,m) {

            if(!is[i][j]) continue;

            up[i][j]=up[i-][j]+;

            if(j==) left[j]=;

            else {

                left[j]=j;

                while(up[i][left[j]-]>=up[i][j]) left[j]=left[left[j]-];

            }

        }

        for(int j=m;j;j--) {

            if(!is[i][j]) continue;

            if(j==m) right[j]=m;

            else {

                right[j]=j;

                while(up[i][right[j]+]>=up[i][j]) right[j]=right[right[j]+];

            }

            ans=max(ans,(up[i][j]+)*(right[j]-left[j]+));

        }

    }

    printf("%d\n",ans);

    return ;

}

T2:简要题意，计算从最上角上方连一条管道到最下角下方的方案书数。

显然是不可做的插头DP，写个暴搜60

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

int n,m,ans;

char A[maxn][maxn];

int have[maxn][maxn];

int mx[]={,-,,},my[]={,,,-};

void dfs(int x,int y) {

     have[x][y]=;

     if(x==n&&y==m) ans++;

     else rep(dir,,) if(x>=&&x<=n&&y>=&&y<=m&&!have[x+mx[dir]][y+my[dir]]&&A[x+mx[dir]][y+my[dir]]=='.') dfs(x+mx[dir],y+my[dir]);

     have[x][y]=;

}

int main() {

    freopen("voda.in","r",stdin);

    freopen("voda.out","w",stdout);

    n=read();m=read();

    rep(i,,n) scanf("%s",A[i]+);

    if(A[][]=='#'||A[n][m]=='#') {puts("");return ;}

    dfs(,);printf("%d\n",ans%);

    return ;

}

T3:有一个N层M格的书架，可以将一本书移动到另一层，也可以把同一层的书左右移动，求从初始状态到最终状态的最少移动数。

考虑那些前后所在层不变的书，应对答案贡献总数-LCS的数目，如果这层全满，需要答案额外+1（先将一本拿到别层再拿回来）。

对于前后所在层变化的书，答案要+1表示移动一次，如果所在连通分量全满，同理答案要再+1.

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

int m,C[maxn],t[maxn*maxn],g[maxn];

int get(int* C,int len) {

    int ans=;

    rep(i,,len) g[i]=<<;

    rep(i,,len) {

        int k=lower_bound(g+,g+len+,C[i])-g;

        ans=max(ans,k);g[k]=C[i];

    }

    return ans;

}

int n,A[maxn][maxn],B[maxn][maxn],yes[maxn],ans;

int pos[maxn*maxn],pos2[maxn*maxn],first[maxn],next[maxn*maxn*],to[maxn*maxn*],e;

void AddEdge(int u,int v) {

    ans++;

    to[++e]=v;next[e]=first[u];first[u]=e;

    to[++e]=u;next[e]=first[v];first[v]=e;

}

int vis[maxn],f[maxn];

int dfs(int x) {

    if(vis[x]) return f[x];vis[x]=;

    int& ans=f[x];ans=!yes[x];

    for(int i=first[x];i;i=next[i]) ans&=dfs(to[i]);

    return ans;

}

int main() {

    freopen("police20.in","r",stdin);

    freopen("police.out","w",stdout);

    n=read();m=read();int ok=,dif=;

    rep(i,,n) rep(j,,m) {

        A[i][j]=read();

        if(!A[i][j]) ok=yes[i]=;

        else pos[A[i][j]]=i,pos2[A[i][j]]=j;

    }

    rep(i,,n) rep(j,,m) {

        B[i][j]=read();

        if(B[i][j]&&i!=pos[B[i][j]]) AddEdge(i,pos[B[i][j]]);

    }

    rep(i,,n) {

        int len=;

        rep(j,,m) if(B[i][j]&&pos[B[i][j]]==i) C[++len]=pos2[B[i][j]];

        int tmp=len-get(C,len);

        if(tmp) ans+=tmp+(len==m);

    }

    if(ans&&!ok) puts("-1");

    else {

        rep(i,,n) if(!vis[i]&&first[i]) ans+=dfs(i);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

BJOI2015 Day2

最新文章

热门文章