THU2017spring 1-2 Company 题解

THU2017spring 1-2 Company


描述

公司有n个员工,编号1 ~ n。员工数量众多,需要你为他们编写一个管理系统。

员工上班时都要登录管理系统登记一个code,离开要从管理系统上注销,员工也可以随时更新自己的code。到了下班时间,所有员工都会自动注销。公司管理人员随时都可能想要知道有多少员工上班,以及任一员工登记的code。

输入

第一行两个整数n、m。接下来m行,每行都是以下内容之一:

1
2
3
4
5
I a c   //Log In:员工a登录,code为c。若a已登录,则将code更新为c
O a     //Log Out:编号为a的员工注销。若a未登录,则注销无效
C           //Close:到下班时间,所有员工注销
N           //Number:询问有多少员工正在上班
Q a     //Query:询问员工a的code(若未登录或已注销,视为-1)

输出

一个整数,是所有询问(N、Q)的答案之和(int表示,自动溢出,不用管溢出部分)

输入样例

1
2
3
4
5
6
7
8
9
10 8
I 1 2
I 1 4
Q 1
C
I 2 4
O 2
Q 2
N

输出样例

1
2
3
//“Q 1”答案是4,“Q 2”答案是-1,“N”答案是0,所有答案之和为3

限制

n <= 10,000,000

m <= 1,000,000

1<=a<=n

code为[0, 2^31)的整数

空间限制:256 MB

时间限制:2 sec

提示

一级提示

测试数据中,每种操作都可能频繁出现,或很少出现。因此,你的算法需要应对所有可能的情况。

● Bitmap / 常数时间初始化的数组

● Bitmap: 习题解析[2-34],实例参考[2-35],[2-36]

二级提示

● 避免频繁初始化整个数组。

● 可以借助Bitmap记录数组的各元素是否已被初始化。将一个(或所有)元素置为未初始化状态,实质上只需要打破“校验环”两个验证条件中的任何一个,考虑如何打破校验条件的复杂度最低。

● 还可以使用“懒删除”策略。

● 参考习题[2-34]。

用scanf(“%c”, …)或getchar()读入一个字符时,可能会读到空格、制表符、回车符或换行符,尽量避免使用这个方法。使用scanf(“%s”, …)会自动过滤空白字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    setvbuf(stdin,new char[1<<24],_IOFBF,1<<24);
    setvbuf(stdout,new char[1<<24],_IOFBF,1<<24);
    int n,m;
    scanf("%d %d",&n,&m);
    int * staffs=new int[n+1];
    int * version_arr=new int[n+1]; //使用版本号
    memset(staffs,-1,sizeof(int)*(n+1));
    memset(version_arr,-1,sizeof(int)*(n+1));
    int sum=0;
    int staff_num=0,version=0;
    while(m--){
        char c;
        do{
            scanf("%c",&c);
        }while(c>'Z'||c<'A');
        switch(c){ //登录
        case 'I':
            int a,c;
            scanf("%d %d",&a,&c);
            if(version_arr[a]<version||staffs[a]==-1&&version_arr[a]==version)staff_num++; //版本号在过去或者当前版本号并且未登录
            staffs[a]=c;
            version_arr[a]=version; //更新版本号
            break;
        case 'O': //注销
            int b;
            scanf("%d",&b);
            if(version_arr[b]==version&&staffs[b]!=-1)staff_num--; //原来版本号的不需要去减,当前版本号登陆过的才需要去减,在twd2的提醒下才加上staffs[b]!=-1
            staffs[b]=-1;
            break;
        case 'C':
            version++;
            staff_num=0;
            break;
        case 'N':
            sum+=staff_num;
            break;
        case 'Q':
            int d;
            scanf("%d",&d);
            if(version_arr[d]<version||staffs[a]==-1&&version_arr[a]==version)sum-=1;//原来版本号,当前版本号未登录都是-1
            else sum+=staffs[d];
            break;
        }
    }
    printf("%d",sum);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注