棋子

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

棋盘从左到右被分割成 n(n≤1000) 个格子，从左到右编号为1,2,...,n。棋盘上有 m(m≤n) 个棋子，编号为 1,2,...,m ，编号为i的棋子刚开始摆放在编号为 pi 的格子上，一个格子最多摆放一个棋子。每次操作小R可以选择一个棋子，将它移动到它右边第一个空着的格子中，如果它右边没有空着的格子了，那么这就是一个非法操作，执行一次非法操作不会对棋盘有任何改变。小R依次做了k次操作，如果一次操作是合法的，你需要输出这颗棋子移动到的格子的编号，如果是非法的，你需要输出"error!"。

输入格式

从标准输入读入数据。

第一行三个整数 n、m、k ，表示格子数、棋子数和操作数。

第二行 m 个正整数，第 i 个正整数表示 pi ，即第 i 个棋子的初始位置。

第三行 k 个正整数，第 i 个正整数表示 xi ，即第 i 次操作选定的棋子的编号。

输出格式

输出到标准输出。

输出 k 行，第i行表示第i次操作的结果。对于合法操作，输出棋子移动到的位置，对于非法操作，输出一行"error!"。

思路：

1000x10000暴力都能做，然而我看成了10000x10000

写了个超级麻烦的线段树

线段树怎么做呢？

首先，开一颗线段树

每个节点维护他的子树里面的0的个数

我们同时开一个映射数组

ys[i]表示当前编号为i的数在ys[i]这个位置

然后查询ys[i]~n这些位置的第一个0的位置

输出即可

如果一个没有

那就是不合法

合法的话更新线段树和映射数组即可

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<bitset>

#include<queue>

#include<cstdlib>

#include<algorithm>

#define rs 1024

#define rii register int i

#define rij register int j

using namespace std;

struct tree{

    int cnt,val,wz;

}x[];

int n,m,k,ys[];

void mem(int l,int r,int bh)

{

    x[bh].cnt=(r-l+);

    if(l==r)

    {

        x[bh].wz=l;

        return;

    }

    int mid=(l+r)/;

    mem(l,mid,bh*);

    mem(mid+,r,bh*+);

}

void add(int wz,int nl,int nr,int val,int bh)

{

    if(nl==wz&&nr==wz)

    {

        if(val==)

        {

            x[bh].cnt=;

        }

        else

        {

            x[bh].cnt=;

        }

        return;

    }

    int mid=(nl+nr)/;

    if(wz<=mid)

    {

        add(wz,nl,mid,val,bh*);

    }

    else

    {

        add(wz,mid+,nr,val,bh*+);

    }

    x[bh].cnt=x[bh*].cnt+x[bh*+].cnt;

}

int query(int l,int r,int nl,int nr,int bh)

{

    if(l<nl)

    {

        l=nl;

    }

    if(r>nr)

    {

        r=nr;

    }

    if(l==nl&&nr==nl)

    {

        return x[bh].wz;

    }

    int re=;

    int mid=(nl+nr)/;

    if(l<=mid)

    {

        if(x[bh*].cnt!=)

        {

            re=query(l,r,nl,mid,bh*);

        }

    }

    if(r>mid&&re==)

    {

        if(x[bh*+].cnt!=)

        {

            re=query(l,r,mid+,nr,bh*+);

        }

    }

    return re;

}

int main()

{

//    freopen("1.in","r",stdin);

    scanf("%d%d%d",&n,&m,&k);

    mem(,rs,);

    for(rii=;i<=m;i++)

    {

        int val;

        scanf("%d",&val);

        ys[i]=val;

        add(val,,rs,i,);

    }

    for(rii=;i<=k;i++)

    {

        int bh;

        scanf("%d",&bh);

        int wz=ys[bh];

        if(wz+>n)

        {

            puts("error!");

            continue;

        }

        int ltt=query(wz+,n,,rs,);

        if(ltt==)

        {

            puts("error!");

            continue;

        }

        else

        {

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

        }

        add(ltt,,rs,bh,);

        add(wz,,rs,,);

        ys[bh]=ltt;

    }

}

巴特西

code#5 P2 棋子

棋子

题目描述

输入格式

输出格式

思路：

代码：

最新文章

热门文章