【NOIP2015模拟11.4】JZOJ8月6日提高组T1 刷题计划

题目

题解

题意

有\(n\)道题，编号为1~\(n\)

给出\(m\)次操作

每次操作有3种类型

1 \(x\) 表示交了\(AC\)的代码在编号为\(x\)的题

2 \(x\)表示交了没有\(AC\)的代码在编号为\(x\)的题

3 表示询问当前做过的题目中从来没有\(AC\)的题，晚交的先输出

对于每个3询问，输出前20个

分析

既然\(m\)只有100

那为什么不打暴力呢

对于每种操作

是1的话给题目打个\(AC\)标记

是2的话放入未\(AC\)数组，注意我们不在意之前是否\(AC\)

对于3，查找未\(AC\)数组中的没有打过\(AC\)标记的题目，并判断是否输出过，注意只输出前20个即可

（考试的时候没看见，30没了）

其实可以离散化也可以不离散化，看你的\(AC\)标记怎么打，像我的话就是给编号打标记

Code

#include<cstdio>

#include<cstring>

using namespace std;

int m,i,d,now,num,tot,p[105];

long long n,x,hash[10010];

bool b[10010],bj[10010];

int HASH(long long x)

{

    int pos;

    pos=x%10007;

    while (hash[pos]!=0)

    {

        if (hash[pos]==x) return pos;

        pos++;

        if (pos==10007) pos=0;

    }

    hash[pos]=x;

    return pos;

}

int main()

{

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

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

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

    while (m--)

    {

        scanf("%d",&d);

        if (d==1)

        {

            scanf("%lld",&x);

            now=HASH(x);

            b[now]=true;

        }

        if (d==2)

        {

            scanf("%lld",&x);

            now=HASH(x);

            if (b[now]==false)

            {

                num++;

                p[num]=now;

            }

        }

        if (d==3)

        {

            memset(bj,false,sizeof(bj));

            tot=0;

            for (i=num;i;i--)

            {

                if (b[p[i]]==false&&bj[p[i]]==false)

                {

                    printf("%lld ",hash[p[i]]);

                    bj[p[i]]=true;

                    tot++;

                }

                if (tot==20) break;

            }

            printf("\n");

        }

    }

    fclose(stdin);

    fclose(stdout);

    return 0;

}