P3892 [GDOI2014]OJ

· · 题解

Solution

题目很长，简单来说就是维护一个比赛系统。

先给出要维护的东西：

每场比赛每个用户对应的 AC 数量，每场比赛对应 AC 数量的人数，每个提交对应的编号、用户、比赛、和结果。

下面分操作讲述。

新建比赛。

其实新建比赛是没有用的，因为之后其他的操作中都会给出对应的比赛编号和题目编号（或者提交编号),所以并不需要记录比赛中有哪些题目。

提交。

对于一个 UNAC 的提交，记录每场比赛有哪些人是交过题了，如果当前这个提交对应的用户之前交过题，那么这个提交是不用管的，否则需要将 AC 数量为 0 的人数 +1（在对应的比赛中)。

如果是 AC 的提交，则将对应用户在对应比赛中的 AC 数量 +1。注意我们要先判断这个人是否曾经 AC 过这道题目，但如果直接开数组会爆空间，所以要用链式前向星，将对于这个用户和这道题对应比赛的 AC 数量打在连向对应比赛的边上（这里可能有点难懂，可以结合下面的代码理解）。

查询排名。

相当于给出一个过题数，在对应比赛中查找有多少人的过题数大于，多少人过题数等于。这里可以用数据结构或者前缀/后缀和。

重测。

跟提交差不多，如果原本的状态是 UNAC 的话，不需要管。

如果是 AC，则只需要将对应用户的 AC 数量 -1。

Code

#include<cstdio>
#define N 5005
#define M 350005
using namespace std;
struct sub
{
    int pid,cid,uid;
    bool res;
}sub[M];
struct contest
{
    int num[N],solve[N];
}con[55];
struct node
{
    int to,next;
}a[M];
int n,m,q,id,sid,cid,pid,uid,tot,cnt[M],head[N][N];
bool b[55][N];
char ch[20];
int read()
{
    int res=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();
    return res;
}
void add(int uid,int pid,int cid)
{
    a[++tot].to=cid;
    a[tot].next=head[uid][pid];
    head[uid][pid]=tot;
}
int find(int uid,int pid,int cid)
{
    for (int i=head[uid][pid];i;i=a[i].next)
    {
        int v=a[i].to;
        if (v==cid) return i;
    }
    return 0;
}
int main()
{
    n=read();m=read();q=read();
    while (q--)
    {
        scanf("%s",ch);
        if (ch[0]=='c')
        {
            int num,x;
            cid=read();num=read();
            for (int i=1;i<=num;++i)
                x=read();
        }
        else if (ch[0]=='s')
        {
            int sid,cid,pid,uid;
            sid=read();cid=read();pid=read();uid=read();scanf("%s",ch);
            sub[sid].cid=cid;sub[sid].pid=pid;sub[sid].uid=uid;sub[sid].res=(ch[0]=='A');
            if (!b[cid][uid])
            {
                b[cid][uid]=true;
                con[cid].num[0]++;
            }
            if (ch[0]=='A')
            {
                id=find(uid,pid,cid);
                if (!id) add(uid,pid,cid),id=tot;
                ++cnt[id];
                if (cnt[id]==1) con[cid].num[++con[cid].solve[uid]]++;
            }
        }
        else if (ch[0]=='g')
        {
            cid=read();uid=read();
            int pnum=con[cid].solve[uid];
            printf("%d %d %d %d\n",uid,pnum,con[cid].num[pnum+1]+1,con[cid].num[pnum]);
        }
        else if (ch[0]=='r')
        {
            sid=read();
            uid=sub[sid].uid;cid=sub[sid].cid;pid=sub[sid].pid;
            if (sub[sid].res)
            {
                int id=find(uid,pid,cid);
                --cnt[id];
                if (cnt[id]==0) con[cid].num[con[cid].solve[uid]--]--;
            }
        }
    }
    return 0;
}